リストのシャッフルミスによる精度比較
リストを完全にランダムに並び替える場合、fisher-yatesのアルゴリズムを使うといいらしい。 ただ、検索してみると間違った実装をしている例も多く見かけた。
ランダムに選択するインデックスを、常にリスト全体からとってしまっているために 後半になるほど置換が重複するらしい。
間違った実装をしても検証がしにくいため気づきにくいのかもしれない。
間違ったアルゴリズムと正しいアルゴリズムで、並び替えの分布を調べてみた。
分布の偏りが結構大きいことが分かる。 よくあるミスらしいので、間違えないように覚えておきたい。
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()