# Difference between revisions of "TADM2E 7.1"

## Algorithm

Given <code>a</code>, the input array, and <code>curr</code>, the derangement built up so far:

1. If <code>curr</code> represents a complete solution, print it.
2. Otherwise, examine all the possibilities for the next element of the derangement. The next element must come from the input array <code>a</code>. It must not already have been used so far (<code>!curr.contains(a[i]</code>), and it must not be the element at the same position in the input array (<code>i != curr.size()</code>).
1. For each remaining possibility, add it to the current derangement and recurse.

## Implementation in Java

<pre> public class DerangementGenerator {

   public void derangements(int[] a) {
}

   public void d(int[] a, LinkedList<Integer> curr) {
if (curr.size() == a.length)
print(curr);
else {
for (int i = 0; i < a.length; i++) {
if (!curr.contains(a[i]) && i != curr.size()) {
d(a, curr);
curr.removeLast(); // O(1)
}
}
}
}

   public void print(List<Integer> l) {
for (int i = 0; i < l.size() - 1; i++) {
System.out.print(l.get(i) + ", ");
}
System.out.println(l.get(l.size() - 1));
}

   public static void main(String[] args) {
if (args.length < 1) {
System.err.println("Usage: java DerangementGenerator N");
System.exit(-1);
}
int n = Integer.parseInt(args[0]);

       DerangementGenerator dg = new DerangementGenerator();
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = i + 1;
}

       dg.derangements(a);
}


} </pre>