## digitalmars.D - Re: next_permutation and cartesian product for ranges?

```On Wed, Oct 10, 2012 at 10:59:32AM -0400, Andrei Alexandrescu wrote:
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 another subject, I think this can be done with only input ranges
- no need for bidirectional.

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.

On Wed, Oct 10, 2012 at 11:00:43AM -0400, Andrei Alexandrescu wrote:
On 10/10/12 10:59 AM, Andrei Alexandrescu wrote:
I'm still thinking of Cantor's method, just a different schedule of
spanning the triangle. Multiple save points are necessary.

I meant "Multiple save points are NOT necessary."

In the interest of not stalling the inclusion of a Cartesian product in
Phobos any longer (since the original discussion was apparently some
*years* ago), I propose that we check in the current implementation of
the Cantor method first, and then think about how we can improve it.
Since the improved version will *relax* the requirement on the argument
ranges, any code based on the current method shouldn't break with the
improved version once we figure out how to do it.

T

--
He who sacrifices functionality for ease of use, loses both and deserves
neither. -- Slashdotter
```
Oct 10 2012