Java:列表列表的笛卡尔积

Question

我有一个问题,这是一个普通的编程问题,但我的实现是在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
    }
}

我需要从my生成一个嵌套数组,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中有多少元素.我找到的答案与你想要在一个数组中所有元素的每个独特组合的情况相匹配,但没有任何东西完全符合这一点.如果这是问题的完全重复,请在回复中添加一个链接,我将关闭该问题.

更新 - 我将我的类型更改为字符串,因为我的真实世界示例实际上是字符串.我试图使用整数来使示例更具可读性,但到目前为止我得到的答案并没有很好地转换为字符串.所以,是的,它们是数字,但在我的实际情况中,它们将是除了使用这个特定应用程序的人之外没有多大意义的字符串.所以,这只是它的抽象.

Answer 1

尝试这样的事情:

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书(在评论@chikitin有一个更具体的参考:它是在PRE肌束2A节7.2.1.1生成所有n元组,艺术的Knuth的计算机编程,Addison Wesley).

请注意,我已经命名了数组set,但它们当然不需要包含唯一元素.我使用它的时候,它们确实包含了独特的元素,因此得名.

编辑

它几乎是一对一的翻译:

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

如果您运行上面的类,则打印以下内容:

[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]