Original issue created by tomas.zalusky on 2012-02-24 at 05:44 PM

Hi,

the current implementation of Sets.cartesianProduct returns Lists where the first value changes most quickly and last value most slowly.
If ordering inside Set matters (in case of some ordered set implementation) and one makes the cartesian product of set with itself, the iteration order is not stable.

My use case:

I have to find a best Hamiltonian path in a (not so large) graph, given a restriction that the first and last node must be in specified subsets of nodes. The algorithm tries all nonequal pairs of possibly-first and possibly-last nodes, evaluates quality of a path and in case of a tie the minimal ordering should decide. Example: (for simplicity edges don't matter and assume all possible paths have same quality)

Let G1 be graph with nodes a,b,c, possiblyFirst=[a,b,c], possiblyLast=[c].
Cartesian products: [[a,c],[b,c],[c,c]].
First successful: [a,c].
Result: [a,b,c].

Let G2 be graph with nodes a,b, possiblyFirst=[a,b], possiblyLast=[a,b].
Cartesian products: [[a,a],[b,a],[a,b],[b,b].
First successful: [b,a].
Result: [b,a].

So removing node c breaks order between a and b.

I am aware of javadoc of cartesianProduct method https://google.github.io/guava/releases/v11.0.1/apidocs/com/google/common/collect/Sets.html#cartesianProduct%28java.util.List%29 stating the order is not guaranteed. Should it rather do? Other methods (difference, union, intersection) do it too.

Moreover, in the javadoc example Sets.cartesianProduct(ImmutableSet.of(1, 2),ImmutableSet.of("A", "B", "C")) the state result is in different order that in reality which is little confusing, however I admit the "returns a set containing six lists:" statement is precise.

If Guava team is open to such a change, I would try to add a patch of Sets.CartesianSet.

The current workaround is Sets.cartesianProduct(originalList.reverse()); and reverse resulting lists back.

Thank you

Tomas Zalusky