如何获取两个等长集合的交叉组合结果及最大可能数量？

现有两个等长集合：

A:  [a,b,c]
B:  [d,e,f]

希望得到如下形式的交叉组合结果（注：示例中存在重复项为输入笔误，实际所有组合无重复）：

[ [a,e,f],[a,b,f],[d,b,c],[d,b,f],[d,b,c],[d,e,c],[a,e,c],[a,b,c],[d,e,f]... ]

请问如何获取所有可能的交叉组合结果？该场景下的最大组合数量是多少？

一、生成所有交叉组合的实现思路 #

核心逻辑是：每个位置上的元素，都可以选择A对应位置的元素，或者B对应位置的元素，枚举所有位置的选择组合即可得到全部结果。

以Python为例，用二进制掩码的方式实现最直观：

A = ['a', 'b', 'c']
B = ['d', 'e', 'f']
combinations = []

# 遍历所有可能的选择状态，用二进制数表示每个位置的选择
for mask in range(2 ** len(A)):
    current_combo = []
    for idx in range(len(A)):
        # 检查当前位是否为1，是则选B的元素，否则选A的
        if mask & (1 << idx):
            current_combo.append(B[idx])
        else:
            current_combo.append(A[idx])
    combinations.append(current_combo)

print(combinations)

运行后会输出所有8种无重复的组合：

[['a', 'b', 'c'], ['a', 'b', 'f'], ['a', 'e', 'c'], ['a', 'e', 'f'], ['d', 'b', 'c'], ['d', 'b', 'f'], ['d', 'e', 'c'], ['d', 'e', 'f']]

其他编程语言可以用类似思路：通过循环枚举所有可能的选择状态，每个状态对应一种组合。

二、最大组合数量计算 #

当两个集合对应位置的元素均不重复时，每个位置有2种独立选择，集合长度为n时，总组合数为 2ⁿ。

题目中集合长度n=3，因此最大组合数量是2³=8。如果存在某个位置A[i] = B[i]，该位置的选择不会产生新组合，总数量会相应减少，但题目示例中所有对应位置元素都不同，所以最大是8种。

内容的提问来源于stack exchange，提问作者Alex