如何在Java中按特定顺序生成多列表的排列组合

引言

在编程中，我们经常需要从多个列表中生成所有可能的组合，即排列组合。标准的递归方法通常会按照输入列表的顺序生成结果，例如，如果输入列表是 [a, b]、[x, y, z]、[1, 2]，则默认输出通常是 [a, x, 1], [a, x, 2], [a, y, 1], ...。然而，有时我们需要一种特定的、非默认的输出顺序。本教程将指导您如何通过巧妙地调整输入和后处理步骤来实现这种自定义的排列顺序。

问题描述与初始方法

假设我们有三个字符串列表：

List first = Arrays.asList("a", "b");
List second = Arrays.asList("X", "Y", "Z");
List third = Arrays.asList("1", "2");

一个典型的递归方法来生成这些列表的所有组合可能如下所示：

public static void permute(List> lists, List> result, int depth, String current) {
    // 当递归深度达到列表总数时，表示一个组合已完成
    if (depth == lists.size()) {
        // 将当前组合字符串转换为List
        List current_list = current.chars()
                                          .mapToObj(e -> Character.toString((char)e))
                                          .collect(Collectors.toList());
        result.add(current_list); // 添加到结果集
        return;
    }

    // 遍历当前深度的列表中的所有元素
    for (int i = 0; i < lists.get(depth).size(); i++) {
        // 递归调用，深度加1，并将当前元素添加到组合字符串
        permute(lists, result, depth + 1, current + lists.get(depth).get(i));
    }
}

如果我们将 first、second、third 依次添加到 lists 中，并调用上述方法，我们会得到以下结果：

[[a, X, 1], [a, X, 2], [a, Y, 1], [a, Y, 2], [a, Z, 1], [a, Z, 2], [b, X, 1], [b, X, 2], [b, Y, 1], [b, Y, 2], [b, Z, 1], [b, Z, 2]]

这个结果是按 first、second、third 的顺序进行组合的，即 first 元素变化最慢，third 元素变化最快。

立即学习“Java免费学习笔记（深入）”；

目标输出顺序分析

现在，假设我们期望的输出顺序是这样的：

[[a,X, 1], [b, X, 1], [a, Y, 1], [b, Y, 1], [a, Z, 1], [b, Z, 1], [a, X, 2], [b, X, 2], [a, Y, 2], [b, Y, 2], [a, Z, 2], [b, Z, 2]]

仔细观察这个目标顺序，我们可以发现以下模式：

绘蛙AI修图

绘蛙平台AI修图工具，支持手脚修复、商品重绘、AI扩图、AI换色

下载

1. 最外层（变化最慢）的元素来自 third 列表（先是 1 的所有组合，然后是 2 的所有组合）。
2. 中间层变化的元素来自 second 列表（在 third 元素固定后，second 元素依次为 X, Y, Z）。
3. 最内层（变化最快）的元素来自 first 列表（在 second 和 third 元素固定后，first 元素依次为 a, b）。

这表明，如果我们希望在递归过程中，third 列表的元素作为最外层循环，second 列表的元素作为中间循环，first 列表的元素作为最内层循环，那么在传递给 permute 方法的 lists 参数中，它们的顺序应该是 third -> second -> first。

解决方案：调整输入顺序与局部反转

为了实现目标输出，我们需要对原始方法进行两处关键修改：

1. 调整输入列表的顺序： 在调用 permute 方法之前，将 third、second、first 列表按照我们期望的遍历顺序添加到 permute 方法的 lists 参数中。
2. 局部反转组合结果： 由于递归是按照 third -> second -> first 的顺序构建 current 字符串的，这意味着 current 字符串的第一个字符是 third 列表的元素，第二个是 second 列表的元素，第三个是 first 列表的元素。为了使最终的 List 元素顺序符合 first -> second -> third 的逻辑显示，我们需要在将 current_list 添加到 result 之前对其进行反转。

完整实现代码

下面是包含这些修改的完整 Java 代码示例：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;

public class PermutationGenerator {

