如何验证一个混洗算法是一致的？
如何验证一个混洗算法是一致的？
提问于 2018-05-31 00:08:11
我有一个简单的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)，但它们都没有回答我的问题。了解如何在一般情况下执行这样的检查将是很棒的。
回答 1
Stack Overflow用户
发布于 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”混洗，并确保每个排列至少获得一次)。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/50609193
复制相关文章
相似问题