algorithm - 一种寻找序列排列的算法

Question

我要问一个简单的问题：如何在具有最低复杂性的数字序列（有重复）中找到一个（并且只有一个）排列？

假设我们有序列：1 1 2 3 4。然后我们置换 2 和 3，所以我们有：1 1 3 2 4。我怎样才能发现 2 和 3 已被置换？最糟糕的解决方案是生成所有可能性并将每个可能性与原始排列序列进行比较，但我需要一些快速的东西......

谢谢您的回答。

Answer 1

这样做的问题是，您的问题将有多种解决方案，而没有一些限制，例如顺序找到顺序。

我要看的是首先测试序列中是否仍然存在相同的值，如果是这样，只需一步一步完成，直到找到不匹配，然后找到另一个值的第一次出现的位置并将其标记为排列。现在继续寻找下一个修改等等……

如果您只想知道它发生了多大变化，我会看看 levenshtein 算法。该算法的基础甚至可以为您提供自定义算法所需的内容或启发其他方法。

这很快，但它不会告诉您哪些项目已更改。

我所知道的唯一完整的解决方案是记录每个更改，这样您就可以查看更改的历史以了解完美的答案。

Answer 2

function findswaps:
    linkedlist old <- store old string in linkedlist
    linkedlist new <- store new string in linkedlist

    compare elements one by one:
        if same
             next iteration until exhausted
        else
             remember old item
             iterate through future `new` elements one by one:
                 if old item is found
                     report its position in new list
                 else
                     error

我的谦虚尝试如果有错请纠正我，以便我可以提供更好的帮助。我猜数据是无序的，所以它不能比线性快吗？

Answer 3

如果原始数组和派生数组之间只有 1 次交换，您可以在 O(n) 处尝试这样的操作，数组长度为 n：

int count = 0;
int[] mismatches;

foreach index in array {
    if original[index] != derived[index] {
        if count == 2 {
            fail
        }
        mismatches[count++] = index;
    }
}

if count == 2 and
   original[mismatches[0]] == derived[mismatches[1]] and
       original[mismatches[1]] == derived[mismatches[0]] {

    succeed
}

fail

请注意，当阵列之间没有交换任何内容时，这会报告失败。