takecの気まぐれブログ

プログラミング等の話題を気まぐれに

リストのシャッフルミスによる精度比較

リストを完全にランダムに並び替える場合、fisher-yatesのアルゴリズムを使うといいらしい。 ただ、検索してみると間違った実装をしている例も多く見かけた。

kujirahand.com

ランダムに選択するインデックスを、常にリスト全体からとってしまっているために 後半になるほど置換が重複するらしい。

間違った実装をしても検証がしにくいため気づきにくいのかもしれない。

間違ったアルゴリズムと正しいアルゴリズムで、並び替えの分布を調べてみた。

分布の偏りが結構大きいことが分かる。 よくあるミスらしいので、間違えないように覚えておきたい。

f:id:takecccc:20170825054719p:plain

import random
import math
import numpy as np
import matplotlib.pyplot as plt
size = 5
N = 1000000

dist_wrong   = np.zeros(math.factorial(size))
dist_correct = np.zeros(math.factorial(size))

def shuffle_wrong(ary, size):
    for i in range(0,size):
        j = random.randrange(size)
        t = ary[i]
        ary[i] = ary[j]
        ary[j] = t
    return ary

def shuffle_correct(ary, size):
    for i in range(size-1,0,-1):
        j = random.randrange(i+1)
        t = ary[i]
        ary[i] = ary[j]
        ary[j] = t
    return ary

def get_permutation_pos(ary, size):
    pos = 0
    numlist = list(range(size))
    for i in range(size-1):
        index = numlist.index(ary[i])
        pos += index * math.factorial(size-1-i)
        del numlist[index]
    return pos

# 間違ったアルゴリズムの分布
for n in range(N):
    ary = list(range(size)) # 1~(size-1)の数列
    ary = shuffle_wrong(ary,size)      # ランダムに並び替え(間違い)
    pos = get_permutation_pos(ary,size) # 並び替えられた数列が、順列の何番目か計算
    #print(ary,pos)
    dist_wrong[pos] += 1 # 求められた位置の数を足す。

for n in range(N):
    ary = list(range(size)) # 1~(size-1)の数列
    ary = shuffle_correct(ary,size)     # ランダムに並び替え(正解)
    pos = get_permutation_pos(ary,size) # 並び替えられた数列が、順列の何番目か計算
    #print(ary,pos)
    dist_correct[pos] += 1 # 求められた位置の数を足す。

plt.plot(dist_wrong, label="wrong")
plt.plot(dist_correct, label="correct")
plt.ylim( ( 0, np.mean(dist_correct)*2 ) )
plt.xlabel("position")
plt.ylabel("count")
plt.legend()
plt.savefig("dist.png")
plt.show()