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