数组排列问题：如何获取多数组各取一个元素的所有组合

需求说明 #

你需要的是多集合笛卡尔积计算逻辑：给定多层嵌套列表，从每一层列表中各选取1个元素，输出所有可能的组合。

示例输入：
[['a', 'b', 'c'], ['e', 'f'], ['g', 'h', 'i']]
示例输出包含所有3×2×3=18种合法组合，例如['a','e','g']、['a','e','h']、['a','e','i']等。

实现思路 #

两种常见实现逻辑可选：

• 迭代法：初始结果集设为[[]]，依次遍历每一层子列表，将当前结果集的每一项和子列表的每个元素拼接生成新结果集，直到遍历完所有子列表
• 回溯法：递归遍历每一层元素，选完当前层元素后进入下一层，选完所有层元素就存入结果集

代码实现 #

Python 内置方法实现 #

Python标准库itertools的product方法可以直接实现需求：

from itertools import product

input_lists = [['a', 'b', 'c'], ['e', 'f'], ['g', 'h', 'i']]
# product返回元组格式，按需转列表即可
result = [list(item) for item in product(*input_lists)]

# 打印验证结果
for item in result:
    print(item)

无依赖迭代实现 #

如果不想依赖第三方/内置库，可以手动写迭代逻辑：

def cartesian_product(lists):
    result = [[]]
    for sub_list in lists:
        temp = []
        for res_item in result:
            for elem in sub_list:
                temp.append(res_item + [elem])
        result = temp
    return result

input_lists = [['a', 'b', 'c'], ['e', 'f'], ['g', 'h', 'i']]
print(cartesian_product(input_lists))

回溯法实现 #

def cartesian_product_backtrack(lists):
    result = []
    def backtrack(index, current):
        # 遍历完所有子列表，存入结果
        if index == len(lists):
            result.append(current.copy())
            return
        # 遍历当前子列表所有元素
        for elem in lists[index]:
            current.append(elem)
            backtrack(index + 1, current)
            current.pop()
    backtrack(0, [])
    return result

input_lists = [['a', 'b', 'c'], ['e', 'f'], ['g', 'h', 'i']]
print(cartesian_product_backtrack(input_lists))

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