    // 静态变量用于存储所有生成的组合，方便在main方法中访问
    static List> result = new ArrayList<>();

    public static void main(String[] args) {
        List first = Arrays.asList("a", "b");
        List second = Arrays.asList("X", "Y", "Z");
        List third = Arrays.asList("1", "2");

        // 创建一个列表来存储要进行排列组合的列表，并调整其顺序
        List> listsToPermute = new ArrayList<>();

        // 按照期望的遍历顺序添加列表：third -> second -> first
        // 这样在递归中，depth=0 对应 third，depth=1 对应 second，depth=2 对应 first
        listsToPermute.add(new ArrayList<>(third));
        listsToPermute.add(new ArrayList<>(second));
        listsToPermute.add(new ArrayList<>(first));

        // 调用排列组合方法
        permute(listsToPermute, result, 0, "");

        // 打印所有生成的组合
        for(List re : result) {
            System.out.println(re);
        }
    }

    /**
     * 递归方法，用于生成多列表元素的排列组合。
     *
     * @param lists 包含待组合元素的列表的列表。
     * @param result 存储所有生成组合的列表。
     * @param depth 当前递归的深度，对应于 lists 中的索引。
     * @param current 当前正在构建的组合字符串。
     */
    public static void permute(List> lists, List> result, int depth, String current) {
        // 基本情况：当递归深度达到列表总数时，表示一个完整的组合已生成
        if (depth == lists.size()) {
            // 将当前组合字符串转换为List
            List current_list = current.chars()
                                              .mapToObj(e -> Character.toString((char)e))
                                              .collect(Collectors.toList());

            // 关键步骤：反转当前组合列表，使其元素顺序与原始列表的逻辑顺序一致 (first, second, third)
            Collections.reverse(current_list);

            result.add(current_list); // 将反转后的组合添加到结果集
            return;
        }

        // 递归步骤：遍历当前深度的列表中的所有元素
        for (int i = 0; i < lists.get(depth).size(); i++) {
            // 递归调用，深度加1，并将当前元素添加到组合字符串
            // 注意：current 字符串的构建顺序是 third -> second -> first
            permute(lists, result, depth + 1, current + lists.get(depth).get(i));
        }
    }
}

代码解释与注意事项

1. main 方法中的调整：
   • listsToPermute 的构建顺序至关重要。我们将 third、second、first 依次添加到 listsToPermute 中。这意味着当 permute 方法开始执行时，depth=0 会处理 third 列表，depth=1 处理 second 列表，depth=2 处理 first 列表。这决定了递归遍历的优先级，使得 third 列表的元素变化最慢，first 列表的元素变化最快。
2. permute 方法中的 Collections.reverse(current_list)：
   • 当 depth == lists.size() 条件满足时，current 字符串已经包含了 third 元素、second 元素和 first 元素的组合，但它们的顺序是 third_elem + second_elem + first_elem。
   • 例如，对于组合 [a, X, 1]，在 current 字符串中它会是 "1Xa"。
   • 通过 current.chars().mapToObj(...).collect(...) 转换为 List 后，它会是 ["1", "X", "a"]。
   • 为了得到 ["a", "X", "1"] 这样的期望输出，我们需要对 current_list 进行反转。Collections.reverse() 方法正是完成了这一任务，将列表中的元素顺序颠倒。

总结

通过本教程，我们学习了如何通过两个关键步骤来控制多列表排列组合的输出顺序：

1. 调整输入列表的传入顺序： 决定了递归遍历的优先级和元素的“变化速度”。将变化最慢的列表放在 lists 的最前面（depth=0），变化最快的列表放在最后面。
2. 对最终组合进行局部反转： 如果递归构建的字符串或列表的元素顺序与最终期望的逻辑顺序相反，则在将其添加到结果集之前进行反转。

这种方法提供了一种灵活的策略，可以根据具体需求生成各种自定义顺序的排列组合，而不仅仅局限于默认的字典序输出。理解递归的工作原理以及如何操纵输入和输出是解决此类问题的关键。