Go First Dice Wiki

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====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// 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.

===Python Code===
<code>
1  s = "abcddbaccbadcabddacbdbcadcbadcabbcaddacbbacdabcdacbdbcaddbacdabccabddcba"
2  count = {"" : 1}
3  for c in s:
4      for k in count.keys():
5          if k.count(c)==0:
6              k2 = k + c
7              count[k2] = count.get(k2,0) + count[k]
</code>

  *  s is just the input dice set
  *  count will contain how many ways each substring can occur. We initialize it to say that from the get-go, there is only one way to have the empty string.
  *  We step through every number in the die step. Each step will depend on the previous step.
  *  We need to look at all substrings. The real magic happens on line 7
  *  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.
  *  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>

[[http://www.ericharshbarger.org/cgi-bin/basic_perm_check.pl|Here is a Perl script implementation of the permutation-fairness checking in action.]]
Go First Dice Wiki

User Tools

Site Tools

Page Tools
