如何將一組連續整數轉換為一組唯一隨機數？
我有一組連續且非重複的整數，我想將其轉換為一組非重複的隨機整數。
我想要實現的是這個 - 我有一個序列號列表，如下所示
[1, 2, 3, 4, 5, 6, 7, 8, 9]這個列表實際上會很大，例如 1 億
我想多次打亂這個列表，以便重新排列列表中的數字。每次洗牌都應該給我一個新的序列，如果我在每次洗牌後在列表中的特定位置選擇一個數字，我永遠不會得到重複。
例如，如果上面的列表被洗牌 3 次，我在每次洗牌後得到以下三個序列
shuffle 1 --> [9, 3, 4, 1, 7, 2, 6, 5, 8] shuffle 2 --> [8, 2, 7, 5, 4, 6, 3, 9, 1] shuffle 3 --> [1, 9, 6, 7, 5, 3, 4, 8, 2]在上面的列表中，如果你在任何位置選擇一個數字，比如 2，從所有集合中，你永遠不會得到任何重複。如果您從第一個序列中選擇位置 2 並從第三組中選擇位置 5，您將得到一個副本，這很好。
出於某種原因，我覺得這種洗牌應該有一個加密函式，我可以將輸入序列傳遞給它，然後如上所述得到一個洗牌後的序列。有沒有？我查看了LFSR，但不確定該解決方案在這種情況下是否有效。
讓 $ P $ 是任意隨機固定排列 $ n $ 元素。每個所需的 shuffle 都可以從前面生成，如下所示：
- 申請 $ P $ 到前一個洗牌（或初始集合/向量，第一次）；
- 將結果向左旋轉一位；
- 申請 $ P^{-1} $ 到結果。
這將通過*“如果我在每次洗牌後在列表中的特定位置選擇一個數字，我永遠不應該得到重複*”來詢問屬性。證明：在順序應用 shuffle 時，下一個應用 $ P $ 取消之前的申請 $ P^{-1} $ . 因此，旋轉將對前一個旋轉的結果進行操作，因此該屬性在旋轉的輸出處得到滿足。由此可見，申請後滿足屬性 $ P^{-1} $ ，因此在輸出端。
我們可以迭代這個 $ n-1 $ 次（如果我們再做一次，我們就會回到原來的狀態，因此會得到一些清晰的順序，因此在上下文中可以很容易地和幾乎確定地與所需的*“隨機整數”區分開來）。*
我們可以使用Fisher-Yates shuffle來生成 $ P $ . 或者，如果由於大小而將其保存在記憶體中是一個問題，我們可以使用密碼來實現 $ P $ , 及其反面; 這是Format Preserving Encryption的標準技巧。
任何孤立的 shuffle 都無法與隨機 shuffle 區分開來，但即使是生成的前兩個 shuffle 也可以與具有所需屬性的隨機 shuffle 區分開來（如果沒有明確禁止，這可能是不可取的）。
如果我們取消對相同操作進行迭代以從一個 shuffle 到下一個 shuffle 的要求（我們被告知我們可以），我們可以做得更好：選擇三個任意隨機排列 $ P $ , $ Q $ , $ R $ 的 $ n $ 元素，並得到 $ (j+1)^\text{th} $ 隨機播放
- 申請 $ P $ 到初始狀態
- 旋轉結果 $ Q(j) $ 左邊的時間，在哪裡 $ Q(j) $ 是個 $ (j+1)^\text{th} $ 通過應用獲得的向量的元素 $ Q $ 到第一個向量 $ n $ 非負整數；或者，另外說， $ Q(j) $ 是一個整數 $ q_j $ 和 $ 0\le q_j<n $ , 這樣 $ 0\le i<j<n\implies q_i\ne q_j $ .
- 申請 $ R $ 到結果。
這一次，我們可以得到 $ n $ 單獨隨機的洗牌，這顯然是最大的。同樣，Fisher-Yates 或 FPE 可用於實現 $ P $ , $ Q $ 和 $ R $ . 即使知道初始洗牌和任何兩個生成的洗牌的等級，我也模糊地推測（沒有證據）它們與滿足所要求屬性的兩個隨機洗牌沒有區別。通過計數參數，三個生成的 shuffle 是可區分的，至少對於一個無界的對手來說是可區分的；因此，我們遠未產生盡可能好的隨機性。
我在那裡用更多的學術術語提出了這個問題。
這是第二種方法的 Java 範常式式碼。MyCipher類實現了大小元素的偽隨機排列，使用循環（可以說是最簡單的高效 FPE 技術）和基本的迭代分組密碼。MyShuffledArray類是我建議的技術的直接實現。該程式碼可用於大參數，並使用常量記憶體。
import java.util.Random; import java.security.SecureRandom; public class MyShuffledArrayDemo { // MyCipher implement a PRP of size elements static class MyCipher { private static final int R = 40; // number of rounds private final int size; // size of PRP private final int mask; // bit mask for block // 0 < size <= mask+1 and mask+1 is a power of 2 private final int rish; // right shift count private final int[] rk = new int[R]; // rk for each round // Constructor from rng source private MyCipher(int size, Random rng) { assert size>0 : "MyCipher.size must be positive"; int i,j; // find block cipher width j in bits; and mask for (j = 3, i = 8; j<31 && i<size; ++j) i += i; this.size = size; this.mask = i-1; // one less than a power of two this.rish = j*3/7; // shift count, at least 1 i = R; do rk[--i] = rng.nextInt(); while (i!=0); } // Implement PRP, using a basic iterated block cipher and cycling. // Input and output are a non-negative integer less than size. private int Perm(int x) { assert x>=0 && x<this.size : "bad input to MyCipher.encrypt"; do { // cycling loop; executed on average less than twice when size>4 int r = R; do {// Round loop; each losslessly transforms x by // - multiplying by 0xADB modulo a power of 2 // - adding a round key // - XORing x with a right-shifted version // Here, x<= mask and mask+1 is a power of 2 x = (x*0xADB+this.rk[--r]) & this.mask; x ^= x>>>this.rish; } while (r!=0); } while (x>=this.size); return x; } } // class MyCipher // MyShuffledArray implement a virtual square array where each line and column appears to be a random permutation static class MyShuffledArray { private final int size; // dimension private MyCipher P,Q,R; // Constructor from rng source private MyShuffledArray(int size, Random rng) { assert size>0 && size<=0x40000000: "MyShuffledArray.size must be positive and at most 1073741824"; this.size = size; P = new MyCipher(size, rng); Q = new MyCipher(size, rng); R = new MyCipher(size, rng); } // Implement the virtual array private int Get(int col, int lin) { return R.Perm((P.Perm(col)+Q.Perm(lin))%this.size); } } // class MyShuffledArray // Example use final static int START_OF_RANGE = 1; final static int END_OF_RANGE = 9; final static int NUMBER_OF_LISTS = 3; final static int size = END_OF_RANGE - START_OF_RANGE + 1; public static void main(String[] args) { MyShuffledArray myShuffledArray = new MyShuffledArray(size, new SecureRandom()); for (int j = 0; j <NUMBER_OF_LISTS; j++) { for (int i = 0; i <size; i++) System.out.print(String.format(i==0?"[%d":", %d", myShuffledArray.Get(i,j) + START_OF_RANGE)); System.out.println("]"); } } }這個答案表明我們正在生成一個latin square。這是一個文獻調查。
讓我們改寫你想要的。您需要一組具有兩個屬性的序列。
- 對於集合中的任何元素，該序列包含的每個可能元素不超過一個。
2）在集合的任意兩個元素a和b中，序列a的第n個元素不等於序列b的第n個元素。
與其想像一組序列，不如想像一個方陣。在任何給定的列中，您都希望沒有元素出現兩次。在任何行中，您也希望沒有元素出現兩次。（有點像數獨表。）換句話說，任何給定的行都是一個排列，任何給定的列都是一個排列。因此，如果您有一個 N x N 表，其值為 1 到 N，您可以通過查看第 n 行數字來提取第 n 個混洗序列。
您可以將偽隨機函式應用於一系列唯一數字。如果該函式是單射的，那麼根據定義，該函式的輸出序列將不會有重複。為簡單起見，假設您有一大堆可用的雙射偽隨機函式。雙射函式是單射的，因此對於具有域和余域的整數 1 到 n 的任何雙射函式 F，序列
$$ F(1), F(2), F(3), … F(N) $$是值 1 到 N 的排列。 您可以應用另一個雙射函式來排列您的第一個排列，從而再次產生一個排列。這是因為雙射函式的組合是雙射函式。這就是 Even-Mansour 加密的工作原理。XOR 和模加法之類的簡單事物是雙射的，但並不隨機。XOR-Encrypt-XOR 操作鏈用於從非密鑰排列創建塊密碼或從普通塊密碼創建可調整的塊密碼。
EM 密碼的子密鑰大小與塊大小相同。由於子鍵在輸入階段由 xor 組合，這使得輸入和第一個子鍵在某種意義上是可互換的，因為 xor 是可交換操作。
因此，假設我們不關心我們的 shuffle 函式是否在密碼學上是安全的，而不是使用這些子密鑰來創建秘密排列。然後讓我們使用一個兩階段的 EM 密碼，前兩個子密鑰是我們的 x 和 y 值，用作調整值，以及一個常數，比如零，用於密碼輸入。 $ F(x, y) = P(P(x \oplus 0) \oplus y) \oplus constk $ . 如果我們讓 x 保持不變，我們可以證明 $ F_x(y) $ 是雙射的。如果我們讓 y 保持不變並改變 x，我們可以類似地證明 $ F_y(x) $ 是雙射的。
這是一個顯示相同想法的pastebin 。我使用查找表來創建小的雙射函式。兩個排列輪足以獲得您想要的唯一性屬性，但結果看起來並不隨機。我添加了第三輪查找表來“重新洗牌”作為前兩輪結果的非隨機排列。該展示在密碼學上並不安全，但如果這是基於真正的 EM 密碼，並且在算法的末尾添加了幾輪額外的密鑰，那麼它可能是安全的。我使用模運算而不是 xor，因為它具有相同的屬性，但也適用於非 2 的冪。
這種方法的有趣之處在於，您可以在 O(1) 時間內訪問第 y 次隨機播放的第 x 個元素。不利的一面是，無論您選擇什麼域大小，您都需要一個雙射偽隨機函式。如果大小是 2 的冪，或者如果大小小到可以使用查找表來實現，那麼選擇一個易於實現的函式是相當容易的。對於未知的任意大小，您需要為該域大小選擇一個好的雙射函式。如果您選擇了比實際需要更大的塊大小，則可以將矩陣截斷為前 n 行和前 n 列。子矩陣中沒有表示共域的元素，也不是每一行都包含相同的元素。（每一行都是共域的一個隨機子集。）
儘管您在加密方面提出了要求，但我希望您不希望實現加密安全的東西。如果您不容易想到生成這些序列的加密安全方法，那麼您就沒有必要的知識來知道您是否正確實施了它。如果您需要一種不需要安全性的應用程序的專用算法，例如影片遊戲、模擬或奇怪的非密碼雜湊函式，那麼您可以使用我的展示來建構一些東西。對於非加密應用程序，我建議使用 Murmur Hash 3 的 64 位變體的終結常式作為您的公共知識偽隨機排列而不是查找表。（然後您可以使用 xor 代替模加法。）