评估数组单调性的算法(即判断数组的"排序性")

Question

---

编辑:哇,很多很棒的回复.是的,我使用它作为一个适应度函数来判断遗传算法执行的排序质量.因此,评估成本很重要(即,必须快速,最好O(n).)

---

作为我正在使用的AI应用程序的一部分,我希望能够根据其单调性(也就是其"排序性")对整数的候选数组进行评级.目前,我正在使用一种计算最长排序运行的启发式算法,然后将其除以数组的长度:

public double monotonicity(int[] array) {
    if (array.length == 0) return 1d;

    int longestRun = longestSortedRun(array);
    return (double) longestRun / (double) array.length;
}

public int longestSortedRun(int[] array) {

    if (array.length == 0) return 0;

    int longestRun = 1;
    int currentRun = 1;

    for (int i = 1; i < array.length; i++) {
        if (array[i] >= array[i - 1]) {
            currentRun++;
        } else {
            currentRun = 1;
        }

        if (currentRun > longestRun) longestRun = currentRun;
    }

    return longestRun;
}

这是一个良好的开端,但它没有考虑到可能存在分类子序列的"块"的可能性.例如:

{ 4, 5, 6, 0, 1, 2, 3, 7, 8, 9}

该数组被划分为三个排序的子序列.我的算法将它评定为只有40%排序,但直观地说,它应该得到更高的分数.这种事情有标准的算法吗？

Answer 1

这似乎是Levenshtein Damerau-Levenshtein距离的良好候选者- 对阵列进行排序所需的交换次数.这应该与每个项目与排序数组中的位置的距离成比例.

这是一个简单的ruby算法,它总结了距离的平方.它似乎是排序的一个很好的衡量标准 - 每次交换两个无序元素时结果会变小.

ap = a.sort
sum = 0
a.each_index{|i| j = ap.index(a[i])-i 
  sum += (j*j)
}
dist = sum/(a.size*a.size)

Answer 2

我认为要使用的函数的选择在很大程度上取决于您打算使用它的用途。根据您的问题，我猜测您正在使用遗传系统来创建排序程序，这将是排名功能。如果是这样的话，那么执行速度就至关重要。基于此，我敢打赌你的最长排序子序列算法会工作得很好。听起来它应该很好地定义健身。