1

我正在尝试重现 Fisher-Yates 算法以将数组改组到位：

问题是当我为“幼稚”的洗牌运行第一步时，我的结果非常均匀。我没有看到某些组合的预期偏差。我已经进行了多达 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)
4

1 回答 1

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})
于 2013-08-14T16:12:39.110 回答