|
|
| Line 1: |
Line 1: |
| − | == Algorithm ==
| |
| − |
| |
| − | Given <code>a</code>, the input array, and <code>curr</code>, the derangement built up so far:
| |
| − |
| |
| − | # If <code>curr</code> represents a complete solution, print it.
| |
| − | # 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>).
| |
| − | ## 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>
| |
| | | | |
| | | | |
| | Back to [[Chapter 9]] | | Back to [[Chapter 9]] |
