11

假设我有两组数字：

{1, 2, 3},
{4, 5}

我想创建一个输出以下 6 种组合的算法（在 Java 中）：

1,4
1,5
2,4
2,5
3,4
3,5

每个组内可以有任意数量的组和任意数量的成员。所以在上面的例子中，有 2 个组，第一个组有 3 个成员，第二个组有 2 个成员。另一个示例如下（3 个组，第一组 3 个成员，第二组和第三组 2 个成员）：

{1, 2, 3},
{4, 5},
{6, 7}

这将产生以下 12 种组合：

1,4,6
1,4,7
1,5,6
1,5,7

2,4,6
2,4,7
2,5,6
2,5,7

3,4,6
3,4,7
3,5,6
3,5,7

我怎样才能在 Java 中做到这一点？我正在尝试使用递归，并且我已经看过一个类似的问题，但我仍然做不到。谢谢您的帮助！（PS这不是家庭作业）

4

5 回答 5

16

有点无聊，决定试一试。应该正是您需要的：

public static void main(String args[]) {
    ArrayList<int[]> input = new ArrayList<int[]>();
    input.add(new int[]{1, 2, 3});
    input.add(new int[]{4, 5});
    input.add(new int[]{6, 7});

    combine(input, new int[input.size()], 0);
}

private static void combine(ArrayList<int[]> input, int[] current, int k) {
    if (k == input.size()) {
        for (int i = 0; i < k; i++) {
            System.out.print(current[i] + " ");
        }
        System.out.println();
    } else {
        for (int j = 0; j < input.get(k).length; j++) {
            current[k] = input.get(k)[j];
            combine(input, current, k + 1);
        }
    }
}
于 2012-04-21T19:45:14.960 回答
9

如果您可以使用库，那么Guava 的 Sets.cartesianProduct(List<Set<E>>)功能正是您想要的。（披露：我为 Guava 做出了贡献。）

于 2012-04-21T19:49:55.000 回答
6

一种可能的方法（不一定是最有效的）可能是采取分而治之的方法。查找两个组的所有排列相对简单（最愚蠢的方法就是嵌套 for 循环）。假设您编写了一个名为的函数permute，它permute(A,B)在 A（例如 {(1), (2), (3)}）和 B（例如 {(4), (5)} 是一组数字，它返回所有A & B 作为单个组的排列（例如 {(1,4), (1,5), (2,4), (2,5), (3,4), (3,5)}） .

因此，当您有 N 个组而不是 2 个时，最简单的做法就是挑出问题的一小部分。假设您有 A、B 和 C 组。与其单独担心它们，不如将其视为：

permute(permute(A,B),C)

首先找到 A 和 B 的所有排列。一旦你有了这个结果，用 C 找到这个结果的所有排列。四个组 A、B、C、D 可能看起来像：

permute(permute(permute(A,B),C),D)

等等。在此过程中的每一步，您都会获取当前的排列结果，并将其与作为输入的组列表中的下一个组进行排列。您一次只能组合两个组，因此算法不必根据您作为输入获得的组数而改变。

当您进行递归时，您需要回答几个主要问题：

  1. 你能递归地将问题分解成更小、更容易解决的问题吗？我认为上面的例子证明你可以。

  2. 基本情况是什么？导致递归停止和展开的解决方案是什么？它通常应该是一些非常简单的东西，你的递归可以朝着这个方向努力。在这种情况下，它可能归结为permute(A,{}){} 是空集。

  3. 什么是递归案例？你将如何分解问题的一部分并递归到问题的较小子集上？我认为最初的解释为您提供了一种可能这样做的方法。只需一次拆分一组，然后根据您不断增长的结果对其进行排列。

这个问题当然还有其他解决方案，这只是我脑海中浮现的第一个。随着 N 越来越大，这个算法会变得非常慢，因为它不是很有效。

所以即使你不使用这个解决方案，我希望它能让你走上正轨！

于 2012-04-21T19:32:08.053 回答
1

下面的伪代码怎么样（没有递归）

// Create the initial result filled with the first set of numbers
List result = new List()
For each number in the first set
   result.add(new List(number))

// Iterate over the following sets to permutate over
For each remaining set S
   List newResult = new List()
   For each list L in result
     For each number N in S
       newResult.add(copy of L with N added)
   result = newResult
于 2012-04-21T19:38:26.007 回答
0

您可以使用map 和 reduce方法获得任意数量列表的笛卡尔积。

在线尝试！

List<List<Integer>> lists = Arrays.asList(
        Arrays.asList(1, 2, 3),
        Arrays.asList(4, 5),
        Arrays.asList(6));

// cartesian product of an arbitrary number of lists
List<List<Integer>> cp = lists.stream()
        // represent each element of a list as a singleton list
        .map(list -> list.stream().map(Arrays::asList)
                // Stream<List<List<String>>>
                .collect(Collectors.toList()))
        // summation of pairs of list into a single list
        .reduce((list1, list2) -> list1.stream()
                // combinations of inner lists
                .flatMap(inner1 -> list2.stream()
                        // concatenate into a single list
                        .map(inner2 -> Stream.of(inner1, inner2)
                                .flatMap(List::stream)
                                .collect(Collectors.toList())))
                // list of combinations
                .collect(Collectors.toList()))
        // otherwise an empty list
        .orElse(Collections.emptyList());

// output
cp.forEach(System.out::println);

输出：

[1, 4, 6]
[1, 5, 6]
[2, 4, 6]
[2, 5, 6]
[3, 4, 6]
[3, 5, 6]

另请参阅：地图值的笛卡尔积

于 2021-07-24T00:52:26.317 回答