Add Lists.cartesianProduct

[gissuebot]

Original issue created by jmkristian on 2012-02-27 at 08:15 PM

---

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);

[gissuebot]

Original comment posted by wasserman.louis on 2012-02-27 at 08:21 PM

---

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?

[gissuebot]

Original comment posted by jmkristian on 2012-02-28 at 06:01 AM

---

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);

[gissuebot]

Original comment posted by kevinb@google.com on 2012-03-01 at 05:49 PM

---

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.

---

Status: Acknowledged

[gissuebot]

Original comment posted by kevinb@google.com on 2012-03-16 at 09:19 PM

---

(No comment entered for this change.)

---

Labels: Type-Enhancement

[gissuebot]

Original comment posted by phwendler on 2012-05-01 at 06:13 PM

---

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?

[gissuebot]

Original comment posted by wasserman.louis on 2012-05-03 at 03:32 PM

---

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.

---

Labels: Package-Collect

[gissuebot]

Original comment posted by tomas.zalusky on 2012-05-07 at 07:29 AM

---

If the feature will be implemented, will it address the most-significant-to-least-significant issue? ( https://github.com/google/guava/issues/908 )

[gissuebot]

Original comment posted by kevinb@google.com on 2012-05-07 at 05:18 PM

---

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.

[gissuebot]

Original comment posted by kevinb@google.com on 2012-05-30 at 07:45 PM

---

(No comment entered for this change.)

---

Labels: -Type-Enhancement, Type-Addition

[gissuebot]

Original comment posted by kevinb@google.com on 2012-06-22 at 06:16 PM

---

(No comment entered for this change.)

---

Status: Research

[gissuebot]

Original comment posted by wasserman.louis on 2012-12-25 at 05:54 PM

---

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

[gissuebot]

Original comment posted by hartmetz on 2013-02-25 at 09:06 PM

---

yes please expose it!

one more upvote for order preserving Cartesian Product

[gissuebot]

Original comment posted by hartmetz on 2013-02-25 at 10:33 PM

---

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.

[gissuebot]

Original comment posted by guznik on 2014-06-19 at 09:12 AM

---

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

[PhilippWendler]

In the meantime, more and more possible uses of this have appeared in our project, and for several we cannot use the Set version. So please expose this.

[Xaerxess]

I believe Lists.cartesianProduct was added in 19.0.

[cpovirk]

Thanks for pointing that out.