列表列表的笛卡尔积

data-structures java nested-loops recursion linkedhashmap

2022-09-01 22:39:53

我有一个问题，实际上是一个通用的编程问题，但我的实现是用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 生成一个嵌套数组，该数组表示 LHM 中所有值的每个唯一组合。例如，如果我的LHM看起来像这样（伪代码，但我认为你可以得到这个想法..）：LinkedHashMap

{"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 中有多少个元素。我已经找到了与您希望单个数组中所有元素的每个唯一组合相匹配的答案，但没有一个完全符合这种情况。

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

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

这将打印：

我已经根据（我相信）Knuth的TAOCP书籍之一实现了上述算法（在评论中@chikitin有一个更具体的参考：它在

答案 2