本文介绍如何系统性地生成两个等长集合的全部交叉组合——即每个位置独立选择来自集合a或b的元素，共产生2ⁿ种结果，并提供高效位运算实现与代码示例。
本文介绍如何系统性地生成两个等长集合的全部交叉组合——即每个位置独立选择来自集合a或b的元素，共产生2ⁿ种结果，并提供高效位运算实现与代码示例。
在集合交叉问题中，当给定两个长度均为 n 的集合 A 和 B（如 A = [a, b, c]，B = [d, e, f]），所谓“crossover result”并非传统笛卡尔积，而是一种逐位置二选一的组合生成方式：对结果序列的第 i 个位置，可自由选择 A[i] 或 B[i]，且各位置选择相互独立。因此，总组合数为 2ⁿ —— 本例中 n = 3，故最多有 2³ = 8 种唯一结果（注意：原问题示例中列出9项且含重复 [d,b,c]，实为笔误；正确结果应为8个互异组合）。
该问题本质是枚举所有长度为 n 的二进制掩码：每一位 0 表示取 A 中对应元素，1 表示取 B 中对应元素。例如掩码 010₂ = 2 对应 [a, e, c]（A[0], B[1], A[2]）。
以下是 Java 实现（兼容任意泛型列表）：
import java.util.*;
public class CrossoverGenerator {
public static <t> List<list>> crossover(List<t> a, List<t> b) {
if (a.size() != b.size() || a.isEmpty()) {
throw new IllegalArgumentException("Both lists must be non-empty and of equal size");
}
int n = a.size();
List<list>> result = new ArrayList();
// 枚举 0 到 2^n - 1 的所有掩码
for (int mask = 0; mask combo = new ArrayList();
for (int i = 0; i > i) & 1) == 1 ? b.get(i) : a.get(i);
combo.add(element);
}
result.add(combo);
}
return result;
}
// 使用示例
public static void main(String[] args) {
List<string> A = Arrays.asList("a", "b", "c");
List<string> B = Arrays.asList("d", "e", "f");
List<list>> allCrossovers = crossover(A, B);
for (List<string> combo : allCrossovers) {
System.out.println(combo); // 输出: [a,b,c], [d,b,c], [a,e,c], [d,e,c], ...
}
System.out.println("Total combinations: " + allCrossovers.size()); // 输出: 8
}
}</string></list></string></string></list></t></t></list></t>
✅ 关键要点说明：
- 时间复杂度：O(n × 2ⁿ)，不可优化（需生成全部组合）；
- 空间复杂度：O(n × 2ⁿ)，用于存储结果；
- 注意事项：确保 A 和 B 长度一致，否则逻辑失效；若需去重（如元素本身重复），应在生成后调用 new LinkedHashSet(result) 处理；
- 扩展性：该模式可推广至多集合交叉（需使用递归或迭代进位法），但二集合场景下位运算是最优解。
综上，利用二进制掩码驱动逐位选择，是解决此类等长集合交叉组合问题简洁、高效且易于理解的标准方法。
