HasParts - COS 126

http://www.cs.princeton.edu/courses/archive/fall13/cos126/docs/mid1-f12-prog.pdf
http://www.cs.princeton.edu/courses/archive/fall13/cos126/docs/HatsPart1.java.html
public class HatsPart1
public static boolean isD(int[] a) // Is the permutation in array a a derangement?

    public static boolean isD(int[] r) {
        for (int i = 0; i < r.length; i++) {
            if (r[i] == i+1) //i+1 to account for Java 0-based arrays
                return false;
        }
        return true;
    }

Assuming that all hats are labeled with owner’s names, one way to get your hat back aer
graduation is to swap hats with the person whose hat you have, continuing until you get your hat.
You are always guaranteed to get your hat back that way. For example, in the permutation
p1 p2 p3 p4 p5 p6 p7 p8 p9
3 7 6 9 8 2 1 5 4
student 1 would get her hat back by swapping with student 3, then 6 then 2, then 7.
e sequence 1 3 6 2 7 is an example of a cycle. e length of this cycle is 5 (including 7 back
to 1). A person who already has her own hat forms a cycle of length 1. Every permutation consists
of a set of 1 or more cycles. In this example, the other cycles are 4 9 and 5 8, each of length 2.
Your next task is to determine the length of the longest cycle in each permutation from the input,
and use that to determine the average longest cycle length for the given permutations. For
example, in the permutation above the longest cycle length is 5. e lengths of the longest cycles
in the %ve permutations in 5perms9.txt are 1, 2, 2, 9, and 5, respectively, so the average length
of the longest cycle in this set of permutations is 3.8.
http://www.cs.princeton.edu/courses/archive/fall13/cos126/docs/HatsPart2.java.html

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

http://www.cs.princeton.edu/courses/archive/fall15/cos126/exams.html