如何測試洗牌程序 - tudas－IT工程師數位筆記本

文章出處

關于洗牌程序的文章，之前已經寫過一篇，http://www.cnblogs.com/tudas/p/3-shuffle-algorithm.html ，因為上次被nie大神們重新問到且沒有正確回答上來，所以有必要在研究一下。

這次來說說n張牌的洗牌程序如何測試。眾所周知，洗牌即得到n的一個全排列結果（1/n!），因此每張牌在每個位置出現的概率是1/n。

一個洗牌程序的功能是，對于長度為n的兩兩不同的數組，輸出的任何一個排列的概率相等，也就是1/n!。可以驗證，Fisher-Yates算法是可以保證這一點的。

貼上我的測試代碼：

import random

#測試次數
test_count = 10000

#記錄字典
counter = {}

#測試集合
char_array = [ 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j' ]

#fisher_yates洗牌算法
def fisher_yates_shuffle( array ):
    array_len = len( array )
    for i in range( array_len - 1, 0, -1 ):
        r = random.randrange( 0, i)
        array[ i ], array[ r ] = array[ r ], array[ i ]
    return array

#記錄每張牌在每個位置出現的次數
def count( array, counter ):
    for i in range( len( char_array ) ):
        char = array[ i ]
        pos = i + 1
        if not counter.get( char ):
            counter[ char ] = {}
        if not counter[ char ].get( pos ):
            counter[ char ][ pos ] = 0
        counter[ char ][ pos ] += 1

#測試test_count次
for i in range( test_count ):
    shuffled = fisher_yates_shuffle( char_array )
    count( shuffled, counter )

#打印結果
for key in sorted( counter.keys() ):
    print( key, counter[ key ] )