Differences

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

--- fast_perm_check [2023/03/21 15:10]
harshec
+++ fast_perm_check [2023/04/19 10:30] (current)
harshec
@@ Line 1: / Line 1: @@
 ====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.
@@ Line 22: / Line 22: @@
   *  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

Differences

Page Tools