Algowikiadmin: Recovering wiki

2014-09-11T18:22:37Z

Recovering wiki

Algowikiadmin: Recovering wiki

2014-09-11T18:13:19Z

Recovering wiki

New page

== 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>

@@ Line 1: / Line 1: @@
 == Algorithm ==
-Given &lt;code&gt;a&lt;/code&gt;, the input array, and &lt;code&gt;curr&lt;/code&gt;, the derangement built up so far:
+Given <code>a</code>, the input array, and <code>curr</code>, the derangement built up so far:
-# If &lt;code&gt;curr&lt;/code&gt; represents a complete solution, print it.
+# 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 &lt;code&gt;a&lt;/code&gt;. It must not already have been used so far (&lt;code&gt;!curr.contains(a[i]&lt;/code&gt;), and it must not be the element at the same position in the input array (&lt;code&gt;i != curr.size()&lt;/code&gt;).
+# 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 ==
-&lt;pre&gt;
+<pre>
 public class DerangementGenerator {
      public void derangements(int[] a) {
-         d(a, new LinkedList&lt;Integer&gt;());
+         d(a, new LinkedList<Integer>());
+     }
-     public void d(int[] a, LinkedList&lt;Integer&gt; curr) {
+     public void d(int[] a, LinkedList<Integer> curr) {
          if (curr.size() == a.length)
              print(curr);
          else {
-             for (int i = 0; i &lt; a.length; i++) {
+             for (int i = 0; i < a.length; i++) {
-                 if (!curr.contains(a[i]) &amp;&amp; i != curr.size()) {
+                 if (!curr.contains(a[i]) && i != curr.size()) {
                      curr.addLast(a[i]); // O(1)
                      d(a, curr);
@@ Line 29: / Line 29: @@
+     }
-     public void print(List&lt;Integer&gt; l) {
+     public void print(List<Integer> l) {
-         for (int i = 0; i &lt; l.size() - 1; i++) {
+         for (int i = 0; i < l.size() - 1; i++) {
-             System.out.print(l.get(i) + &quot;, &quot;);
+             System.out.print(l.get(i) + ", ");
+         }
          System.out.println(l.get(l.size() - 1));
@@ Line 37: / Line 37: @@
      public static void main(String[] args) {
-         if (args.length &lt; 1) {
+         if (args.length < 1) {
-             System.err.println(&quot;Usage: java DerangementGenerator N&quot;);
+             System.err.println("Usage: java DerangementGenerator N");
              System.exit(-1);
+         }
@@ Line 45: / Line 45: @@
          DerangementGenerator dg = new DerangementGenerator();
          int[] a = new int[n];
-         for (int i = 0; i &lt; n; i++) {
+         for (int i = 0; i < n; i++) {
              a[i] = i + 1;
+         }
@@ Line 52: / Line 52: @@
+     }
+}
-&lt;/pre&gt;
+</pre>

TADM2E 7.1 - Revision history

Algowikiadmin: Recovering wiki

Algowikiadmin: Recovering wiki