給定一個打亂的列表和種子，如何取回原始列表？
假設我有一個在 Python 中使用
random.shuffle(). 使用種子隨機數生成器執行改組。有沒有辦法可以取回原始列表，即取消隨機列表？例如 list1=$$ 1,4,2,5 $$在隨機播種和改組 list2=$$ 5,2,1,4 $$如果我們只知道 list2 和種子值，有沒有辦法找回 list1
是的。在整個過程中，我將做出假設（似乎是這種情況）以
random.shuffle()僅取決於以下方式排列列表：
- 使用的種子
- 被洗牌的列表的長度
這就是說，對於一個固定的種子和固定長度的列表（比如說 $ n $ )，
random.shuffle()選擇一些排列 $ \sigma\in S_n $ ，然後發送列表：$$ [a_1,a_2,\dots, a_n] \mapsto [a_{\sigma(1)}, a_{\sigma(2)},\dots, a_{\sigma(n)}] $$
例如，如果 $ n = 4 $ ， 和 $ \sigma $ 發送 $ 1 \to 2 $ , $ 2\to 4 $ , $ 3\to 3 $ ， 和 $ 4\to 1 $ ，然後對於任何初始列表 $ [a_1, a_2, a_3, a_4] $ ,
random.shuffle()將其置換為 $ [a_{\sigma(1)}, a_{\sigma(2)},\dots, a_{\sigma(n)}] = [a_2, a_4, a_3, a_1] $ .讓 $ ls = [a_1,\dots, a_n] $ 成為您關心的（初始）列表，並讓 $ \sigma(ls) = [a_{\sigma(1)},\dots, a_{\sigma(n)}] $ 是它的洗牌版本。我們可以通過使用我們先前關於
random.shuffle()“找到”排列的假設來“打亂”它 $ \sigma $ 那是以前用過的。特別是，如果我們將種子設置為相同，並使用列表 $ \mathsf{perm} = [b_1,\dots, b_n] $ 相同的長度，我們將擁有：$$ \sigma(\mathsf{perm}) = [b_{\sigma(1)}, b_{\sigma(2)},\dots, b_{\sigma(n)}] $$ 那麼，如果我們有一些恢復的方法 $ \sigma(\mathsf{perm})\mapsto \mathsf{perm} $ ，我們可以簡單地“做這些相同的步驟” $ \sigma(ls) $ 恢復 $ ls $ .
正因為如此，一個特別容易的選擇 $ \mathsf{perm} $ 合作是 $ \mathsf{perm}= [1,2,\dots,n] $ （我們可以通過排序返回它）。請注意 $ b_i = i $ ， 所以 $ \sigma(\mathsf{perm}) = [\sigma(1),\dots, \sigma(n)] $ .
一種特別簡單的“排序”方法 $ \sigma(\mathsf{perm}) $ , 但將相同的轉置序列應用於 $ \sigma(ls) $ ”是通過創建“壓縮列表”：
$$ \mathsf{zipped_list} = [(\sigma(ls)[0], \sigma(\mathsf{perm})[0]), (\sigma(ls)[1], \sigma(\mathsf{perm})[1]), \dots, (\sigma(ls)[n], \sigma(\mathsf{perm})[n])] $$
請注意，每個元組的每個部分都以完全相同的方式排列！所以我們可以將其視為： $$ \sigma([(a_1, 1), (a_2, 2), \dots, (a_n, n)]) $$ 即我們的初始列表，以及列表 $ [1,2,\dots,n] $ ,對它們都應用相同的排列。然後我們可以通過基於每個元組的第二個組件對這個更大的列表進行排序來*刪除這個排列。*這將返回列表 $ \sigma([1,2,\dots,n]) $ 至 $ [1,2,\dots,n] $ ，因此將返回 $ \sigma([a_1,\dots,a_n]) $ 至 $ [a_1,\dots, a_n] $ 以及（作為相同的移動序列，“取消” $ \sigma $ , 正在應用於每個列表）。
如果對正在發生的事情的理論描述仍然不清楚，下面的 python3 程式碼應該證明這是有效的。我還把它上傳到這裡的線上翻譯。
import random def shuffle_under_seed(ls, seed): # Shuffle the list ls using the seed `seed` random.seed(seed) random.shuffle(ls) return ls def unshuffle_list(shuffled_ls, seed): n = len(shuffled_ls) # Perm is [1, 2, ..., n] perm = [i for i in range(1, n + 1)] # Apply sigma to perm shuffled_perm = shuffle_under_seed(perm, seed) # Zip and unshuffle zipped_ls = list(zip(shuffled_ls, shuffled_perm)) ls.sort(key=lambda x: x[1]) return [a for (a, b) in ls]
ls對於任何 list和任何選擇seedthat ，這些都應該滿足，unshuffle_ls(shuffled_under_seed(ls, seed), seed) == ls您可以通過實驗驗證。