Java : Cartesian Product of a List of Lists
I have a problem that is really kind of a general programming question, but my implementation is in Java, so I will provide my examples that way
I have a class like this:
public class Foo {
LinkedHashMap<String, Vector<String>> dataStructure;
public Foo(LinkedHashMap<String, Vector<String>> dataStructure){
this.dataStructure = dataStructure;
}
public String[][] allUniqueCombinations(){
//this is what I need to do
}
}
I need to generate a nested array from my LinkedHashMap that represents every unique combination of all values in the LHM. for example, if my LHM looks like this (pseudocode, but I think you can get the idea..):
{"foo" => ["1","2","3"], "bar" => ["3","2"], "baz" => ["5","6","7"]};
then my String[][] should look like this:
{
{"foo","bar","baz"},
{"1","3","5"},
{"1","2","5"},
{"1","3","6"},
{"1","2","6"},
{"1","3","7"},
{"1","2","7"},
{"2","3","5"},
{"2","2","5"},
{"2","3","6"},
{"2","2","6"},
{"2","3","7"},
{"2","2","7"},
{"3","3","5"},
{"3","2","5"},
{"3","3","6"},
{"3","2","6"},
{"3","3","7"},
{"3","2","7"},
}
I think that's all of them, I made that manually (obviously) so I might have missed a set, but I think this illustrates what I'm trying to do. It doesn't matter what order each set comes in, so long as all unique combinations are present. Also to be clear, you don't know how many elements are in the LHM, nor how many elements are in each subsequent Vector. I have found answers that match the case where you want every unique combination of all elements in a single array, but nothing that fits this exactly. If this is an exact duplicate of a question however, please put a link in the response and I will close the question.
update - I changed my types to strings because my real world example is actually strings. I was trying to use integers to make the example more readable, but the answers I've gotten so far do not translate well to strings. So, yes they are numbers, but in my actual case, they will be strings that wouldn't make much sense to anyone but people who use this particular application. so, this is just an abstraction of it.
I know it's long after you needed the answer, but somehow I can't refrain from noticing that one could switch to Groovy, at least for some part of a Java application, and write a wrapper class to match the desired interface. The Groovy code for such permutations is
myListOfLists.combinations()
Ever since I started using Groovy in my Java applications, it's much faster to write them and way more interesting to debug/profile them (ehem...)
How about generating the product lazily, ie. only create the tuple when you're accessing it?
/**
* A random access view of tuples of a cartesian product of ArrayLists
*
* Orders tuples in the natural order of the cartesian product
*
* @param T the type for both the values and the stored tuples, ie. values of the cartesian factors are singletons
* While the type of input sets is List<T> with elements being treated as singletons
*
*/
abstract public class CartesianProductView<T> extends AbstractList<T> {
private final List<List<T>> factors;
private final int size;
/**
* @param factors the length of the factors (ie. the elements of the factors argument) should not change,
* otherwise get may not return all tuples, or throw exceptions when trying to access the factors outside of range
*/
public CartesianProductView(List<List<T>> factors) {
this.factors = new ArrayList<>(factors);
Collections.reverse(this.factors);
int acc = 1;
for (Iterator<List<T>> iter = this.factors.iterator(); iter.hasNext(); ) {
acc *= iter.next().size();
}
this.size = acc;
}
@Override
public T get(int index) {
if (index < 0 || index >= size()) {
throw new IndexOutOfBoundsException(String.format("index %d > size() %d", index, size()));
}
T acc = null;
for (Iterator<List<T>> iter = factors.iterator(); iter.hasNext();) {
List<T> set = iter.next();
acc = makeTupleOrSingleton(set.get(index % set.size()), acc);
index /= set.size();
}
return acc;
}
@Override
public int size() {
return size;
}
private T makeTupleOrSingleton(T left, T right) {
if (right == null) {
return left;
}
return makeTuple(left, right);
}
/**
*
* @param left a singleton of a value
* @param right a tuple of values taken from the cartesian product factors, with null representing the empty set
* @return the sum of left and right, with the value of left being put in front
*/
abstract protected T makeTuple(T left, T right);
}
and use it like this
final List<List<String>> l1 = new ArrayList<List<String>>() {{ add(singletonList("a")); add(singletonList("b")); add(singletonList("c")); }};
final List<List<String>> l2 = new ArrayList<List<String>>() {{ add(singletonList("X")); add(singletonList("Y")); }};
final List<List<String>> l3 = new ArrayList<List<String>>() {{ add(singletonList("1")); add(singletonList("2")); add(singletonList("3")); add(singletonList("4")); }};
List<List<List<String>>> in = new ArrayList<List<List<String>>>() {{ add(l1); add(l2); add(l3); }};
List<List<String>> a = new CartesianProductView<List<String>>(in) {
@Override
protected List<String> makeTuple(final List<String> left, final List<String> right) {
return new ArrayList<String>() {{ add(left.get(0)); addAll(right); }};
}
};
System.out.println(a);
The result:
[[a, X, 1], [a, X, 2], [a, X, 3], [a, X, 4], [a, Y, 1], [a, Y, 2], [a, Y, 3], [a, Y, 4], [b, X, 1], [b, X, 2], [b, X, 3], [b, X, 4], [b, Y, 1], [b, Y, 2], [b, Y, 3], [b, Y, 4], [c, X, 1], [c, X, 2], [c, X, 3], [c, X, 4], [c, Y, 1], [c, Y, 2], [c, Y, 3], [c, Y, 4]]
As an added bonus, you can use it join strings all with all:
final List<String> l1 = new ArrayList<String>() {{ add("a"); add("b"); add("c"); }};
final List<String> l2 = new ArrayList<String>() {{ add("X"); add("Y"); }};
final List<String> l3 = new ArrayList<String>() {{ add("1"); add("2"); add("3"); add("4"); }};
List<List<String>> in = new ArrayList<List<String>>() {{ add(l1); add(l2); add(l3); }};
List<String> a = new CartesianProductView<String>(in) {
@Override
protected String makeTuple(String left, String right) {
return String.format("%s%s", left, right);
}
};
System.out.println(a);
The result:
[aX1, aX2, aX3, aX4, aY1, aY2, aY3, aY4, bX1, bX2, bX3, bX4, bY1, bY2, bY3, bY4, cX1, cX2, cX3, cX4, cY1, cY2, cY3, cY4]
上一篇: Java属性是否被有效地弃用？
下一篇: Java：列表列表的笛卡尔积