如何按“仅取数组首元素洗牌”规则生成两数组全可能组合？

核心思路 #

用递归回溯就能解决这个问题——每一步你只有两种选择（如果两个数组都还有元素的话）：要么取第一个数组的首元素，要么取第二个数组的首元素。取完之后把该元素从原数组移除，继续递归处理剩余的元素，直到两个数组都为空，此时就得到了一个合法的序列。

Python 递归实现 #

def generate_all_shuffles(arr1, arr2):
    result = []
    
    def backtrack(current_seq, left1, left2):
        # 两个数组都空了，把当前序列存起来
        if not left1 and not left2:
            result.append(current_seq.copy())
            return
        
        # 尝试取第一个数组的首元素
        if left1:
            current_seq.append(left1[0])
            backtrack(current_seq, left1[1:], left2)
            current_seq.pop()  # 回溯，撤销刚才的选择
        
        # 尝试取第二个数组的首元素
        if left2:
            current_seq.append(left2[0])
            backtrack(current_seq, left1, left2[1:])
            current_seq.pop()  # 回溯
    
    backtrack([], arr1, arr2)
    return result

# 测试示例
arr1 = [1, 2]
arr2 = ['x', 'y']
print(generate_all_shuffles(arr1, arr2))
# 输出结果：[[1, 2, 'x', 'y'], [1, 'x', 2, 'y'], [1, 'x', 'y', 2], ['x', 1, 2, 'y'], ['x', 1, 'y', 2], ['x', 'y', 1, 2]]

非递归实现（栈模拟） #

如果数组元素较多，递归可能会触发深度限制，用栈模拟递归过程更稳妥：

def generate_all_shuffles_iterative(arr1, arr2):
    result = []
    # 栈里每个元素存：当前生成的序列、剩余的arr1、剩余的arr2
    stack = [([], arr1, arr2)]
    
    while stack:
        current, rem1, rem2 = stack.pop()
        
        if not rem1 and not rem2:
            result.append(current)
            continue
        
        # 注意栈是后进先出，所以先压入取arr2的情况，保证生成顺序和递归一致
        if rem2:
            stack.append((current + [rem2[0]], rem1, rem2[1:]))
        
        if rem1:
            stack.append((current + [rem1[0]], rem1[1:], rem2))
    
    return result

# 测试
print(generate_all_shuffles_iterative([1,2], ['x','y']))

逻辑说明 #

• 不管递归还是非递归，核心都是枚举所有合法的选择路径：每次只能从两个数组的头部取元素，取完后剩余的元素继续参与后续选择。
• 回溯的作用是在尝试完一条路径后，恢复状态，去尝试另一条可能的路径，这样就能覆盖所有合法的排列组合。

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