Dinesman's multiple-dwelling problem: Difference between revisions

← Older edit Newer edit →

Content deleted Content added

Inline

@@ Line 129: / Line 129: @@
 =={{header|D}}==
 As for flexibility: the solve function is parameterized, accepting a length argument and a variable number of function predicates.
-<lang d>import std.stdio, std.range, std.math;
+<lang d>import std.stdio, std.exception, std.range, std.algorithm, std.math;
+pure T fact(T)(T n) {
-// From http://rosettacode.org/wiki/Permutations#D
+    T result = 1;
-auto permutations(size_t n) {
-    auto seq = array(iota(n));
+    for (T i = 2; i <= n; i++)
+        result *= i;
-    size_t[][] res;
+    return result;
+}
-    void perms(size_t[] s, size_t[] pre = []) {
-        if (s.length) {
+struct LazyPermutation {
-            foreach (i, c; s) {
+    private uint[] seq;
-               perms(s[0 .. i] ~ s[i + 1 .. $], pre ~ c);
+    private size_t tot;
+    private size_t num;
+    this (size_t num) {
+        enforce(num > 1, "LazyPermutation: num must be > 1");
+        this.seq = array(iota(0, num));
+        this.tot = fact(num);
+        this.num = num;
+    }
+    @property uint[] front() {
+        return seq;
+    }
+    @property bool empty() {
+        return tot == 0;
+    }
+    void popFront(){
+        if (--tot > 0) {
+            size_t j = num - 2;
+            while (seq[j] > seq[j + 1]) {
+                j--;
             }
-        } else res ~= pre;
+            size_t k = num - 1;
+            while (seq[j] > seq[k]) {
-    }
-    perms(seq);
+                k--;
-    return res;
+            }
+            swap(seq[k], seq[j]);
+            size_t r = num - 1;
+            size_t s = j + 1;
+            while (r > s) {
+                swap(seq[s], seq[r]);
+                r--;
+                s++;
+            }
+        }
+    }
 }
 size_t[] solve(T : size_t, F...)(T len, F predicates) {
     outer:
-    foreach (p; permutations(len)) {
+    foreach (p; LazyPermutation(len)) {
         foreach (pred; predicates)
             if (!pred(p))
                 continue outer;
         return p;
@@ Line 161: / Line 195: @@
     enum Floors = 5;
     enum {Baker, Cooper, Fletcher, Miller, Smith};
     auto p1 = (uint[] s){ return s[Baker] != s.length-1; };
     auto p2 = (uint[] s){ return s[Cooper] != 0; };
     auto p3 = (uint[] s){ return s[Fletcher] != 0 && s[Fletcher] != s.length-1; };
     auto p4 = (uint[] s){ return s[Miller] > s[Cooper]; };
     auto p5 = (uint[] s){ return abs(cast(int)(s[Smith] - s[Fletcher])) != 1; };
     auto p6 = (uint[] s){ return abs(cast(int)(s[Cooper] - s[Fletcher])) != 1; };
     if (auto sol = solve(Floors, p1, p2, p3, p4, p5, p6))
         writeln(sol);