• Kendall tau距離的定義

以下定義取自wiki百科Kendall tau distance：

The Kendall tau rank distance is a metric that counts the number of pairwise disagreements between two ranking lists. The larger the distance, the more dissimilar the two lists are.

也就是說，Kendall tau距離就是兩個排列之間的逆序數，它反映了兩個排列的相似程度。例如兩個在區間[ 0 , 6 ]的排列：

a = { 0, 3, 1, 6, 2, 5, 4 }?
b = { 1, 0, 3, 6, 4, 2, 5 }

求a，b的Kendall tau距離，就是求兩個排列之間的逆序{ 0，1 }，{ 3，1 }，{ 2，4 }，{ 5，4 }，一共為4對，故Kendall tau距離為4。

• Kendall tau距離的求法

從上面的例子可以看出，兩個排列之間的逆序數可以看作是以a為排列的標準，b排列自身的逆序數。要以a為排列標準，首先需要將a排列的索引提取出來放到新排列aIndex中，即aIndex[ a[ i ] ] = i 。接著要以a排列的索引去確定b的索引，即bIndex[ i ] = aIndex[ b[ i ] ] 。從而bIndex中索引的逆序數就是a，b之間的逆序數了。?
一種特殊情況就是：a[ i ] = i 自然數序，則aIndex[ i ] = i ，bIndex[ i ] = b[ i ] ，則以a為排列的標準，b排列的逆序數就是b排列自身的逆序數。

• 求一個排列的逆序數

首先考慮簡單的平方量級的算法。在插入排序或者冒泡排序中，元素交換的次數等于該排列的逆序數，因此在排序過程中統計交換次數即可。但是這種方法效率比較低。?
更高效的方法啟發自高效的排序算法，比如歸并排序，它可以使得算法變成線性對數量級。在將兩個有序的排列歸并在一起時，前子數組首元素如果小于后子數組首元素，則逆序數為0，反之，逆序數為前子數組當前的元素個數。

• 求Kendall tau距離的實現

public class KendallTau {private static long counter = 0;public static long distance(int[] a, int[] b) {if (a.length != b.length) {throw new IllegalArgumentException("Array dimensions disagree");}int N = a.length;int[] aIndex = new int[N];// 記錄a數組的索引for (int i = 0; i < N; i++) {aIndex[a[i]] = i;}int[] bIndex = new int[N];// b數組引用a數組的索引for (int i = 0; i < N; i++) {bIndex[i] = aIndex[b[i]];}return mergeCount(bIndex);}// 使用插入排序方法求逆序數public static long insertionCount(int[] a) {for (int i = 1; i < a.length; i++) {for (int j = i; j > 0 && a[j] < a[j - 1]; j--) {int temp = a[j];a[j] = a[j - 1];a[j - 1] = temp;counter++;// 插入排序每交換一次，就存在一對逆序數}}return counter;}// 使用歸并排序方法求逆序數private static int[] aux;public static long mergeCount(int[] a) {aux = new int[a.length];mergeSort(a, 0, a.length-1);return counter;}private static void mergeSort(int[] a, int lo, int hi) {if (hi <= lo) {return;}int mid = lo + (hi - lo) / 2;mergeSort(a, lo, mid);mergeSort(a, mid + 1, hi);merge(a, lo, mid, hi);}public static void merge(int[] a, int lo, int mid, int hi) {int i = lo, j = mid + 1;for (int k = lo; k <= hi; k++) {aux[k] = a[k];}for (int k = lo; k <= hi; k++) {if (i > mid) {a[k] = aux[j++];} else if (j > hi) {a[k] = aux[i++];} else if (aux[j] < aux[i]) {a[k] = aux[j++];counter += mid - i + 1;// 每個比前子數組小的后子數組元素，逆序數為前子數組現有的長度} else {a[k] = aux[i++];}}}public static void main(String[] args) {int[] a = new int[] { 0, 3, 1, 6, 2, 5, 4 };int[] b = new int[] { 1, 0, 3, 6, 4, 2, 5 };for (int i = 0; i < a.length; i++) {System.out.println(a[i] + " " + b[i]);}System.out.println("Inversions:" + distance(a, b));} } 原文

總結

以上是生活随笔為你收集整理的Kendall tau距离：求两个排列之间的逆序数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。