[Issue 7128] Cartesian product of ranges

[d-bugmail--- via Digitalmars-d-bugs]

https://issues.dlang.org/show_bug.cgi?id=7128

--- Comment #27 from tyckesak  ---
*** Issue 6788 has been marked as a duplicate of this issue. ***

--

[Issue 7128] Cartesian product of ranges

[d-bugmail--- via Digitalmars-d-bugs]

https://issues.dlang.org/show_bug.cgi?id=7128

tyckesak  changed:

   What|Removed |Added

 Status|REOPENED|RESOLVED
 CC||jos...@live.de
 Resolution|--- |FIXED

--- Comment #28 from tyckesak  ---
Considered done with the introduction of
`std.algorithm.setops.cartesianProduct`

--

[Issue 7128] Cartesian product of ranges

[via Digitalmars-d-bugs]

https://issues.dlang.org/show_bug.cgi?id=7128

--- Comment #26 from Andrei Alexandrescu  ---
@greenify thanks, I'v bootcamped it so it gets looked at again :o).

--

[Issue 7128] Cartesian product of ranges

[via Digitalmars-d-bugs]

https://issues.dlang.org/show_bug.cgi?id=7128

--- Comment #25 from greenify  ---
@andralex: as there was no positive decision on the PR it's now part of Mir
(http://docs.mir.dlang.io/latest/mir_combinatorics.html) with a couple of other
goodies (more functions, allocator support). 

So there is no need to use this as bootcamp task as this is already done and
reviewed and it was only blocked by your "No" a couple of months ago. If you
want to have it in Phobos, I am happy to reopen the regarding PR again ;-)

--

[Issue 7128] Cartesian product of ranges

[via Digitalmars-d-bugs]

https://issues.dlang.org/show_bug.cgi?id=7128

Andrei Alexandrescu  changed:

   What|Removed |Added

   Keywords||bootcamp

--

[Issue 7128] Cartesian product of ranges

[via Digitalmars-d-bugs]

https://issues.dlang.org/show_bug.cgi?id=7128

--- Comment #24 from greenify  ---
As @quickfur linked to this:

I put a PR for cartesianProduct together - so maybe this issue can be tackled
:)

https://github.com/D-Programming-Language/phobos/pull/4026

--

[Issue 7128] Cartesian product of ranges

[via Digitalmars-d-bugs]

https://issues.dlang.org/show_bug.cgi?id=7128

greenify  changed:

   What|Removed |Added

 CC||greeen...@gmail.com
   Assignee|nob...@puremagic.com|greeen...@gmail.com

--

[Issue 7128] Cartesian product of ranges

[via Digitalmars-d-bugs]

https://issues.dlang.org/show_bug.cgi?id=7128

--- Comment #19 from bearophile_h...@eml.cc ---
This pull has fixed the most glaring problems of cartesianProduct:
https://github.com/D-Programming-Language/phobos/pull/2276

I leave this ER open for the repeat argument request (compile time argument
or run-time one), and for the desire of benchmarking.

--

[Issue 7128] Cartesian product of ranges

[d-bugmail]

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



