如何隨機洗牌的排列次序比PRNG的時間更長？

我有一個包含3900個元素的列表，我需要產生隨機排列來產生統計分佈。我環顧四周，發現Maximal Length of List to Shuffle with Python random.shuffle解釋了Python中PRNG的週期爲2**19937-1，這導致列表的最大長度爲2080，因此無法生成所有可能的排列。我只產生300-1000個列表的排列，所以我不太可能會產生重複的排列，但是，因爲這是一個產生統計分佈，我想所有可能的排列作爲潛在的樣本。如何隨機洗牌的排列次序比PRNG的時間更長？

來源

2015-12-07 Darwin

你想產生所有可能的3900個元素的排列？ – Tempux

你有沒有考慮過使用'os.urandom'？ urandom適合加密，所以我認爲它應該適用於你正在做的任何事情。 – senshin

出於統計的目的 - 實際上，基本上用於任何目的 - 可能的排列限制是沒有問題的。如果你擔心這一點，你會有更大的偏離理想的分配擔心。 – user2357112

我同意@ user2357112，它不可能是一個真正的問題 - 但它看起來像你應該能夠使用標準random模塊的方式，所有的排列至少是可能的。

你可以做一個分而治之的方法。使用初始種子將列表分成兩個大約2000個列表。這些分區的數量大致爲C(4000,2000)，大約爲1.66 x 10^1202。這少於該期間，這表明至少可以用random.sample()生成所有這樣的分區。然後 - 重新設置隨機數生成器並排列前半部分。然後 - 再次重新鑲嵌，然後排列下半部分。也許在重新加載之前有一點時間延遲，這樣你就不會遇到涉及解析系統時鐘的問題。您也可以嘗試將初始列表隨機分成大量較小的列表。

在數學上很容易看出，如果隨機將列表分成子列表以便每個分區具有相同的可能性，然後以每個子列表排列所有子列表排列的可能性相同的方式排列，並將這些子列表粘合在一起排列得到一個完整的列表排列，那麼所有的全列表排列都是相同的可能性。

這是一個實現：

import random, time 

def permuted(items, pieces = 2): 
    sublists = [[] for i in range(pieces)] 
    for x in items: 
     sublists[random.randint(0,pieces-1)].append(x) 
    permutedList = [] 
    for i in range(pieces): 
     time.sleep(0.01) 
     random.seed() 
     random.shuffle(sublists[i]) 
     permutedList.extend(sublists[i]) 
    return permutedList

我不知道那是真正需要time.sleep(0.01)。我擔心的是，如果種子在一毫秒內發生，那麼在一些系統上可能會使用相同的種子。

作爲最後一句話，僅僅因爲上述函數（適當選擇pieces）不能通過簡單的計數參數顯示錯過某些置換（比較置換數與初始狀態數）本身並不構成所有排列實際上都是可能的證據。這將需要對隨機數生成器，對其進行種子處理的散列函數以及混洗算法進行更詳細的分析。

來源

2015-12-08 19:15:17

這似乎是一個非常好的解決方案。你能否提供一個用於隨機分割原始列表的代碼示例？ – Darwin

@達爾文我添加了代碼。 –

有較長的PRNGs比MT，但他們很難找到。

要得到所有3090！組合，你需要40,905比特的熵。大約5kb。你應該能夠從random.org那裏抓取大小不小的字節塊，而且沒有問題。爲了精確平衡，你必須添加一些並做拒絕抽樣。即，每次抓取12位（0..4095），並拒絕高於當前循環索引的數字。這可能會誇大所需的位數，但可能不會超過8kb。

來源

2015-12-07 23:40:32

如何隨機洗牌的排列次序比PRNG的時間更長？

回答

相關問題