时间戳

首页 > 解决方案 > 条件置换后如何将数组恢复为原始形式

c# - 条件置换后如何将数组恢复为原始形式

问题描述

我的代码：

var unpermuted = new byte[]{137, 208, 135, 4, 191, 255, 132, 99, 85, 54, 58, 137, 208, 37, 151, 30};
var longKey = new byte[] {75, 79, 84, 69, 197, 129, 75, 65, 74, 65, 75, 75, 79, 84, 69, 197, 129, 75, 65, 74, 65};

    var permuted = (byte[])unpermuted.Clone();

    for(var i = 0; i < permuted.Length;i++)
    {
        if (i > 1 && (permuted[i] < longKey[i]))
        {
            var swapCont = permuted[i - 1];
            permuted[i - 1] = permuted[i];
            permuted[i] = swapCont;
        }
    }

    printArr(unpermuted);
    Console.WriteLine();
    printArr(permuted);

    // How do I reverse permuted array to unpermuted?
    Console.WriteLine();
    printArr(permuted);
}


public static void printArr(byte[] arr)
{
    for(var i = 0; i < arr.Length;i++)
    {
        Console.Write(arr[i]);
        Console.Write(" ");
    }
}

我有 unpermute 数组，进行深拷贝，然后，如果keyValue高于 value，我与前一个元素交换。

问题是：如何将置换数组恢复为只有LongKey Array 和 Permuted 数组的未置换形式？

标签： c#.netalgorithm

解决方案

鉴于您拥有的信息，不可能“取消排列”数组。

想象一下，您有以下内容：

longkey = [1,2,3,9,5]
array   = [3,4,9,5,6]

运行您的代码，结果将是[3,4,5,9,6].

但是如果原始数组是[3,4,5,9,6]，结果是一样的。

如您所见，原始数组有多个排列可以提供相同的输出。结果和longkey数组中没有足够的信息来告诉您原始数组是什么。

通常，如果您有一个 3 项序列，其中满足以下条件，则不可能可靠地反转操作。

longkey = [b, c, d]
array   = [x, y, z]

在哪里：

b <= x, b <= y
c <  x, c > y
d <= z

例如：

longkey = [...,3,9,5,...]
array   = [...,9,5,6,...]

这里的关键是 9 永远不能和它左边的东西交换，而 6 永远不会和 5 交换。所以 5 和 9 不能移动，除非互相交换位置。如果原来的顺序是[9,5,6]，最后的顺序是[5,9,6]。如果原来的顺序是[5,9,6]，结果又是[5,9,6]。

推荐阅读