Java：列表列表的笛卡尔乘积 [英] Java : Cartesian Product of a List of Lists

问题描述

我有一个非常有问题的一般的编程问题，但我的实现是在Java中，所以我将提供我的例子

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

我有一个类如下：

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看起来像这样（伪码，但我想你可以得到想法..）：

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"]};

然后我的String [] []应该如下所示：

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"},
}

我认为这些都是，手动（显然），所以我可能错过了一套，但我认为这说明了我正在做的事情。只要所有独特的组合都存在，每个集合进入什么顺序并不重要。还要清楚，你不知道LHM中有多少个元素，也不知道每个后续向量中有多少个元素。我找到的答案与您想要单个数组中所有元素的每个独特组合的情况相匹配，但没有什么可以适应这一点。如果这是一个问题的确切重复，请在响应中放一个链接，我将关闭这个问题。

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.

推荐答案

尝试这样的一个例子：

public static void generate(int[][] sets) {
    int solutions = 1;
    for(int i = 0; i < sets.length; solutions *= sets[i].length, i++);
    for(int i = 0; i < solutions; i++) {
        int j = 1;
        for(int[] set : sets) {
            System.out.print(set[(i/j)%set.length] + " ");
            j *= set.length;
        }
        System.out.println();
    }
}

public static void main(String[] args) {
    generate(new int[][]{{1,2,3}, {3,2}, {5,6,7}});
}

将打印：

1 3 5
2 3 5
3 3 5
1 2 5
2 2 5
3 2 5
1 3 6
2 3 6
3 3 6
1 2 6
2 2 6
3 2 6
1 3 7
2 3 7
3 3 7
1 2 7
2 2 7
3 2 7

我已经基于（我相信）Knuth的一个 TAOCP 的书（对不起，没有更好的参考...）。

I've implemented the algorithm above based on (I believe) one of Knuth's TAOCP books (sorry, no better reference...).

请注意，我命名为数组设置，但当然不需要持有唯一的元素。我使用它的时候，它们包含了唯一的元素，因此它的名称。

Note that I've named the arrays set, but they needn't hold unique elements, of course. The time I used it, they did contain unique elements, hence the name.

一个1合1的翻译：

import java.util.Arrays;
import java.util.LinkedHashMap;
import java.util.Vector;

public class Foo {

    private LinkedHashMap<String, Vector<String>> dataStructure;

    public Foo(LinkedHashMap<String, Vector<String>> dataStructure){
        this.dataStructure = dataStructure;
    }

    public String[][] allUniqueCombinations(){
        int n = dataStructure.keySet().size();
        int solutions = 1;

        for(Vector<String> vector : dataStructure.values()) {
            solutions *= vector.size();            
        }

        String[][] allCombinations = new String[solutions + 1][];
        allCombinations[0] = dataStructure.keySet().toArray(new String[n]);

        for(int i = 0; i < solutions; i++) {
            Vector<String> combination = new Vector<String>(n);
            int j = 1;
            for(Vector<String> vec : dataStructure.values()) {
                combination.add(vec.get((i/j)%vec.size()));
                j *= vec.size();
            }
            allCombinations[i + 1] = combination.toArray(new String[n]);
        }

        return allCombinations;
    }

    public static void main(String[] args) {
        LinkedHashMap<String, Vector<String>> data = new LinkedHashMap<String, Vector<String>>();
        data.put("foo", new Vector<String>(Arrays.asList("1", "2", "3")));
        data.put("bar", new Vector<String>(Arrays.asList("3", "2")));
        data.put("baz", new Vector<String>(Arrays.asList("5", "6", "7")));

        Foo foo = new Foo(data);

        for(String[] combination : foo.allUniqueCombinations()) {
            System.out.println(Arrays.toString(combination));            
        }
    }
}

如果您运行上述课程，打印如下：

If you run the class above, the following is printed:

[foo, bar, baz]
[1, 3, 5]
[2, 3, 5]
[3, 3, 5]
[1, 2, 5]
[2, 2, 5]
[3, 2, 5]
[1, 3, 6]
[2, 3, 6]
[3, 3, 6]
[1, 2, 6]
[2, 2, 6]
[3, 2, 6]
[1, 3, 7]
[2, 3, 7]
[3, 3, 7]
[1, 2, 7]
[2, 2, 7]
[3, 2, 7]

这篇关于Java：列表列表的笛卡尔乘积的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！