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