# 9.1

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

## Algorithm

Given `a`, the input array, and `curr`, the derangement built up so far:

1. If `curr` 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 `a`. It must not already have been used so far (`!curr.contains(a[i]`), and it must not be the element at the same position in the input array (`i != curr.size()`).
1. For each remaining possibility, add it to the current derangement and recurse.

## Implementation in Java

```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);

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

dg.derangements(a);
}
}
```

Back to Chapter 9