c# - 使用 key 的可逆洗牌算法

Question

我如何在 C# 中编写可逆洗牌算法，该算法使用 key 进行洗牌并可以逆转为原始状态？

例如，我有一个字符串:“Hello world”，我该如何打乱它以便稍后我能够将打乱的字符串反转回“Hello world”。

Answer 1

看Fisher-Yates shuffle一种基于键置换字符串的方法。将 key 作为种子输入 PRNG，使用它来生成随机数。

现在，如何逆转这个过程？ Fisher-Yates 通过交换某些元素对来工作。因此，要反转该过程，您可以将相同的 key 输入相同的 PRNG，然后运行 ​​Fisher-Yates 算法，就好像您正在对字符串大小的数组进行洗牌。但实际上你并没有移动任何东西，只是记录了每个阶段要交换的元素的索引。

完成此操作后，反向遍历交换列表，将它们应用到打乱后的字符串。结果是原始字符串。

例如，假设我们使用以下交换对字符串“hello”进行了洗牌(我在这里没有使用 PRNG，我掷了骰子，但关于 PRNG 的要点是它给你相同的数字序列给出相同的种子):

(4,0): "hello" -> "oellh"
(3,3): "oellh" -> "oellh"
(2,1): "oellh" -> "olelh"
(1,0): "olelh" -> "loelh"

所以，打乱后的字符串是“loelh”。

为了洗牌，我生成了相同系列的“随机”数字 0、3、1、0。然后以相反的顺序应用交换:

(1,0): "loelh" -> "olelh"
(2,1): "olelh" -> "oellh"
(3,3): "oellh" -> "oellh"
(4,0): "oellh" -> "hello"

成功!

当然，这样做的缺点是它会使用大量内存来进行洗牌:索引数组与原始字符数组一样长。因此，对于真正庞大的数组，您可能希望选择一个可以向前或向后步进而无需存储所有输出的 PRNG(或者无论如何是一个序列生成函数)。这排除了基于散列的加密安全 PRNG，但 LFSR 是可逆的。

顺便说一句，你为什么要这样做？