Permutations by swapping: Difference between revisions

Content added Content deleted

Inline

@@ Line 13: / Line 13: @@
 * [[Matrix arithmetic]]
-=={{header|J}}==
+=={{header|D}}==
+===Iterative Version===
+This isn't a Range.
+{{trans|Python}}
+<lang d>import std.algorithm, std.array, std.typecons, std.range;
+struct Spermutations {
+    const int n;
+    alias Tuple!(int[], int) TResult;
+    int opApply(int delegate(ref TResult) dg) {
+        int result;
+        TResult aux;
+        int sign = 1;
+        alias Tuple!(int, int) Pair;
+        auto p = iota(n).map!(i => Pair(i, i ? -1 : 0))().array();
+        aux = tuple(p.map!(pp => pp[0])().array(), sign);
+        result = dg(aux); if (result) goto END;
+        while (p.canFind!(pp => pp[1])()) {
+            // Failed using std.algorithm here, too much complex
+            auto largest = Pair(-100, -100);
+            int i1 = -1;
+            foreach (i, pp; p)
+                if (pp[1]) {
+                    if (pp[0] > largest[0]) {
+                        i1 = i;
+                        largest = pp;
+                    }
+                }
+            int n1 = largest[0], d1 = largest[1];
+            sign *= -1;
+            int i2;
+            if (d1 == -1) {
+                i2 = i1 - 1;
+                swap(p[i1], p[i2]);
+                if (i2 == 0 || p[i2 - 1][0] > n1)
+                    p[i2][1] = 0;
+            } else if (d1 == 1) {
+                i2 = i1 + 1;
+                swap(p[i1], p[i2]);
+                if (i2 == n - 1 || p[i2 + 1][0] > n1)
+                    p[i2][1] = 0;
+            }
+            aux = tuple(p.map!(pp => pp[0])().array(), sign);
+            result = dg(aux); if (result) goto END;
+            foreach (i3, ref pp; p) {
+                auto n3 = pp[0], d3 = pp[1];
+                if (n3 > n1)
+                    pp[1] = (i3 < i2) ? 1 : -1;
+            }
+        }
+        END: return result;
+    }
+}
+void main() {
+    import std.stdio;
+    foreach (n; [3, 4]) {
+        writefln("\nPermutations and sign of %d items", n);
+        foreach (tp; Spermutations(n))
+            writefln("Perm: %s Sign: %2d", tp.tupleof);
+    }
+}</lang>
+{{out}}
+<pre>
+Permutations and sign of 3 items
+Perm: [0, 1, 2] Sign:  1
+Perm: [0, 2, 1] Sign: -1
+Perm: [2, 0, 1] Sign:  1
+Perm: [2, 1, 0] Sign: -1
+Perm: [1, 2, 0] Sign:  1
+Perm: [1, 0, 2] Sign: -1
+Permutations and sign of 4 items
+Perm: [0, 1, 2, 3] Sign:  1
+Perm: [0, 1, 3, 2] Sign: -1
+Perm: [0, 3, 1, 2] Sign:  1
+Perm: [3, 0, 1, 2] Sign: -1
+Perm: [3, 0, 2, 1] Sign:  1
+Perm: [0, 3, 2, 1] Sign: -1
+Perm: [0, 2, 3, 1] Sign:  1
+Perm: [0, 2, 1, 3] Sign: -1
+Perm: [2, 0, 1, 3] Sign:  1
+Perm: [2, 0, 3, 1] Sign: -1
+Perm: [2, 3, 0, 1] Sign:  1
+Perm: [3, 2, 0, 1] Sign: -1
+Perm: [3, 2, 1, 0] Sign:  1
+Perm: [2, 3, 1, 0] Sign: -1
+Perm: [2, 1, 3, 0] Sign:  1
+Perm: [2, 1, 0, 3] Sign: -1
+Perm: [1, 2, 0, 3] Sign:  1
+Perm: [1, 2, 3, 0] Sign: -1
+Perm: [1, 3, 2, 0] Sign:  1
+Perm: [3, 1, 2, 0] Sign: -1
+Perm: [3, 1, 0, 2] Sign:  1
+Perm: [1, 3, 0, 2] Sign: -1
+Perm: [1, 0, 3, 2] Sign:  1
+Perm: [1, 0, 2, 3] Sign: -1</pre>
+===Recursive Version===
+Same output.
+{{trans|Python}}
+<lang d>import std.algorithm, std.array, std.typecons, std.range;
+Tuple!(int[], int)[] sPermutations(in int n) /*pure nothrow*/ {
+    static int[][] sPermu(in int items) /*pure nothrow*/ {
+        if (items <= 0)
+            return [[]];
+        typeof(return) r;
+        foreach (i, item; sPermu(items - 1)) {
+            if (i % 2)
+                r ~= iota(cast(int)item.length, -1, -1)
+                     .map!(i => item[0..i] ~ (items-1) ~ item[i..$])()
+                     .array();
+            else
+                r ~= iota(item.length + 1)
+                     .map!(i => item[0..i] ~ (items-1) ~ item[i..$])()
+                     .array();
+        }
+        return r;
+    }
+    auto r = sPermu(n);
+    return iota(r.length)
+           .map!(i => tuple(r[i], i % 2 ? -1 : 1))()
+           .array();
+}
+void main() {
+    import std.stdio;
+    foreach (n; [3, 4]) {
+        writefln("\nPermutations and sign of %d items", n);
+        foreach (tp; sPermutations(n))
+            writefln("Perm: %s Sign: %2d", tp.tupleof);
+    }
+}</lang>
+=={{header|J}}==
 J has a built in mechanism for [http://www.jsoftware.com/help/dictionary/dacapdot.htm representing permutations] (which is designed around the idea of selecting a permutation uniquely by an integer) but it does not seem seem to have an obvious mapping to Steinhaus–Johnson–Trotter.  Perhaps someone with a sufficiently deep view of the subject of permutations can find a direct mapping?