HatsPart2.java

Below is the syntax highlighted version of HatsPart2.java.

/***********************************************************************
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);
    }
}