使用密钥可逆洗牌算法 [英] Reversible shuffle algorithm using a key

问题描述

我将如何在C＃中，它使用一键洗牌，并可以扭转到原来的状态，codeA可逆的洗牌算法？

How would I code a reversible shuffle algorithm in C# which uses a key to shuffle and can be reversed to the original state?

例如，我有一个字符串：世界，你好，我怎么能打乱它，这样以后我可能是能够扭转洗牌字符串返回到世界，你好。

For instance, I have a string: "Hello world", how can I shuffle it so that later I could be able to reverse the shuffled string back to "Hello world".

推荐答案

看费雪耶茨洗牌< /一>一种方式重排基于一个密钥串。饲料主要作为种子成PRNG，用它来生成用于洗牌的随机数。

Look at Fisher-Yates shuffle for a way to permute the string based on a key. Feed the key as the seed into a PRNG, use that to generate the random numbers used by the shuffle.

现在，如何扭转过程中？费雪耶茨的作品通过交换某些元素对。因此，要扭转过程中，你可以在同一个键送入相同的PRNG，再通过费雪耶茨算法的，如果的你洗牌数组的字符串的大小运行。但实际上，你不要动任何东西，只是记录，将在每一个阶段被交换的元素的索引。

Now, how to reverse the process? Fisher-Yates works by swapping certain pairs of elements. So to reverse the process you can feed the same key into the same PRNG, then run through the Fisher-Yates algorithm as if you were shuffling an array the size of your string. But actually you don't move anything, just record the indexes of the elements that would be swapped at each stage.

一旦你做到了这一点，通过你的清单上运行的掉期的反的，把它们应用到你的洗牌字符串。其结果是原始字符串。

Once you've done this, run through your list of swaps in reverse, applying them to your shuffled string. The result is the original string.

因此​​，举例来说，假设我们拖着使用下面的互换字符串hello（我没有用一个PRNG在这里，我滚骰子，而是一个PRNG的一点是它给你相同的数字序列给予相同的种子）：

So for example, suppose we've shuffled the string "hello" using the following swaps (I haven't used a PRNG here, I rolled dice, but the point about a PRNG is it gives you the same sequence of numbers given the same seed):

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

因此​​，洗牌字符串为loelh。

So, the shuffled string is "loelh".

要混洗还原，我产生了同系列的随机数，0，3，1，0，然后申请以相反的顺序互换：

To deshuffle, I generate the same series of "random" numbers, 0, 3, 1, 0. Then apply the swaps in reverse order:

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

成功！

本课程的缺点是，它使用了大量的内存用于混洗还原：索引的数组，只要你原来的字符数组。因此，对于真正庞大的阵列，你可能想选择一个PRNG（或反正一个序列生成功能），可以加强向前或向后，而无需存储所有的输出。这排除了基于散列的加密安全的PRNG，但个LFSR是可逆的。

The downside of this of course is that it uses a lot of memory for the deshuffle: an array of indexes as long as your original array of chars. So for truly huge arrays, you might want to choose a PRNG (or anyway a sequence-generation function) that can be stepped either forwards or backwards without having to store all the output. This rules out hash-based cryptographically secure PRNGs, but LFSRs are reversible.

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

Btw, why do you want to do this?

这篇关于使用密钥可逆洗牌算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！