Kendall's tau相似程度指标

两个序列，例如S1 = {a, b, c, d}、 S2 = {a, c, b, d}，如何度量它们的相似程度，有很重要的应用背景，在投票决策、表达式搜索、top-k比较、乃至搜索引擎优化等问题上有广泛的应用ref1 ,ref2 。Kendall's tau则是其中一种度量指标。由同样元素组成，只是元素的排列顺序不同的两个序列，如果其顺序完全一致，则Kendall's tau值为1，如果完全反序其Kendall's tau值为0。

Kendall's tau具体的计算方式为:

1 - 2.0*reversions / (n * (n -1))，

其中n为序列本身的长度(两个序列的长度相同)，reversions为逆序对的个数。

逆序对的计算方法是: 对于两个给定的序列S1 = {a, b, c, d}和S2 = {a, c, b, d}。分别找出两个序列的二元约束集。在这个例子中S1的所有二元约束集为{(a,b), (a,c), (a,d), (b,c), (b,d)， (c,d)}，S2的所有二元约束集为{(a,c), (a,b), (a,d), (c,b), (c,d), (b,d)}。比较两个二元约束集，其中不同的二元约束是(b,c)和(c,b)，即逆序对的个数为1。

代入上面的计算公式可以得到这两个序列的Kendall's tau指标为:

1 - 2. * 1 / (4 * 3)  = 2. / 3 = 0.833

 

输入：

两个由同样元素组成的序列，每行一个。序列长度一致，只是元素的排列顺序不同，里面的元素不重复。

输出：

对应的Kendall's tau指标值，保留到小数点后3位("%.3f\n")

样例输入：

a,b,c,d↵

a,c,b,d↵

样例输出：

0.833↵

 

 

import java.util.Scanner;
public class Main {
	public static int fun(String[] str3,String[] str4){
		int num = str3.length;
		String[] str5 = new String[(num-1)*num/2];//拆分后放置数组
		String[] str6 = new String[(num-1)*num/2];
		for(int i = 0,k=0; i < num-1; i++){//找出二元约束集
			for(int j =i+1;j<num;j++){
				str5[k] = str3[i]+str3[j];
				str6[k++] = str4[i]+str4[j];
			}
		}
		int nReverse = 0;
		for(int i=0;i<str5.length;i++){//查找两个字符串数组中相同的二元约束集的个数
			for(int j=0;j<str6.length;j++){
				if(str5[i].equals(str6[j])){
					nReverse++;
				}
			}	
		}
		return (str5.length - nReverse);//返回不同的二元约束集的个数
	}
			
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		String str1 = scanner.nextLine();
		String str2 = scanner.nextLine();
		String[] str3 = str1.split(",");
		String[] str4 = str2.split(",");
		int strlen = str3.length;
		int nr = fun(str3,str4);
		double d = 1-2.0*nr/(strlen*(strlen-1));
		System.out.printf("%.3f\n",d);
	}
}