Java：列表列表的笛卡尔积
我有一个问题，它确实是一种常见的编程问题，但我的实现是使用Java，所以我将以这种方式提供我的示例
我有这样的课程：
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
}
}
我需要从我的LinkedHashMap生成一个嵌套数组，它表示LHM中所有值的每个唯一组合。 例如，如果我的LHM看起来像这样（伪码，但我认为你可以得到这个想法..）：
{"foo" => ["1","2","3"], "bar" => ["3","2"], "baz" => ["5","6","7"]};
那么我的String [] []应该看起来像这样：
{
{"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"},
}
我认为这就是所有这些，我手动（明显）做到了这一点，所以我可能错过了一套，但我认为这说明了我想要做的。 只要所有的独特组合都存在，每个集合以什么顺序出现并不重要。 另外要清楚的是，您不知道LHM中有多少个元素，也不知道每个后续Vector中有多少个元素。 我找到了符合您希望单个数组中所有元素的每个独特组合的情况的答案，但没有任何结果恰好符合这一点。 如果这是一个问题的确切副本，请在回复中添加一个链接，我将结束该问题。
更新 - 我改变我的类型为字符串，因为我的真实世界的例子实际上是字符串。 我试图使用整数使示例更具可读性，但迄今为止所得到的答案不能很好地转换为字符串。 所以，是的，他们是数字，但在我的实际情况下，他们将是字符串，除了使用这个特定应用程序的人之外，其他任何人都没有什么意义。 所以，这只是一个抽象而已。
我知道在你需要答案后很久，但不知怎的，我不禁要注意到可以切换到Groovy，至少在Java应用程序的某个部分，并编写一个包装类来匹配所需的接口。 这种排列的Groovy代码是
myListOfLists.combinations()
自从我开始在我的Java应用程序中使用Groovy后，编写它们的速度就会快得多，而且调试/配置它们的方式会更有趣（ehem ...）
如何产生懒惰的产品，即。 只有在访问它时才创建元组？
/**
* 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);
}
并像这样使用它
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);
结果：
[[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]]
作为一个额外的好处，你可以使用它连接所有字符串：
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);
结果：
[aX1, aX2, aX3, aX4, aY1, aY2, aY3, aY4, bX1, bX2, bX3, bX4, bY1, bY2, bY3, bY4, cX1, cX2, cX3, cX4, cY1, cY2, cY3, cY4]