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 に答える