我有一个简单的Knuth's shuffling algorithm的Python实现
def knuth_shuffle(ar):
num = len(ar)
for i in range(num):
index = random.randint(0, i)
ar[i], ar[index] = ar[index], ar[i]
return ar
如何测试(使用scipy
或其他任何包)混洗确实是一致的?我找到了一些相关的帖子(1,2),但它们都没有回答我的问题。了解如何在一般情况下执行这样的检查将是很棒的。
发布于 2018-05-31 02:38:48
您可以通过将所有可能的随机数序列注入到knuth_shuffle
中,然后验证您恰好一次获得每个排列,来精确地检查这一点。
这段代码可以做到这一点:
import collections
import itertools
import random
def knuth_shuffle(ar, R=random.randint):
num = len(ar)
for i in range(num):
index = R(0, i)
ar[i], ar[index] = ar[index], ar[i]
return ar
def fact(i):
r = 1
while i > 1:
r *= i
i -= 1
return r
def all_random_seqs(N):
for r in range(fact(N)):
seq = []
for i in range(N):
seq.append(r % (i+1))
r //= (i+1)
it = iter(seq)
yield lambda x, y: next(it)
for N in range(1, 6):
print N
results = collections.Counter()
for R in all_random_seqs(N):
a = list('ABCDEFG'[:N])
knuth_shuffle(a, R)
results[''.join(a)] += 1
print 'checking...'
if len(results) != fact(N):
print 'N=%d. Not enough results. %s' % (N, results)
if any(c > 1 for c in results.itervalues()):
print 'N=%d. Not all permutations unique. %s' % (N, results)
if any(sorted(c) != list('ABCDEFG'[:N]) for c in results.iterkeys()):
print 'N=%d. Some permutations are illegal. %s' % (N, results)
这段代码检查大小为1,2,3,4,5的输入列表的正确性。变得太大了。
您还需要使用random.randint
对代码版本执行健全性检查(例如,生成500次“ABCD”混洗,并确保每个排列至少获得一次)。
https://stackoverflow.com/questions/50609193
复制相似问题