digitalmars.D - Re: next_permutation and cartesian product for ranges?
- "H. S. Teoh" <hsteoh quickfur.ath.cx> Oct 10 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
Oct 10 2012