next_permutation and cartesian product for ranges?

[H. S. Teoh]

On Wed, Oct 10, 2012 at 09:41:34AM -0400, Andrei Alexandrescu wrote:
> On 10/9/12 7:25 PM, H. S. Teoh wrote:
> >I was an idiot. I knew about std.algorithm.joiner but for some reason
> >didn't think of it at the time. In any case, crossProduct doesn't
> >make any sense to me... I don't see what it's got to do with
> >flattening nested ranges.
> 
> I meant the resulting range spans the cross product (all combinations)
> of the passed-in ranges.

Hmm. We must be using a different set of terms, because in my
understanding, a cross product is a binary operation on 3D vectors that
produces a perpendicular vector. The product that produces all
combinations of a set is known as a Cartesian product to me.


> On another subject, I think this can be done with only input ranges -
> no need for bidirectional.
[...]

In the case of finite ranges, one of the ranges can be an input range,
but the other must at least be a forward range, since otherwise you
could only traverse it once, so it would be impossible to combine each
element with every element from the other range.

When one of the ranges is infinite, it's obviously not enough for the
other range to be an input range, since you'd have to produce an
infinite number of combinations per element (of the second range) before
moving on to the next element, so you'd never get to it.

It should be possible to do it with both ranges being forward ranges,
but it may not be very efficient -- think about it, for every element in
one range, you need to combine it with every element in the other range,
so when you're at, say, the 100th element of the first range, you still
need to go back to the 1st, 2nd, 3rd, etc., elements in the second
range. But since you can only combine it with a finite number of
elements from the second range (otherwise you'll never get to the 101th
element), when you get to the 101th element, you still haven't produced
some of the combinations of the 100th element yet. So you'll end up
needing an increasing number of save points in order to get to every
possible combination -- possible but not efficient.

Using the Cantor method we can allow one range to be a forward range,
and the second a range whose take(n) is a reversible range (I was wrong
before: the second range doesn't need to be bidirectional, it works as
long as take(n) returns a reversible range). This gives us constant
space complexity. I'd say this is a pretty good solution.


T

-- 
Век живи - век учись. А дураком помрёшь.