Dinesman's multiple-dwelling problem: Difference between revisions

As for flexibility: the solve code works with an arbitrary number of people and of function predicates.

<lang d>import std.stdio, std.range, std.algorithm, std.math, std.exception;

struct LazyPermutations {

private immutable size_t num;

private uint[] seq;

private ulong tot;

this (in size_t n) /*pure*/ nothrow

in {

enforce(n > 1, "Permutations: n must be > 1");

} body {

static ulong factorial(in uint n) pure nothrow {

ulong result = 1;

foreach (i; 2 .. n + 1)

result *= i;

return result;

}

this.seq = array(iota(n)); // not pure

this.tot = factorial(n);

this.num = n;

}

@property const(uint[]) front() const pure nothrow {

return seq;

}

@property bool empty() const pure nothrow {

return tot == 0;

}

void popFront() pure nothrow {

tot--;

if (tot > 0) {

size_t j = num - 2;

while (seq[j] > seq[j + 1])

j--;

size_t k = num - 1;

while (seq[j] > seq[k])

k--;

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++;

}

}

}

}

//import std.traits: EnumMembers;

import std.traits;

enum N { Baker, Cooper, Fletcher, Miller, Smith }

alias /*immutable*/ bool function(in uint[]) pure nothrow P;

enum nNames = EnumMembers!N.length;

foreach (sol; LazyPermutations(nNames))

writeln(map!(p => [EnumMembers!N][p])(sol));