October 10, 2012Re: 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