Python(天真的)洗牌到位 - 旨在重现 Fisher-Yates

Question

我正在尝试重现 Fisher-Yates 算法来对数组进行适当的洗牌:

• ref1: Coding Horror
• ref2: Eli Bendersky

问题是，当我运行“天真的”洗牌的第一步时，我的结果非常均匀；我没有看到某些组合的预期偏差。我已经运行了多达 600 万次试验:

• 123 --> 999,472 (16.7%)
• 132 --> 999,588 (16.7%)
• 213 --> 1,000,883 (16.7%)
• 231 --> 1,001,306 (16.7%)
• 312 --> 999,702 (16.7%)
• 321 --> 999,049 (16.7%)
• TOT --> 6,000,000 (100.0%)

我怀疑我的实现存在“问题”，希望得到反馈。

这是我正在使用的代码:

import random
from pprint import pprint

runLength = 600000

cards = [1, 2, 3]
sequenceCount = {'123':0, '132':0, '213':0, '231':0, '312':0, '321':0}

for k in range(runLength):

    # naive shuffle
    for i,v in enumerate(cards):
        n = random.randint(0, len(cards)-1)
        cards[i], cards[n] = cards[n], cards[i] #swap

    # track results
    strDeck = ''
    for j,v in enumerate(cards):
        strDeck = strDeck + str(cards[j])
    sequenceCount[strDeck] = sequenceCount[strDeck] + 1

# results summary
pprint(sequenceCount)

Answer 1

啊哈哈，问题是你一次又一次地重新洗牌，而不是总是使用[1,2,3]作为起点。而且你的Python非常不惯用并且有点难以阅读，所以让我为你重写它;)

import random
from pprint import pprint
from collections import Counter

runLength = 600000

sequenceCount = Counter()
originalCards = ["1", "2", "3"]
ncards = len(originalCards)

for k in range(runLength): # use xrange on python 2
    cards = list(originalCards)

    # naive shuffle        
    for i in range(ncards):
        n = random.randint(0, ncards - 1)
        cards[i], cards[n] = cards[n], cards[i] #swap

    sequenceCount[''.join(cards)] += 1

# results summary
print(sequenceCount)

# result: Counter({'132': 111424, '231': 111194, '213': 110312, 
#                  '123': 89533, '321': 88846, '312': 88691})