如何验证洗牌算法的一致性?

编辑:

AS Paul Hankin 在评论中,我最初的测试只检查了每个元素落入每个位置的概率,而不是所有排列的概率相等,这是一个更强的要求。下面的片段统计每个排列的频率,这是我们应该看到的:

import math
import random

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

# This function computes a unique index for a given permutation
# Adapted from https://www.jaapsch.net/puzzles/compindx.htm#perm
def permutation_index(permutation):
    n = len(permutation)
    t = 0
    for i in range(n):
      t = t * (n - i)
      for j in range(i + 1, n):
        if permutation[i] > permutation[j]:
            t += 1
    return t

N = 6  # Test list size
T = 1000  # Trials / number of permutations

random.seed(100)
n_perm = math.factorial(N)
trials = T * n_perm
ar = list(range(N))
freq = [0] * n_perm
for _ in range(trials):
    ar_shuffle = ar.copy()
    knuth_shuffle(ar_shuffle)
    freq[permutation_index(ar_shuffle)] += 1

如果shuffle是一致的,则 freq 向量应按二项分布 T * N! 试验和成功概率 1 / (N!) . 下面是上一个示例的分布估计图(使用 Seaborn ,其中频率值应在1000左右:

我觉得看起来 好的 但同样,对于定量结果,您需要更深入的统计分析,例如 Pearson's chi-squared test ,由建议 David Eisenstat .

原始答案:

我将在这里提出一些基本的想法,但我没有最强大的统计背景,所以可能有人想补充或纠正任何错误。

您可以将每个值的频率矩阵放入每个位置进行多次试验:

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

N = 100  # Test list size
T = 10000  # Number of trials
ar = list(range(N))
freq = [[0] * N for _ in range(N)]

for _ in range(T):
    ar_shuffle = ar.copy()
    kunth_shuffle(ar_shuffle)
    for i, j in enumerate(ar_shuffle):
        freq[i][j] += 1

一旦你能做到这一点,你可以采取几种方法。一个简单的想法是,如果洗牌是均匀的, freq / T 应该倾向于 1 / N 作为 T 趋向于无限。所以你可以用一个“非常大”的值 T 并确保这些值“足够接近”。或检查 freq / T - 1 / N 是“足够小”。

这些“足够近”和“足够小”虽然不是很坚实的概念。扎根分析需要更多的统计工具。我想你需要 test the hipothesis 每个频率值都是从 binomial distribution 具有 T 试验A 1/n 成功概率。正如我所说,没有充分解释的背景,这可能不是它的地方,但如果你真的需要一个彻底的分析,你可以阅读的主题。

通过将所有可能的随机数序列注入 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的输入列表的正确性。你可以在n之前再往前走一点!变得太大了。

您还需要使用 random.randint (例如生成500个“abcd”洗牌,并确保每个排列至少得到一次)。

如果从给定的固定顺序随机洗牌相同的项目,则 一 洗牌项目中的固定位置应该趋向于相同的值。

下面我将列表0..9洗几次并打印输出:

from random import shuffle  # Uses Fischer-Yates

tries = 1_000_000
intcount = 10
first_position_counts = {n:0 for n in ints}
ints = range(intcount)
for _ in range(tries):
    lst = list(ints)   # [0, 1, ...9] In that order
    shuffle(lst)
    first_position_counts[lst[0]] += 1

print(f'{tries} shuffles of the ints 0..{intcount-1} should have each int \n',
      'appear in the first position {tries/intcount} times.')
for item in first_position_counts.items():
    print(' %i: %5i' % item)

跑一次你可能会得到这样的东西:

 0: 99947
 1: 100522
 2: 99828
 3: 100123
 4: 99582
 5: 99635
 6: 99991
 7: 100108
 8: 100172
 9: 100092

再说一遍:

 0: 100049
 1: 99918
 2: 100053
 3: 100285
 4: 100293
 5: 100034
 6: 99861
 7: 99584
 8: 100055
 9: 99868

现在如果你有成千上万的物品要洗牌,那么它们应该在 n! 排列, 但是 n! 变得很大,古怪 ;如果它是“可比的”,肯定比随机数生成器的可能范围更大,那么它就会崩溃。