測試沒有 Fisher-Yates 生成的隨機排列的隨機性？
問題概述
在立即將其標記為重複之前，我對測試 Fisher-Yates shuffle 的隨機性不感興趣，因為這可以通過測試底層 RNG 來完成。我有興趣測試任何生成隨機排列的函式的質量。
如何測試隨機洗牌功能的質量，我不知道其底層實現？
我的具體問題
為了更具體地解決我的難題，我目前正在嘗試從這篇部落格文章中實現一個 64 位版本的置換算法。
TLDR：您可以使用雜湊函式（對於給定的二次冪大小的域是可逆的）來生成隨機排列，方法是將範圍四捨五入到下一個二次冪並排除生成的索引小於範圍。
一個hacky的解決方案
我想出了一個 hacky 解決方案，但我不確定是否有更好的解決方案以及如何計算此解決方案引入的偏差：
評估隨機排列時會想到的一件事是，如果我們對包含連續整數的數組進行洗牌，並且只使用第一個索引作為隨機生成的數字，現在可以使用像 PractRand 這樣的測試套件來測試隨機性。
但是，這種方法有一個明顯的問題，因為我們感興趣的是單個排列的相關性，而不是不同排列之間的相關性，因為例如在上述算法中，初始索引總是適當隨機的。
現在下一個想法是使用第一個
k索引作為隨機數，但這也有一個問題，因為一旦生成了一個數字，它就不能再次出現。這可以通過在數組中多次儲存連續整數來提升到一定程度。因此，每個整數
[0,n]都儲存m在數組中的時間，並且k洗牌的整數用於測試。隨著m獲得重複整數的偏差增加，獲得重複整數的偏差會下降，因此這是一個理論上可用的解決方案。雖然這將需要大量記憶體，但幸運的是我感興趣的算法一次生成一個隨機索引，因此可以通過使用
mod n生成的索引來非常有效地完成此操作。編輯：澄清我在較小範圍內談論的內容：假設我有一個包含
m零和一的數組m（所以n=1）。我現在打亂數組並將第一個k零和一個作為位寫入像 PractRand 這樣的測試套件，然後重複這個過程。對於一個非常大的m（例如2^50）和一個較小的k（例如2^8），重複的偏差應該很小以至於可以忽略不計。我不知道
k,n和m選擇什麼值以及相應的偏差是什麼。問題
- 在不知道函式的底層實現的情況下，除了隨機排列數組之外，還有其他方法可以測試函式嗎？
- 我提出的方法有什麼問題嗎？
- 如何計算我的方法對給定值 和 引入
k的n偏差m？
評估隨機排列時會想到的一件事是，如果我們對包含連續整數的數組進行洗牌，並且只使用第一個索引作為隨機生成的數字，現在可以使用測試套件（如
PractRand.不，你不能那樣做，但差不多。偽/真正隨機序列具有多個相同的值、重複和 +/- 數字執行。即使完全排列，您單獨的增量序列也很容易通過測試，甚至可能通過簡單的
ent.您通過推理測試 shuffle 算法。
- 從類似的東西
/dev/urandom或windows等價物生成一個大文件。- 按順序排列，上升或下降。
- 然後置換那個。
- 然後測試隨機性。
檢驗假設是，由於原始序列是密碼隨機的，並且具有正確的 $ \chi^2 $ 分配，適當的洗牌不會使情況變得更糟。它會將值分隔到隨機位置。所以標準的隨機性測試應該通過它。