Struct Perm

A struct that generates all possible permutations of a sequence.

struct Perm(T) ;

Constructors

NameDescription
this Generate permutations from an input range. Create a duplicate of this sequence so that the original sequence is not modified.

Fields

NameTypeDescription
currentIndex ubyte
Is ubyte[MAX_PERM_LEN]
len ubyte
nPerms size_t

Properties

NameTypeDescription
empty[get] bool
front[get] const(T)[]Returns the current permutation. The array is const because it is recycled across iterations and modifying it would destroy the state of the permutation generator.
length[get] size_tThe number of permutations left.
save[get] typeof(this)

Methods

NameDescription
popFront Get the next permutation in the sequence. This will overwrite the contents of the array returned by the last call to front.

Aliases

NameDescription
PermArray

Notes

Permutations are output in undefined order.

The array returned by front is recycled across iterations. To preserve it across iterations, wrap this range using map!"a.dup" or map!"a.idup".

Bugs

Only supports iterating over up to size_t.max permutations. This means the max permutation length is 12 on 32-bit machines, or 20 on 64-bit. This was a conscious tradeoff to allow this range to have a length of type size_t, since iterating over such huge permutation spaces would be insanely slow anyhow.

Examples

double[][] res;
auto perm = map!"a.dup"(Perm!(double)([1.0, 2.0, 3.0][]));
foreach(p; perm) {
     res ~= p;
}

auto sorted = sort(res);
assert(sorted.canFind([1.0, 2.0, 3.0]));
assert(sorted.canFind([1.0, 3.0, 2.0]));
assert(sorted.canFind([2.0, 1.0, 3.0]));
assert(sorted.canFind([2.0, 3.0, 1.0]));
assert(sorted.canFind([3.0, 1.0, 2.0]));
assert(sorted.canFind([3.0, 2.0, 1.0]));
assert(sorted.length == 6);