The OpenD Programming Language

Permutations

Lazy Forward range of permutations using Heap's algorithm.

It always generates the permutations from 0 to n - 1, use indexedRoR to map it to your range.

Generating a new item is in O(k) (amortized O(1)), the total number of elements is n^k.

struct Permutations (

T

) if (

isUnsigned!T &&

T.sizeof <= size_t.sizeof

) {

Slice!(Iterator, N, kind) sliced(Slice!(Iterator, 1, kind) slice, size_t[N] lengths) via import mir.ndslice.slice : sliced, Slice;;

alias Slice = mir_slice via import mir.ndslice.slice : sliced, Slice;;

alias DeepElement = T;

this(T[] state, T[] indices);

Slice!(const(T)*) front [@property getter];

void popFront();

bool empty [@property getter];

size_t length [@property getter];

size_t[2] shape [@property getter];

Permutations save [@property getter];

}

Constructors

this this(T[] state, T[] indices): state should have the length of n - 1, whereas the length of indices should be n

Members

Aliases

DeepElement alias DeepElement = T

Functions

popFront void popFront()
empty bool empty [@property getter]: Input range primitives

Properties

front Slice!(const(T)*) front [@property getter]
length size_t length [@property getter]: Input range primitives
save Permutations save [@property getter]: Forward range primitive. Allocates using GC.
shape size_t[2] shape [@property getter]

Examples

import mir.ndslice.fuse;
import mir.ndslice.topology : iota;

auto expectedRes = [[0, 1, 2],
     [1, 0, 2],
     [2, 0, 1],
     [0, 2, 1],
     [1, 2, 0],
     [2, 1, 0]];

auto r = iota(3);
auto rp = permutations(r.length).indexedRoR(r);
assert(rp.fuse == expectedRes);

// direct style
auto rp2 = iota(3).permutations;
assert(rp2.fuse == expectedRes);

import mir.algorithm.iteration: equal;
import mir.ndslice.slice: sliced;
import mir.ndslice.topology : iota;

import std.experimental.allocator.mallocator;

static immutable expected2 = [0, 1, 1, 0];
auto r = iota(2);
auto rp = makePermutations(Mallocator.instance, r.length);
assert(expected2.sliced(2, 2).equal(rp.indexedRoR(r)));
dispose(Mallocator.instance, rp);

See Also

permutations, makePermutations

Meta

Source

See Implementation

mir combinatorics functions

structs