9.1

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) {
        d(a, new LinkedList<Integer>());
    }

    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()) {
                    curr.addLast(a[i]); // O(1)
                    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);
    }
}

Back to Chapter 9