1. 多列表元素组合的常见递归方法
在编程中，我们经常需要从多个独立的列表中各取一个元素，组合成一个新的序列。例如，给定三个列表 first、second 和 third：
List<String> first = Arrays.asList("a", "b");
List<String> second = Arrays.asList("X", "Y", "Z");
List<String> third = Arrays.asList("1", "2");一个典型的递归方法用于生成所有这些组合，通常会按照列表的定义顺序进行遍历和拼接。以下是一个示例的递归实现，它以深度优先的方式构建组合：
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;
public class PermutationGenerator {
// 递归方法，用于生成所有组合
public static void permute(List<List<String>> lists, List<List<String>> result, int depth, String current) {
// 当递归深度达到列表总数时，表示一个完整的组合已生成
if (depth == lists.size()) {
// 将当前组合字符串转换为List<String>并添加到结果集
List<String> 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));
}
}
public static void main(String[] args) {
List<String> first = Arrays.asList("a", "b");
List<String> second = Arrays.asList("X", "Y", "Z");
List<String> third = Arrays.asList("1", "2");
// 按照自然顺序将列表添加到输入集合
List<List<String>> inputLists = new ArrayList<>();
inputLists.add(first);
inputLists.add(second);
inputLists.add(third);
List<List<String>> allPermutations = new ArrayList<>();
permute(inputLists, allPermutations, 0, "");
System.out.println("原始方法生成的组合顺序:");
for (List<String> p : allPermutations) {
System.out.println(p);
}
}
}运行上述代码，将得到以下输出：
原始方法生成的组合顺序: [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。这意味着 third 列表的元素变化最快，而 first 列表的元素变化最慢。
2. 理解目标输出顺序
在某些场景下，我们可能需要一种非标准的组合输出顺序。例如，我们希望得到以下结果：
[[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]]
仔细分析这个目标顺序，我们可以发现其规律与原始方法截然不同：
- third 列表的元素 (1, 2) 变化最慢。它首先固定为 1，生成所有 first 和 second 的组合后，再固定为 2。
- first 列表的元素 (a, b) 变化最快。在 third 和 second 的元素固定时，first 的元素会迅速切换。
- second 列表的元素 (X, Y, Z) 变化速度居中。
这表明我们期望的遍历顺序是：最外层循环控制 third 列表，中间层控制 second 列表，最内层控制 first 列表。
3. 实现特定排列顺序的策略
要实现这种“反向”的遍历顺序，我们需要对原始的递归方法进行两处关键修改：
3.1 调整输入列表的顺序
递归方法 permute(lists, ...) 是按照 lists 中列表的顺序进行深度优先遍历的。如果我们将 third 列表放在 lists 的第一个位置（索引 0），second 放在第二个位置（索引 1），first 放在第三个位置（索引 2），那么递归将首先遍历 third 列表的元素，然后是 second，最后是 first。
这意味着在递归的底层（depth == lists.size()），current 字符串的构建顺序将是 third_element + second_element + first_element。
3.2 对结果进行反转
由于我们调整了输入列表的顺序，导致 current 字符串的元素拼接顺序与我们最终希望的 [first_element, second_element, third_element] 顺序是相反的。因此，在将 current 字符串转换为 List
例如，如果输入列表顺序是 [third, second, first]，并且 third 元素是 1，second 元素是 X，first 元素是 a，那么 current 字符串会是 "1Xa"。我们希望的输出是 [a, X, 1]，所以需要将由 "1Xa" 拆分得到的 ["1", "X", "a"] 反转为 ["a", "X", "1"]。
4. 优化后的代码实现
结合上述策略，以下是修改后的 PermutationGenerator 类，它能够生成目标顺序的组合：
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections; // 引入Collections类用于反转
import java.util.List;
import java.util.stream.Collectors;
public class PermutationGenerator {
// 静态变量用于存储结果，方便在main方法中访问
static List<List<String>> result = new ArrayList<>();
public static void main(String args[]) {
List<String> first = Arrays.asList("a", "b");
List<String> second = Arrays.asList("X", "Y", "Z");
List<String> third = Arrays.asList("1", "2");
List<List<String>> permuteInputLists = new ArrayList<>();
// 关键修改1: 调整输入列表的顺序
// 将third放在第一个，second放在第二个，first放在第三个
// 这样，递归将优先遍历third，其次second，最后first
permuteInputLists.add(new ArrayList<>(third));
permuteInputLists.add(new ArrayList<>(second));
permuteInputLists.add(new ArrayList<>(first));
// 调用递归方法
permute(permuteInputLists, result, 0, "");
System.out.println("调整顺序后生成的组合:");
for(List<String> re : result) {
System.out.println(re);
}
}
public static void permute(List<List<String>> lists, List<List<String>> result, int depth, String current) {
if (depth == lists.size()) {
List<String> current_list = current.chars()
.mapToObj(e -> Character.toString((char)e))
.collect(Collectors.toList());
// 关键修改2: 反转生成的列表，使其元素顺序符合期望
Collections.reverse(current_list);
result.add(current_list);
return;
}
for (int i = 0; i < lists.get(depth).size(); i++) {
permute(lists, result, depth + 1, current + lists.get(depth).get(i));
}
}
}5. 运行与结果验证
执行上述优化后的代码，将得到以下输出：
调整顺序后生成的组合: [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]
这个结果与我们期望的目标输出完全一致，成功实现了自定义的组合输出顺序。
6. 注意事项与总结
- 理解递归的遍历顺序： 递归方法通常会按照输入列表的顺序进行深度优先遍历。理解这一点是控制输出顺序的基础。
- 输入顺序与输出顺序的映射： 通过调整输入给递归方法的列表顺序，可以改变元素在组合中“变化快慢”的优先级。例如，将变化最慢的列表放在 inputLists 的最前面，变化最快的列表放在最后面。
- 结果后处理的重要性： 当输入顺序被调整以影响遍历逻辑时，最终生成的组合元素顺序可能与期望的显示顺序不符。此时，对结果进行反转或其他形式的后处理是必要的，以校正元素的最终呈现位置。
- 代码可读性： 尽管这种方法有效，但在实际项目中，应确保代码注释清晰，解释为何以特定顺序传入列表以及为何需要反转结果，以提高代码的可维护性。
- 通用性： 这种通过调整输入顺序和结果后处理来控制排列组合输出顺序的技巧，可以推广到更复杂的列表组合场景中，为开发者提供了灵活的控制能力。
通过本文的探讨，我们不仅掌握了如何生成多列表元素的组合，更重要的是学会了如何通过巧妙地调整输入参数和对结果进行后处理，来精确控制这些组合的输出顺序，从而满足各种特定的需求。这种对算法细节的深入理解和灵活运用，是编写高效且符合业务逻辑代码的关键。
