在恆定空間中創建1..N的隨機排列

我期待枚舉數字1..N在固定空間中的隨機排列。這意味着我無法將所有數字存儲在列表中。原因是N可能非常大，超過可用內存。我仍然希望能夠一次一個地瀏覽這樣一個數字的排列，每次只訪問一次數字。在恆定空間中創建1..N的隨機排列

我知道這可以爲某個N來完成：許多隨機數生成周期通過他們的整個狀態空間隨機，而是完全。狀態大小爲32位的好隨機數發生器將發出數字0 ...（2^32）-1的置換。每一個數字只有一次。

我想挑電量爲任意數量在所有的，而不是被限制在例如2的冪。有沒有這樣的算法？

2012-04-07 usr

如何隨機應該是什麼？例如，枚舉是否可以從相同的狀態開始，並像「普通」隨機數生成器那樣生成相同的序列，或者每次都必須有所不同？ – gbulmer 2012-04-07 13:08:54

我剛剛發現這篇文章：https://en.wikipedia.org/wiki/Pseudorandom_permutation因此，使用該鍵映射到排列被稱爲「**僞隨機置換F **」的函數的過程，而問題是如何選擇/實現/使用實現這種功能的算法。文章還提到理想分組密碼和理想僞隨機置換之間的聯繫。 – 2014-12-13 21:05:12

略（非常）過時，但我對你的解決方案，不涉及「折騰的東西離開只是因爲我們沒有得到我們想要的」 ** ** IIF'N'是素數。我很猶豫要發佈它（因爲我仍然在根據這個概念開展CSRNG工作），但會作爲答案，但如果您仍然感興趣（以及上述條件匹配），我願意。 – 2017-02-19 05:22:11

最簡單的方法可能是隻創建一個全範圍的PRNG爲更大範圍的比你所關心的，當它產生比你想有一個較大的數目，只是把它扔掉，並得到下一個。

這幾乎是同一的變體的另一種可能性是使用線性反饋移位寄存器（LFSR）在第一位置，以產生數字。這有兩個好處：首先，LFSR可能比大多數PRNG快一點。其次，（我相信）設計一個LFSR更容易，它可以產生接近你想要的範圍的數字，並且仍然可以確保它循環遍歷（僞）隨機順序的範圍內的數字，而不需要重複。

沒有在細節上花了大量的時間，後面的LFSR算算已經相當深入的研究。生成一個遍歷其範圍內的所有數字而不重複的數據只需要選擇一組對應於不可約多項式的「抽頭」。如果您不想自己搜索，那麼可以很容易地找到幾乎任何合理大小的已知列表（例如，快速瀏覽，維基百科文章列出它們的大小最多爲19位）。

如果內存服務，至少有一個不可約多項式的可能位大小。這意味着在最糟糕的情況下，您可以創建一個發電機，其大小是您需要的範圍的兩倍，因此平均而言，您將大致丟棄您生成的每個其他數字。考慮到LFSR的速度，我想你可以做到這一點，仍然保持相當可接受的速度。

來源

2012-04-07 13:49:31

根據https://en.wikipedia.org/wiki/Maximum_length_sequence，LFSR總是將0映射到0，並且序列的最大可能長度爲2 ⁿ - 1其中n是寄存器的位數。因此，可能的排列次數限於（2 ⁿ-1）！最多。當一個隨機密鑰輸入到一個統一映射密鑰的函數中時，可實現最大的隨機性！（2 ⁿ）！可能的排列。 – 2014-12-13 20:17:32

重要的是要認識到，當使用具有硬編碼抽頭的lfsr時，順序是固定的，並且種子只選擇以固定順序開始和結束的位置。 – sh1 2017-09-14 23:29:09

一種方式做這將是

找到比N大的黃金p，最好不要大得多。
查找統一g模p的原根，即，一些1 < g < p使得g^k ≡ 1 (mod p)當且僅當是k的p-1的倍數。
轉到通過g^k (mod p)爲k = 1, 2, ...，忽略了比N較大的值。

