next_permutation and cartesian product for ranges?

H. S. Teoh hsteoh at quickfur.ath.cx
Wed Oct 10 09:30:22 PDT 2012


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


More information about the Digitalmars-d mailing list