找到最接近预期列表的列表的最佳方法是什么？

Question

我目前正在开发一个程序，尝试通过实验得出元素的排序，然后与给定的排序进行比较。例如：

实验：A、C、B、F、E、D 给定：A、B、C、D、E、F

最后，我试图找到一些指标，通过它我可以衡量我的实验顺序与给定顺序的接近程度。我知道所有相同的元素都会出现在两者中。正确位置的元素数除以列表中的元素总数是我能做的最好的吗？谢谢！

Answer 1

我认为这在很大程度上取决于您如何定义两个序列之间的相似性。我先给大家提个思路，然后定义对应的距离函数。

1. 正确的位置很重要：在这种情况下，您只需计算正确定位的元素的数量（正如您在问题中提出的那样）
2. 与所需位置的差异很重要：您可以总结每个字符在实验中的位置与给定序列中的位置的差异
3. 元素之间的排序很重要：在这里你可以计算出有多少对元素是正确的顺序（类似于Kendall rank correlation). Beside this one there are a couple more rank correlation measures。
4. 将一个列表转换为另一个列表的成本：在这种情况下，您必须计算从一个列表转换为另一个列表的最小交换次数。如果您还关心元素与所需位置的距离，则只能允许交换相邻元素。计算这个有点复杂，但这 geeksforgeeks 可能会有所帮助。

如果您希望距离介于 0 和 1 之间，则必须对结果进行归一化。我相信还有更多，这些只是我从头顶想到的。