--- Comment #17 from bearophile_h...@eml.cc 2013-02-09 03:17:30 PST ---
(In reply to comment #16)
 Hmm, you're right. The cartesian power has the advantage that the output will
 be tuples of homogenous elements, so we can use arrays instead of tuples, 
 which
 will allow runtime variation.

Right.

On the other hand if we do this, cartesianProduct() and cartesianPower() will
have different type (this means: they will be ranges that yield different class
of types, the first tuples, the second dynamic arrays). This requires people
that want to use such functions to remember this difference (a broken
symmetry). So this design decision has a little associated cost.

But in the end I prefer cartesianPower() to yield dynamic arrays because
dynamic arrays are more flexible, they offer both the size_t n to be a run-time
value, and dynamic arrays are more usable than tuples in D (I think tuples are
not ranges). Python itertools.cartesian doesn't have such problems because
Python is dynamically typed, so the items that itertools.cartesian are usable
like normal sequences (unlike D tuples).

If you use a cartesianProduct() to produce the data for the Bulls and cows
game you write something like:


auto d9 = 123456789d.dup;
auto choices = cartesianProduct(d9, d9, d9, d9)
   .map!(t = [t.tupleof])()
   .filter!(a = a.sort().uniq().walkLength() == 4)()
   .array();


The map!(t = [t.tupleof])() is used to convert a tuple into a dynamic array,
so later on it you can perform more processing, with a filter() and an array().
D tuples don't play very well with ranges.

- - - - - - - - - - -

Maybe std.typecons.Tuple should define a handy std.typecons.Tuple.arrayof
attribute (that returns [this.tupleof]) when all the items of the tuple have
the same type.

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

[Issue 7128] Cartesian product of ranges

[d-bugmail]

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



--- Comment #18 from bearophile_h...@eml.cc 2013-02-09 03:22:18 PST ---
Extra on cartesianProduct: maybe you should add a little benchmark, to be sure
the way you have implemented the variadic cartesianProduct() (with the
flattening of nested tuples) is efficient/fast enough:

enum N = 10; // Change me.
int[] items = iota(N).array();
immutable len = cartesianProduct(items, items, items, items,
items).walkLength();

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

[Issue 7128] Cartesian product of ranges

[d-bugmail]

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



--- Comment #15 from bearophile_h...@eml.cc 2013-02-08 04:26:20 PST ---
(In reply to comment #14)
 The power must be a compile-time parameter, otherwise it won't compile.

I think it's possible to create a range like this:

auto cartesianPower(R)(R range, in size_t n) { ... }


If you call it with:
int n = 3;
auto result = cartesianPower([0, 1], n).array();


result should be:

[[0, 0, 0], [1, 0, 0], [0, 1, 0], [1, 1, 0], [0, 0, 1], [1, 0, 1], [0, 1, 1],
[1, 1, 1]]



One use case: generate dstrings (dchar[][]) for a Bulls and Cows game, where
they need to be composed of N distinct nonzero digits:


dchar[][] genCases(in size_t nDigits) {
  return cartesianPower(123456789d.dup, nDigits)
 .filter!(a = a.sort().uniq().walkLength() == nDigits)()
 .array();
}


So genCases(4).writeln() should print:

[4321, 5321, 6321, 7321, 8321, 9321, 3421,
5421, 6421, 7421, 8421, 9421, 3521, 4521,
6521, 7521, 8521, 9521, 3621, 4621, 5621,
7621, 8621, 9621, 3721, 4721, 5721, 6721,
8721, 9721, 3821, 4821, 5821, 6821, 7821,
9821, 3921, 4921, 5921, ...]

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

[Issue 7128] Cartesian product of ranges

[d-bugmail]

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



--- Comment #16 from hst...@quickfur.ath.cx 2013-02-08 20:32:06 PST ---
Hmm, you're right. The cartesian power has the advantage that the output will
be tuples of homogenous elements, so we can use arrays instead of tuples, which
will allow runtime variation.

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

[Issue 7128] Cartesian product of ranges

[d-bugmail]

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



--- Comment #8 from bearophile_h...@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: ---

[Issue 7128] Cartesian product of ranges

[d-bugmail]

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



--- Comment #9 from hst...@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: ---

[Issue 7128] Cartesian product of ranges

[d-bugmail]

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



--- Comment #10 from bearophile_h...@eml.cc 2013-02-07 10:17:40 PST ---
(In reply to comment #9)
 *** Issue 6788 has been marked as a duplicate of this issue. ***

It's not a dupe.

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

[Issue 7128] Cartesian product of ranges

[d-bugmail]

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



--- Comment #11 from hst...@quickfur.ath.cx 2013-02-07 12:36:01 PST ---
https://github.com/D-Programming-Language/phobos/pull/1120

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

[Issue 7128] Cartesian product of ranges

[d-bugmail]

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


Andrei Alexandrescu and...@erdani.com changed:

   What|Removed |Added

 Status|NEW |RESOLVED
 CC||and...@erdani.com
 Resolution||FIXED


--- Comment #12 from Andrei Alexandrescu and...@erdani.com 2013-02-07 
15:01:41 PST ---
https://github.com/D-Programming-Language/phobos/pull/1120

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

[Issue 7128] Cartesian product of ranges

[d-bugmail]

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



--- Comment #13 from bearophile_h...@eml.cc 2013-02-07 18:01:50 PST ---
The repetition number is not yet supported:

auto cartesianProduct(size_t nRepetitions=0, R)(R range) { ... }

If the name if the function is different, then it's even possible to support
this API, where it returns a range of dynamic arrays:

auto cartesianPower(R)(R range, in size_t n) { ... }

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

[Issue 7128] Cartesian product of ranges

[d-bugmail]

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


hst...@quickfur.ath.cx changed:

   What|Removed |Added

 Status|RESOLVED|REOPENED
 Resolution|FIXED   |


--- Comment #14 from hst...@quickfur.ath.cx 2013-02-07 21:14:59 PST ---
The power must be a compile-time parameter, otherwise it won't compile. The
variadic cartesianProduct only works if the number of arguments is known at
compile-time.

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

[Issue 7128] Cartesian product of ranges

[d-bugmail]

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



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

http://forum.dlang.org/thread/510f29fd574fd_2193e77ae825...@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: ---

[Issue 7128] Cartesian product of ranges

[d-bugmail]

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



--- Comment #5 from hst...@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: ---

[Issue 7128] Cartesian product of ranges

[d-bugmail]

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



--- Comment #6 from bearophile_h...@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: ---

[Issue 7128] Cartesian product of ranges

[d-bugmail]

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



--- Comment #1 from hst...@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: ---

[Issue 7128] Cartesian product of ranges

[d-bugmail]

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



--- Comment #2 from bearophile_h...@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: ---