Difference between revisions of "TADM2E 7.1"

Revision as of 18:13, 11 September 2014

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) {
       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);
   }

} </pre>