對於每個素數p，有φ(p-1)統一原始根，所以它的工作原理。但是，它可能需要一段時間才能找到一個。一般來說，找到合適的素數要容易得多。

爲了找到一個原始根，我沒有什麼比反覆試驗更好，但是可以通過適當地選擇素數來提高快速查找的概率。

由於原始根的個數爲φ(p-1)，如果一個隨機地從1到p-1範圍選擇r，嘗試的預期數量，直到一個找到一個原始根是(p-1)/φ(p-1)，因此應該選擇p使得φ(p-1)相對大，這意味着p-1必須具有幾個不同的素因子（和優選地僅路數，除了因子2）。

不是隨機選擇，也可以按順序嘗試是否2, 3, 5, 6, 7, 10, ...是原始根，當然是跳過完美的力量（或者不是，它們通常很快被消除），這不應該影響大大需要的嘗試次數。

因此，它歸結爲檢查數x是否是一個原始根模p。如果p-1 = q^a * r^b * s^c * ...與不同的素數q, r, s, ...，x是一個原始根當且僅當

x^((p-1)/q) % p != 1 
x^((p-1)/r) % p != 1 
x^((p-1)/s) % p != 1 
...

因此，人們需要一種體面模冪運算（冪通過反覆平方很適合用於，通過在每個步驟中的模量減少）。並找到p-1的素因子分解的好方法。但是請注意，即使是天真的審判庭將只有O（√ P），而置換的產生是Θ（P），所以它不是最重要的因數分解是最佳的。

來源

2012-04-07 13:42:34

聽起來不錯。任何想法如何我可以輕鬆地獲得一個合適的素根？到目前爲止，我的數學還沒有完成任務。 – usr 2012-04-07 14:07:37

啊，那是棘手的部分。我知道沒有一個確保速度很快的好方法，但我可以提供一些方法來提高發現速度的可能性。我會編輯，給我幾分鐘（可能超過幾個）。 – 2012-04-07 14:16:00

對於素數p正好有島（P-1）不同的原始根，所以只是想選擇一個隨機一會的工夫，通過http://mathworld.wolfram.com/PrimitiveRoot.html – kilotaras 2012-04-07 14:29:22

另一種方法是使用分組密碼;詳情請參閱this blog post。

的博客文章鏈接，其中包含了一堆方案的紙張Ciphers with Arbitrary Finite Domains。

來源

2012-04-11 05:32:11

這將起作用。爲了生成一個27位的隨機數，我必須找到一些具有這種狀態大小的奇特密碼。或丟棄生成的密文的31/32。 – usr 2012-04-11 10:26:33

@usr我鏈接的文章介紹瞭如何做到這一點。您可以使用現有的密碼並減少其塊大小。 – 2012-04-11 23:45:17

雖然這個鏈接可能回答這個問題，但最好在這裏包含答案的基本部分，並提供供參考的鏈接。如果鏈接頁面更改，則僅鏈接答案可能會失效。 – ccjmne 2014-08-25 00:59:01

考慮的首要3.要充分表達所有可能的輸出，認爲它是這樣的...

bias + step mod prime

的bias只是一個偏移偏差。 step是一個累加器（如果它是1，例如，它將依次爲0, 1, 2，而2將導致0, 2, 4），並且prime是我們想要生成排列的素數。

例如。的0, 1, 2一個簡單的順序是......

0 + 0 mod 3 = 0 
0 + 1 mod 3 = 1 
0 + 2 mod 3 = 2

修改夫婦第二這些變量，我們將採取的1bias和2（只是爲了演示）step ...

1 + 2 mod 3 = 0 
1 + 4 mod 3 = 2 
1 + 6 mod 3 = 1

你會注意到我們製作了一個完全不同的序列。集合中沒有任何數字重複，並且所有數字都被表示（它是雙射的）。偏移量和偏差的每個獨特組合都會導致該組合中可能的排列組合prime!之一。在3一個prime的情況下，你會看到有6不同的可能permuations：

