HatsPart1.java

Below is the syntax highlighted version of HatsPart1.java.

/*********************************************************************** 
Christopher Moretti
cmoretti
P01A/P06

Read in list size and permutations of that size.
Determine if each is a "derangement". 
Print out the first derangement if it exists.
Print out the number of derangements.

Requires StdIn and StdOut
***********************************************************************/

public class HatsPart1 {

    // print the first derangement with the given format
    private static void printD(int[] r) {
        StdOut.print("First derangement: ");
        for (int i = 0; i < r.length; i++)
            StdOut.print(r[i]+" ");
        StdOut.println();
    }
    
    // return true if r holds a derangement, false otherwise
    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;
    }

    public static void main(String[] args) {
        // the # of items in permutation
        int N = StdIn.readInt(); 

        // space to hold permutation
        int[] arr = new int[N]; 

        // 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();

            // if arr is a derangement, count i
            // and print it if it's the first.
            if (isD(arr)) { 
                if (count == 0) 
                    printD(arr); 
                count++; 
            }
        }

        // print the count with the given format
        StdOut.println("Number of derangements: " + count);
    }
}