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

我需要从我的 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 的评论中有更具体的引用:它在 } >

请注意，我已将数组命名为 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]