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

问题描述

我有一个问题，这实际上是一个一般的编程问题，但我的实现是用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中有多少元素，也不知道后续的每个向量中有多少元素。我已经找到了与以下情况相匹配的答案：您需要单个数组中所有元素的所有唯一组合，但没有一个完全符合这种情况。

更新：我将类型更改为字符串，因为我的真实示例实际上是字符串。我试图使用整数使该示例更具可读性，但到目前为止我得到的答案不能很好地转换为字符串。所以，是的，它们是数字，但在我的实际情况中，它们将是除了使用此特定应用程序的人之外对任何人都没有多大意义的字符串。所以，这只是它的一个抽象。

推荐答案

尝试如下：

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中有更具体的参考：它在Knuth，Addison Wesley著的􏰑􏰒􏰎􏰓􏰔Art of Computer Programming)的前分册2A节7.2.1.1中生成所有n元组)。

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

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