Как проверить, что алгоритм тасования одинаков?

Question

У меня есть простая реализация 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 ), но они не отвечают на мой вопрос.Было бы замечательно понять, как выполнять такие проверки в целом.

Answer 1

Если вы случайным образом перетасовываете одни и те же предметы из заданного фиксированного порядка, то количество каждого элемента в одной фиксированной позиции в перетасованных элементах должно стремиться к одному и тому же значению.

НижеЯ перетасовываю список 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! становится большим, быстрым ;и если он «сопоставим», конечно, больше, чем возможный диапазон вашего генератора случайных чисел, то он ломается.

Answer 2

Вы можете точно это проверить, введя все возможные последовательности случайных чисел в 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' и убедиться, что вы получаете каждую перестановку хотя бы один раз).

Answer 3

РЕДАКТИРОВАТЬ:

Как Пол Ханкин в комментариях, мой оригинальный тест только проверил, что вероятность попадания каждого элемента в каждую позицию, но не всеперестановки одинаково вероятны, что является более строгим требованием.Приведенный ниже фрагмент подсчитывает частоту каждой перестановки, на что мы и должны смотреть:

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

Если случайный порядок равен, значения результирующего вектора freq должны быть распределены в соответствии с биномиальнымраспределение с T * N! испытаниями и вероятностью успеха 1 / (N!).Вот график оценки распределения для предыдущего примера (с Seaborn ), где значения частоты должны быть около 1000:

Что, мне кажется, выглядит хорошо , но для количественного результата вам потребуется более глубокий статистический анализ, такой как критерий хи-квадрат Пирсона , как предлагает Дэвид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 является «достаточно маленьким».

Эти «достаточно близкие» и «достаточно маленькие», хотя и не очень твердые понятия.Обоснованный анализ требует большего количества статистических инструментов.Я думаю, вам нужно будет проверить гипотезу , что каждое значение частоты выбирается из биномиального распределения с T испытаниями с 1 / N вероятностью успеха.Как я уже сказал, у вас нет предыстории для полного объяснения этого, и это, вероятно, не место для этого, но если вам действительно нужен тщательный анализ, вы можете прочитать эту тему.