01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
|
// Exercise 2.5.19 (Solution published at http://algs4.cs.princeton.edu/)
package algs25;
import stdlib.*;
import algs22.XInversions;
/* ***********************************************************************
* Compilation: javac KendallTau.java
* Execution: java KendallTau N
*
* Generate two random permutations of size N and compute their
* Kendall tau distance (number of inversions).
*
*************************************************************************/
public class XKendallTau {
// return Kendall tau distance between two permutations
public static int distance(int[] a, int[] b) {
if (a.length != b.length) throw new Error("Array dimensions disagree");
int N = a.length;
int[] ainv = new int[N];
for (int i = 0; i < N; i++) ainv[a[i]] = i;
Integer[] bnew = new Integer[N];
for (int i = 0; i < N; i++) bnew[i] = ainv[b[i]];
return XInversions.count(bnew);
}
// return a random permutation of size N
public static int[] permutation(int N) {
int[] a = new int[N];
for (int i = 0; i < N; i++) {
int r = (int) (Math.random() * (i + 1));
a[i] = a[r];
a[r] = i;
}
return a;
}
public static void main(String[] args) {
// two random permutation of size N
int N = Integer.parseInt(args[0]);
int[] a = permutation(N);
int[] b = permutation(N);
// print initial permutation
for (int i = 0; i < N; i++)
StdOut.println(a[i] + " " + b[i]);
StdOut.println();
StdOut.println("inversions = " + distance(a, b));
}
}
|