nextPermutation and ranges

[H. S. Teoh]

On Thu, Feb 07, 2013 at 07:22:10PM +0100, bearophile wrote:
> Recently "quickfur"

That's my github handle.


> and Andrei have added C++-style functions (nextPermutation and
> nextEvenPermutation) to std.algorithm to perform permutations, this is
> a Phobos improvement and I've already used them few times:
[...]
> But in many cases I have a set of items, and I want to find (most or
> all of) their permutations lazily (even if they are not comparable).
> In many of such cases I prefer a permutations generator that plays
> well with ranges:

I've considered implementing as a range before, but there are some
considerations:

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.

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. But there is no generic way to make a
copy of a range (using .save on a forward range is not enough, because
nextPermutation swaps elements in-place, and .save doesn't guarantee
that the saved range isn't just aliasing the original range contents).

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);
	}

A similar wrapper can be made for nextEvenPermutation.

This actually brings up an interesting point: the current documentation
for SortedRange states that ranges with weaker than random access is
unable to provide interesting functionality in SortedRange, but the
above is a counterexample. :) That is, if SortedRange allowed forward
ranges, then we could make the sorted requirement explicit:

	auto permutations(R)(SortedRange!R forwardRange)
		if (isForwardRange!R)
	{
		...
	}


[...]
> A simple speed benchmark seems to show that a permutations Range is
> not bad (0.90 seconds for the range versus 2.76 seconds for
> nextPermutation to fully permute 11 integers):
> 
> 
> 
> import std.algorithm, std.conv, std.traits;
> 
> struct Permutations(bool doCopy=true, T) if (isMutable!T) {
>     private immutable size_t num;
>     private T[] items;
>     private uint[31] indexes;
>     private ulong tot;
> 
>     this (/*in*/ T[] items) /*pure nothrow*/
>     in {
>         static enum string L = text(indexes.length); // impure
>         assert(items.length >= 0 && items.length <= indexes.length,
>                "Permutations: items.length must be >= 0 && < " ~ L);
>     } body {
>         static ulong factorial(in uint n) pure nothrow {
>             ulong result = 1;
>             foreach (i; 2 .. n + 1)
>                 result *= i;
>             return result;
>         }
[...]

I think this is an unfair comparison: using factorial assumes that all
array elements are unique. The advantage of nextPermutation is that it
correctly handles duplicated elements, producing only distinct
permutations of them. It's no surprise that if you sacrifice handling of
duplicated elements, the code will be faster.

(Not to mention, using factorial is limited because its value grows too
quickly, and once your range is large enough, you will be needing to use
BigInt to be able to deal with the factorial values without overflow.
The current implementation of nextPermutation doesn't suffer from this
problem.)


> Extra note: maybe all such functions should be moved inside a
> std.combinatorics or std.math.comb module or something similar, with
> combinations range, binomial coefficient function, etc.
[...]

Someone is already working on std.combinatorics, and when that is ready,
these functions will be folded in there. I guess Andrei decided it was
better to put them into Phobos earlier rather than later. They can be
turned into aliases afterwards, once std.combinatorics is merged, so no
existing code will break.


T

-- 
The volume of a pizza of thickness a and radius z can be described by the following formula: pi zz a. -- Wouter Verhelst