http://d.puremagic.com/issues/show_bug.cgi?id=7128

           Summary: Cartesian product of ranges
           Product: D
           Version: D2
          Platform: All
        OS/Version: All
            Status: NEW
          Severity: enhancement
          Priority: P2
         Component: Phobos
        AssignedTo: nobody@puremagic.com
        ReportedBy: bearophile_hugs@eml.cc


--- Comment #0 from bearophile_hugs@eml.cc 2011-12-18 09:20:32 PST ---
It's useful to have a cartesian product of ranges, like a std.range.product:

http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D.learn&article_id=31050

http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D.learn&article_id=31054


See also the handy design of Python itertools.product:

http://docs.python.org/library/itertools.html#itertools.product

itertools.product(*iterables[, repeat]) Cartesian product of input iterables.

product('ABCD', 'xy') --> Ax Ay Bx By Cx Cy Dx Dy
product(range(2), repeat=3) --> 000 001 010 011 100 101 110 111

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=7128



--- Comment #1 from hsteoh@quickfur.ath.cx 2013-01-03 21:29:14 PST ---
https://github.com/D-Programming-Language/phobos/pull/856

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=7128



--- Comment #2 from bearophile_hugs@eml.cc 2013-01-03 21:54:44 PST ---
(In reply to comment #1)
> https://github.com/D-Programming-Language/phobos/pull/856

I guess the Python "repeat" optional argument is not supported:

>>> from itertools import product
>>> list(product("abc", repeat=4))
[('a', 'a', 'a', 'a'), ('a', 'a', 'a', 'b'), ('a', 'a', 'a', 'c'), ('a', 'a',
'b', 'a'), ('a', 'a', 'b', 'b'), ...]

So you have to write:

array(cartesianProduct("abc", "abc", "abc", "abc"))

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=7128



--- Comment #3 from bearophile_hugs@eml.cc 2013-02-05 18:06:03 PST ---
Partially implemented:

http://forum.dlang.org/thread/510f29fd574fd_2193e77ae82545b@sh2.rs.github.com.mail


Currently three or more arguments are not accepted:

import std.stdio, std.algorithm;
void main() {
    cartesianProduct([0,1], [0,1], [0,1]).writeln();
}


Another interesting feature of Python itertools.product() that's missing is the optional "repeat" argument:

>>> from itertools import product
>>> list(product([0,1], repeat=3))
[(0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0),
(1, 1, 1)]
>>>
>>> list(product([0,1], repeat=4))
[(0, 0, 0, 0), (0, 0, 0, 1), (0, 0, 1, 0), (0, 0, 1, 1), (0, 1, 0, 0), (0, 1,
0, 1), (0, 1, 1, 0), (0, 1, 1, 1
), (1, 0, 0, 0), (1, 0, 0, 1), (1, 0, 1, 0), (1, 0, 1, 1), (1, 1, 0, 0), (1, 1,
0, 1), (1, 1, 1, 0), (1, 1, 1,
 1)]

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=7128



--- Comment #4 from hsteoh@quickfur.ath.cx 2013-02-05 18:26:05 PST ---
Now that the basic 2-argument case is working, I'll start looking into the multi-argument case.

The simplest implementation is to just alias the variadic version to the 2-argument version chained to a recursive invocation of itself, but this has the disadvantage that the resulting range will have nested tuples rather than a single tuple of multiple values at the top-level.

For the repeated case, I'm thinking that with D's compile-time introspection, we can probably implement:

auto cartesianPower(int n, R)(R range) { ... }

which returns the cartesian product of n copies of the range with. Or maybe:

auto cartesianProduct(R)(R range, int repeat) { ... }

Don't really know which API is better.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=7128



--- Comment #5 from hsteoh@quickfur.ath.cx 2013-02-05 18:32:23 PST ---
P.S. on second thoughts, probably the second version is not implementable right now because we can't compute the type of the return value at runtime.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=7128



--- Comment #6 from bearophile_hugs@eml.cc 2013-02-05 18:34:12 PST ---
(In reply to comment #4)

Thank you for your work. I use cartesian often enough in Python.

> but this has
> the disadvantage that the resulting range will have nested tuples rather than a
> single tuple of multiple values at the top-level.

I think this solution is not good enough.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=7128



--- Comment #7 from bearophile_hugs@eml.cc 2013-02-05 18:37:32 PST ---
(In reply to comment #5)
> P.S. on second thoughts, probably the second version is not implementable right now because we can't compute the type of the return value at runtime.

To support this API this cartesianProduct has to return a range of dynamic arrays(this is possible because the types of the items inside the arrays is uniform), but the others return a range of tuples...

auto cartesianProduct(R)(R range, int repeat) { ... }

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=7128



--- Comment #8 from bearophile_hugs@eml.cc 2013-02-07 09:33:02 PST ---
See also Issue 6788

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=7128



--- Comment #9 from hsteoh@quickfur.ath.cx 2013-02-07 09:41:05 PST ---
*** Issue 6788 has been marked as a duplicate of this issue. ***

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------