/***********************************************************************
Christopher Moretti
cmoretti
P01A/P06
Read in list side and permutations of that size.
Determine the max cycle length of each permutation.
Compute and print the average max cycle length.
Requires StdIn, StdOut
***************************************************************************/
public class HatsPart2 {
// determine longest cycle to get own hat back
public static int maxCycleLength(int[] arr) {
int N = arr.length;
int max = 0; // max cycle length
int cycle; // current cycle length
// for each person
for (int i = 0; i < N; i++) {
int j = i;
cycle = 1; // minimal cycle has 1 person
// while person j doesn't have person i's hat
while (arr[j] != i+1) {
j = arr[j] - 1; // new person j to look for
cycle++;
}
if (max < cycle) max = cycle; // new longest cycle
}
// return longest cycle length
return max;
}
public static void main(String[] args) {
// the # of items in the permutation
int N = StdIn.readInt();
// space to hold permutation
int[] arr = new int[N];
// running sum for max cycle lengths
int sum = 0;
// how many derangements have we seen?
int count = 0;
// Read until there are no more permutations left on StdIn.
while (!StdIn.isEmpty()) {
// fill array
for (int i = 0; i < N; i++) {
arr[i] = StdIn.readInt();
}
// count it and find its max cycle length
count++;
sum += maxCycleLength(arr);
}
// compute and print average with the given format
StdOut.println("Average max cycle length: " + (double) sum / count);
}
}