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