0,1,2 
0,2,1 
1,0,2 
1,2,0 
2,0,1 
2,1,0

如果你對變量的數學上面你不會認爲它會導致同樣的信息需求.. 。

1/3! = 1/6 = 1.66..

... ... VS

1/3 (bias) * 1/2 (step) => 1/6 = 1.66..

限制很簡單，bias必須在0..P-1和step必須在1..P-1（我一直在功能上剛剛被使用0..P-2和算術加1在我自己的工作中）。除此之外，它可以處理所有素數，不管它有多大，並且會排列所有可能的獨特集合，而不需要超過幾個整數的內存（每個技術要求比素數本身略小）。

注仔細，這種發電機並不意味着可用於生成集，是不是在數量上黃金。完全可以這樣做，但不建議出於安全敏感的目的，因爲它會引入定時攻擊。

也就是說，如果你想用這種方法來產生一個不是素數的序列，你有兩種選擇。

首先（也是最簡單/最便宜的），選擇比您要查找的設置大小更大的素數，讓您的發生器簡單地丟棄不屬於的任何東西。再次，危險，這是一個非常糟糕的主意，如果這是一個安全敏感的應用程序。

二（迄今爲止最複雜，成本高），可以識別所有的數字都是由素數的和創建多個生成器，然後生產出的產品在集合中的每個元素。換句話說，n的6將涉及所有可能的匹配6（在這種情況下，2和3）的主要生成器，按順序相乘。這既昂貴（雖然在數學上更加優雅），並且還引入了定時攻擊，所以它甚至不被推薦。

最後，如果你需要一個發電機bias和或step ......爲什麼你不使用另一個同一個家庭:)。突然間，你非常接近創建真正的簡單隨機樣本（這通常不容易）。

來源

2017-03-26 03:28:55

我喜歡這個方法，因爲它很容易實現。但是在這方面沒有硬安全，對吧？只是澄清一下，這個問題並不需要安全。 – usr 2017-04-02 16:57:09

輸入信息=置換信息似乎不能推廣到超過3個元素的置換;例如對於n = 5,1/5（偏差）* 1/4（步長）= 1/20！= 1/5！ = 1/120。我不認爲你可以使用兩個不大於n的數字來指定n> 3個元素的置換。 – Thelema 2017-07-17 21:31:44

LCGs（x=(x*m+c)%b風格生成器）的根本弱點在這裏很有用。

如果適當地形成在發電機然後x%f也是所有值的重複序列低於f（提供f如果b一個因子）。

由於b通常是2的乘方，這意味着您可以採用32位發生器並通過屏蔽最高位將其減少到n位發生器，並且它將具有相同的全範圍屬性。

這意味着您可以通過選擇合適的掩碼將丟棄值的數量減少到少於N.

不幸的是LCG是對完全按照上面給出的相同的原因不良產生。

而且，這種具有完全按照我在@ JerryCoffin的回答評論指出相同的弱點。它將始終產生相同的序列，並且種子控制的唯一內容就是以該序列開始的位置。

來源

2017-09-15 17:23:12 sh1

下面是一些SageMath應該產生一個隨機排列的方式Daniel Fischer suggested：

def random_safe_prime(lbound): 
    while True: 
     q = random_prime(lbound, lbound=lbound // 2) 
     p = 2 * q + 1 
     if is_prime(p): 
      return p, q 


def random_permutation(n): 
    p, q = random_safe_prime(n + 2) 

    while True: 
     r = randint(2, p - 1) 
     if pow(r, 2, p) != 1 and pow(r, q, p) != 1: 
      i = 1 
      while True: 
       x = pow(r, i, p) 
       if x == 1: 
        return 

       if 0 <= x - 2 < n: 
        yield x - 2 

       i += 1

來源

2018-03-09 13:18:27 Tyilo

在恆定空間中創建1..N的隨機排列

回答

相關問題