我要问的是一个简单的问题:如何在一系列数字(有重复)中找到一个(且只有一个)复杂度最低的排列?
假设我们有序列:1 1 2 3 4
。然后我们置换 2 和 3,所以我们有:1 1 3 2 4
。我怎样才能发现 2 和 3 已被置换?最糟糕的解决方案是生成所有可能性并将每个可能性与原始排列序列进行比较,但我需要一些快速的东西......
感谢您的回答。
最佳答案
这样做的问题是您的问题会有多种解决方案,而没有一些限制,例如按顺序找到顺序。
我要看的是首先测试序列中是否仍然存在相同的值,如果是这样,则逐个检查直到发现不匹配,然后找到另一个值的第一次出现位置并标记那作为排列。现在继续搜索下一个修改等等……
如果您只想知道它发生了多少变化,我会查看 levenshtein 算法。该算法的基础甚至可以为您提供您自己的自定义算法所需的内容或启发其他方法。
这很快,但它不会告诉您哪些项目发生了变化。
我所知道的唯一完整解决方案是在每次更改发生时记录下来,这样您只需查看更改历史即可知道完美的答案。
关于algorithm - 一种查找序列排列的算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13267225/