next_permutation and cartesian product for ranges?

[Andrei Alexandrescu]

On 10/10/12 10:27 AM, H. S. Teoh wrote:
> 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.

Same thing for sets. I agree using Cartesian is more precise.

http://www.transtutors.com/math-homework-help/set-theory/cartesian-product.aspx

>> 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.

Yah.

> 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.

Something like that.

> 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.

I'm still thinking of Cantor's method, just a different schedule of 
spanning the triangle. Multiple save points are necessary. Consider you 
span the triangle in squares of increasing side. For each side size you 
first walk along one dimension, then walk along the other.


Andrei