Permutation
我們如何在已知的偶數排列中找到最後兩個對應關係？
一個秘密的偶數排列 $ P $ 的非負整數集合小於 $ n $ 被選中。那可能是帶有隨機密鑰的Feisltel 密碼。
我們依次給出 $ P(x) $ 為了 $ x $ 從 $ 0 $ 到 $ n-3 $ ，並且必須輸出有序對 $ (P(n-2),P(n-1)) $ .
什麼是有效的線上算法？所需記憶體的實際最小值是多少？
如果我們被允許怎麼辦 $ n-2 $ 查詢給出 $ P(x_i) $ 對於任何 $ x_i $ 我們反複決定，並且必須輸出 $ (x_{n-2},P(x_{n-2}),x_{n-1},P(x_{n-1})) $ 在哪裡 $ x_{n-2} $ 和 $ x_{n-1} $ 沒有被查詢？
如果允許我們免費重複之前的查詢怎麼辦？
所有排列都有一個循環分解，您可以從中立即讀出您的 $ P(n-2) $ 和 $ P(n-1) $ . 有一些簡單的算法可以在其中執行 $ O(n) $ 時間和 $ O(n) $ 空間（反轉排列），或 $ O(n^2) $ 時間和 $ O(1) $ 空間（通過反复詢問每個人來向後走）。
您可以調整反轉排列算法以使每個元素僅使用 1 位，但這仍然是 $ O(n) $ 空間。或者，如果你有一個稀疏排列的有效表示，那麼你可以替換 $ n $ 通過實際移動的元素數量。