nextPermutation and ranges
Peter Alexander
peter.alexander.au at gmail.com
Thu Feb 7 11:40:25 PST 2013
> Someone is already working on std.combinatorics
That's me. I'm very bust atm with work, so I haven't been able to
do much with it lately, but it is progressing.
> 1) To avoid excessive allocations, it would have to be a
> transient
> range. Which means it may have unexpected results if you use it
> with an
> algorithm that doesn't handle transient ranges correctly.
This has been discussed previously. bearophile suggested a policy
to control whether the buffer is permuted in-place, with it
defaulting to creating duplicates. The slow down from duplicates
on DMD was ~3x.
> 2) If the starting range is not sorted, then the permutation
> range needs
> to make a copy of the original range so that it knows when all
> permutations have been enumerated.
I sort on range creation (if not already sorted).
> If transience is acceptable, and the starting range is always
> sorted,
> then it's almost trivial to write a wrapper range:
>
> auto permutations(R)(R forwardRange)
> if (isForwardRange!R)
> {
> struct Permutations
> {
> R front;
> bool empty = false;
> this(R _src) { front = _src; }
> void popFront() { empty = !nextPermutation(front); }
> }
> return Permutations(forwardRange);
> }
This is missing some features:
- Bidirectionality (this complicates things).
- Length (this complicates things, because it easily overflows).
- Random-access (non-trivial, but useful)
A library solution should address all these.
More information about the Digitalmars-d
mailing list