algorithm - 反向确定性随机播放 -> 派生 key

Question

我正在寻找一种可以从已经发生的洗牌过程中派生出 key 的算法。

假设我们有被打乱的字符串“Hello”:

"hello" -> "loelh"

现在我想从中导出一个 key k，我可以用它来撤销洗牌。因此，如果我们使用 k 作为确定性改组算法的输入参数，例如 Fisher-Yates并再次洗牌 "loelh"，我们将恢复初始字符串 "hello"。

我的意思不是简单地使用一个相同的确定性洗牌算法来洗牌和去洗牌。那是因为在我的例子中，第一个字符串在经典意义上不会被真正洗牌。实际上会有两组刚刚给出的数据(字节或位数组)，我们想从第一组到第二组只用一个之前导出的 key 。

我希望清楚我想要实现的目标，我将不胜感激所有提示或建议的解决方案。

问候，优点

更新:

另一个尝试:基本上，人们也可以将其称为一堆数据的确定性转换，例如一个字节数组，但我会坚持使用“hello”字符串示例。

假设我们有一个转换算法 transform(data, "unknown seed") 其中 data 是 "hello"和 unknown seed 是我们正在寻找的。 transform 的结果是“loelh”。我们正在寻找可以用来逆转这一过程的“未知种子”。在“未知种子”生成时，输入数据和结果当然都是已知的。

稍后我想使用“未知种子”(应该已经知道 ;-) 再次获取原始字符串:所以这个 transform("loelh", seed) 应该导致再次 “你好”。

因此您也可以将其视为方程式的形式，例如 data*["unknown value"]=resultdata 我们正试图找到未知值(运算符 * 可以是任何类型的操作)。

Answer 1

首先，让我们把问题大大简化。我们假设您始终在排列“abcde”，而不是排列“hello”，因为这样会更容易理解。

随机播放是排列的随机生成。洗牌如何产生排列无关紧要；洗牌产生排列，这就是我们需要知道的。

让我们将排列表示为包含数字 1 到 5 的字符串。假设随机播放产生排列“21453”。也就是说，我们取第一个字母并将其放在位置 2:_a___。我们取第二个字母并将其放在位置 1，ba___。我们取第 3 个字母并将其放在位置 5:ab__c。我们把第四个字母放在位置 3，bad_c，我们把第五个字母放在位置 4，badec。

现在您希望推断出一个“ key ”，它允许您“取消排列”排列。好吧，这只是另一种排列，称为逆排列。要计算“21453”的逆排列，请执行以下操作:

• 找到“1”。它在第 2 个位置。
• 找到“2”。它在第一位。
• 找到“3”。它排在第 5 位。
• 找到“4”。它排在第三位。
• 找到“5”。它排在第 4 位。

现在阅读第二列； “21453”的逆排列是“21534”。我们正在取消排列“badec”。我们把第一个字母放在位置 2:_b___。我们将第二个字母放在位置 1:ab___。我们将第三个字母放在位置 4:ab_d_。我们将第四个字母放在位置 5:ab_de。并且我们将第五个字母放在位置 3:abcde。