Go First Dice Wiki

User Tools

Site Tools

Trace:
fast_perm_check

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
Next revision 		Previous revision
fast_perm_check [2023/03/21 19:07]
harshec 		fast_perm_check [2023/04/19 14:30] (current)
harshec
Line 1: Line 1:
 ====Fast-Perm-Check==== ====Fast-Perm-Check====
-This algorithm was created by Landon Kryger to solve the problem of testing if a set of dice is permutation fair. If you have //n// players and //s// sides, the standard approach would require you to test every roll and would run in O(//s//<sup>//n//</sup>). This algorithm runs in approximately O(//s//*//n//*//n//!). For small //s//,//n//, it's not a very noticeable difference, but for large values like //n//=5;//s//=30 the benefit is huge.+This algorithm was created by Landon Kryger to solve the problem of testing if a set of dice is permutation fair. If you have //n// players and //s// sides, the standard approach would require you to test every roll and would run in O(//s//<sup>//n//</sup>). This algorithm runs in approximately O(//s//*//n//*//n//!). For small //s// and //n//, it's not a very noticeable difference, but for large values like //n//=5;//s//=30 the benefit is huge.
  
 This algorithm also works with dice with different number of sides. This algorithm also works with dice with different number of sides.
  
-Python Code+===Python Code===
 <code> <code>
 1  s = "abcddbaccbadcabddacbdbcadcbadcabbcaddacbbacdabcdacbdbcaddbacdabccabddcba" 1  s = "abcddbaccbadcabddacbdbcadcbadcabbcaddacbbacdabcdacbdbcaddbacdabccabddcba"
Line 21: Line 21:
   *  We don't need to look at strings like 'aba'. A die can only produce a number once per roll.   *  We don't need to look at strings like 'aba'. A die can only produce a number once per roll.
   *  k2 is the new string concatenated with the current die/number we're processing.   *  k2 is the new string concatenated with the current die/number we're processing.
-  *  The simplest way to explain this is with an example. Let's say the current letter is a c. The number of ways to make 'abc' now will be equal to how many you could do before plus how many ways you could do 'ab' because all those 'ab's now can have a 'c' added to them.+  *  The simplest way to explain this is with an example. Let's say the current letter is a c. The number of ways to make 'abc' now will be equal to how many you could do before plus how many ways you could do 'ab' because all those 'ab's now can have a 'c' added to them.<code>count['abc'] += count['ab']</code>
  
-    count['abc'] += count['ab']+[[http://www.ericharshbarger.org/cgi-bin/basic_perm_check.pl|Here is a Perl script implementation of the permutation-fairness checking in action.]]
fast_perm_check.1679425664.txt.gz ยท Last modified: 2023/03/21 19:07 by harshec

Page Tools

Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki