Add Lists.cartesianProduct

[GoogleCodeExporter]

Please add a method to generate the Cartesian product of an ordered collection 
of ordered collections, iteratively.

I could use this to develop automated tests that iterate over a large number of 
test cases. Sets.cartesianProduct is close to what I need, but dealing in Sets 
is a problem. I need each axis to be an ordered collection that may contain 
duplicate values, so I can generate the right sequence of inputs to test a 
stateful module. (Technically I guess this isn't a Cartesian product, but 
people seem to know what you mean when you call it that.)

It would be nice to have something that can conveniently produce an 
Iterator<Object[]>, which I would use to implement a TestNG DataProvider 
<http://testng.org/doc/documentation-main.html#parameters-dataproviders>.

It would be least surprising to generate results in which the last element 
varies most quickly; e.g. [[a, 1], [a, 2], [a, 3], [b, 1], [b, 2] ...].

The same code might resolve issue 908.

I tentatively suggest adding two public methods to Iterables:

static <B, A extends B> Iterable<B[]> product(Class<B> resultType, Iterable<? 
extends Iterable<? extends A>> axes);

static <B, A extends B> Iterable<B[]> product(Class<B> resultType, Iterable<? 
extends A>... axes);

Original issue reported on code.google.com by jmkrist...@gmail.com on 27 Feb 2012 at 8:15

[GoogleCodeExporter]

I think if we implemented this feature, we wouldn't be returning 
`Iterable<B[]>` but rather an `Iterable<Iterable<A>>`.  Generics and arrays are 
sufficiently complicated that I think we'd rather that users who need arrays do 
the array conversion with Iterables.toArray themselves.

Not sure how I feel about the feature as a whole, though.  I might feel a 
little happier about list products, rather than general iterable products, and 
that seems like it would address your use case, correct?

Original comment by wasserman.louis on 27 Feb 2012 at 8:21

[GoogleCodeExporter]

Yes, a method that returns Iterable<List<B>> or List<List<B>> would meet my 
needs. It would be a nuisance if each axis passed to the method is a List, 
since some of my axes are the results of a database query. I could make an 
adapter.

By the way, someone pointed out that the type parameter A is unnecessary. These 
declarations would be simpler and no worse, I think:

static <B> Iterable<B[]> product(Class<B> resultType, Iterable<? extends 
Iterable<? extends B>> axes);

static <B> Iterable<B[]> product(Class<B> resultType, Iterable<? extends B>... 
axes);

Original comment by jmkrist...@gmail.com on 28 Feb 2012 at 6:01

[GoogleCodeExporter]

Yeah, the List equivalent of our current set cartesian product has forever been 
filed away in the "if it becomes clear that enough people need it" bucket. This 
is the first time anyone's asked for it that I know of.

Original comment by kevinb@google.com on 1 Mar 2012 at 5:49

• Changed title: Add Lists.cartesianProduct
• Changed state: Acknowledged

[GoogleCodeExporter]

Original comment by kevinb@google.com on 16 Mar 2012 at 9:19

• Added labels: Type-Enhancement

[GoogleCodeExporter]

I have a usecase for a cartesian product, too. We have already implemented it 
ourselves, but would use a Guava version if available.

In our case, the input is a List<Collection<? extends A>>. Using Lists for the 
inner collections doesn't really fit our semantics, and it doesn't seem to be 
necessary for the cartesian product, but we could live with it.

While building the List<Collection<? extends A>> we currently pre-calculate the 
size of the cartesian product and use it for short-cutting the 0 and 1 cases 
(which are by far our most common cases), but that would seem a little bit 
weird for a generic method?

Original comment by phwend...@gmail.com on 1 May 2012 at 6:13

[GoogleCodeExporter]

Given the people appearing who want to use this, I think I'm inclined to +1 it 
myself.  But if phwendler desires, perhaps it should be List<List<E>> 
Collections2.cartesianProduct(List<? extends Collection<? extends E>>), which 
would address both lists and general collections.

Original comment by wasserman.louis on 3 May 2012 at 3:32

• Added labels: Package-Collect

[GoogleCodeExporter]

If the feature will be implemented, will it address the 
most-significant-to-least-significant issue? ( 
http://code.google.com/p/guava-libraries/issues/detail?id=908 )

Original comment by tomas.za...@gmail.com on 7 May 2012 at 7:29

[GoogleCodeExporter]

The only connection is that if we add a new cartesianProduct method then that 
issue should be interpreted as applying equally to both of them.

Original comment by kevinb@google.com on 7 May 2012 at 5:18

[GoogleCodeExporter]

Original comment by kevinb@google.com on 30 May 2012 at 7:45

• Added labels: Type-Addition
• Removed labels: Type-Enhancement

[GoogleCodeExporter]

Original comment by kevinb@google.com on 22 Jun 2012 at 6:16

• Changed state: Research

[GoogleCodeExporter]

It's implemented; do we want to expose it?

Original comment by wasserman.louis on 25 Dec 2012 at 5:54

[GoogleCodeExporter]

yes please expose it!

one more upvote for order preserving Cartesian Product

Original comment by hartm...@gmail.com on 25 Feb 2013 at 9:06

[GoogleCodeExporter]

A more refined statement of what I'm looking for is just a cartesian product 
iterator.

Iterators.cartesianIterator<List<E>> (List<? extends List<E>> columns)

P.S. Sorry for spamming with the upvote.

Original comment by hartm...@gmail.com on 25 Feb 2013 at 10:33

[GoogleCodeExporter]

Is there a reason for not exposing this yet? Do you expect breaking changes?

Original comment by guz...@gmail.com on 19 Jun 2014 at 9:12

[GoogleCodeExporter]

This issue has been migrated to GitHub.

It can be found at https://github.com/google/guava/issues/<id>

Original comment by cgdecker@google.com on 1 Nov 2014 at 4:14

• Added labels: MigratedToGitHub

[GoogleCodeExporter]

Original comment by cgdecker@google.com on 1 Nov 2014 at 4:18

• Changed state: Migrated

[GoogleCodeExporter]

Original comment by cgdecker@google.com on 3 Nov 2014 at 9:08

• Added labels: Restrict-AddIssueComment-Commit