たかがシャッフル、されどシャッフル 〜"permute-with-all" order biasの検証〜

先日、
【Swift4】 ArrayをShuffleする
というタイトルで投稿しました。

var anArray = ["阿部","伊東","佐藤","鈴木","田中","中村","藤井","松井","村田","吉田"]
for i in 0 ..< anArray.count{
            let r = Int(arc4random_uniform(UInt32(anArray.count)))
            anArray.swapAt(i, r)
        }

上記の方法では、結果に偏りが生じるというコメントを頂き、以下のサイトを教えて頂きました。
フィッシャー–イェーツのシャッフル：誤った実装による順序の偏り
それを踏まえて、"permute-with-all" order biasを検証してみました。

        //要素数 = n,試行回数 = repeatCount (自由に変更して下さい)
        let n = 5
        let repeatCount = 100000
        //twoDimArray[要素番号][試行回数何回目か] = 移動先の番号
        var twoDimArray = [[Int]]()
        let originalArray = Array<Int>(0 ..< n)
        for _ in 0 ..< n{
            twoDimArray.append([])
        }
        for _ in 0 ..< repeatCount{
            var anArray = originalArray
            for i in 0 ..< n{
                let r = Int(arc4random_uniform(UInt32(n)))
                anArray.swapAt(i, r)
                }
            for i in 0 ..< n{
                twoDimArray[i].append(anArray.index(of: i)!)
                }
        }
        for i in 0 ..< n{
            var postShuffleCite = [Int](repeating: 0, count: n)
            for j in 0 ..< repeatCount{
                postShuffleCite[twoDimArray[i][j]] += 1
            }
            for k in 0 ..< n{
                let probability = Double(postShuffleCite[k]) / Double(repeatCount) * 100.0
                print("\(i)が\(k)番目に移動する確率は、\(probability)%")
            }
            print("\n")
        }

n = 5、試行回数10万回で検証して以下のような結果を得ました。

0が0番目に移動する確率は、19.839%
0が1番目に移動する確率は、20.138%
0が2番目に移動する確率は、20.078%
0が3番目に移動する確率は、19.942%
0が4番目に移動する確率は、20.003%

1が0番目に移動する確率は、24.255%
1が1番目に移動する確率は、18.19%
1が2番目に移動する確率は、18.485%
1が3番目に移動する確率は、19.104%
1が4番目に移動する確率は、19.966%

2が0番目に移動する確率は、20.902%
2が1番目に移動する確率は、22.843%
2が2番目に移動する確率は、17.436%
2が3番目に移動する確率は、18.719%
2が4番目に移動する確率は、20.1%

3が0番目に移動する確率は、18.423%
3が1番目に移動する確率は、20.351%
3が2番目に移動する確率は、23.144%
3が3番目に移動する確率は、18.018%
3が4番目に移動する確率は、20.064%

4が0番目に移動する確率は、16.581%
4が1番目に移動する確率は、18.478%
4が2番目に移動する確率は、20.857%
4が3番目に移動する確率は、24.217%
4が4番目に移動する確率は、19.867%

・・・かなり大きな偏りが出るようです。
ちなみにn = 7にすると「フィッシャー–イェーツのシャッフル (Wikipedia)」の"permute-with-all" order biasのサンプルとほぼ同様の結果が得られました。

※※偏りをなくす方法※※

let r = Int(arc4random_uniform(UInt32(n)))

を以下のように書き換えます。

let r = Int(arc4random_uniform(UInt32(n - i))) + i

上記により、シャッフル後の移動確率が均一になります。

※以下のように、extensionにする方法もあります。

extension Array{
    mutating func shuffle(){
        let n = self.count
        for i in 0 ..< n{
            let r = Int(arc4random_uniform(UInt32(n - i))) + i
            self.swapAt(i, r)
        }
    }
}

それから、

for i in 0 ..< n{
                let r = Int(arc4random_uniform(UInt32(n)))
                anArray.swapAt(i, r)
                }

の部分を

anArray.shuffle()

と書き換えます。
extensionの中身を色々書き換えて上記コードを用いれば、shuffle後の偏りの検証に使えますので皆様ご利用下さい。