001// Exercise 2.5.19 (Solution published at http://algs4.cs.princeton.edu/) 002package algs25; 003import stdlib.*; 004import algs22.XInversions; 005/* *********************************************************************** 006 * Compilation: javac KendallTau.java 007 * Execution: java KendallTau N 008 * 009 * Generate two random permutations of size N and compute their 010 * Kendall tau distance (number of inversions). 011 * 012 *************************************************************************/ 013 014public class XKendallTau { 015 016 // return Kendall tau distance between two permutations 017 public static int distance(int[] a, int[] b) { 018 if (a.length != b.length) throw new Error("Array dimensions disagree"); 019 int N = a.length; 020 021 int[] ainv = new int[N]; 022 for (int i = 0; i < N; i++) ainv[a[i]] = i; 023 024 Integer[] bnew = new Integer[N]; 025 for (int i = 0; i < N; i++) bnew[i] = ainv[b[i]]; 026 027 return XInversions.count(bnew); 028 } 029 030 031 // return a random permutation of size N 032 public static int[] permutation(int N) { 033 int[] a = new int[N]; 034 for (int i = 0; i < N; i++) { 035 int r = (int) (Math.random() * (i + 1)); 036 a[i] = a[r]; 037 a[r] = i; 038 } 039 return a; 040 } 041 042 043 044 045 public static void main(String[] args) { 046 047 // two random permutation of size N 048 int N = Integer.parseInt(args[0]); 049 int[] a = permutation(N); 050 int[] b = permutation(N); 051 052 053 // print initial permutation 054 for (int i = 0; i < N; i++) 055 StdOut.println(a[i] + " " + b[i]); 056 StdOut.println(); 057 058 StdOut.println("inversions = " + distance(a, b)); 059 } 060} 061 062