详解Python中的排列组合生成器

在实际的开发场景中，经常需要遍历多个数组中的元素，将它们组合在一起使用。要取完所有可能的组合，最基本的方法是使用嵌套的循环，有多少个数组就嵌套多少层循环。嵌套循环是基本的原理，但不够简洁，Python中有更优雅的方式来实现这种功能。

在Python的内置模块 functools 中，提供了高阶类 product() ，用于实现多个可迭代对象（列表、字符串等）中元素的组合，返回可迭代对象中元素组合的笛卡尔积，效果相当于嵌套的循环。为了更直观地看出效果，下面用代码对比来看 product 的效果。

# coding=utf-8
phone = ['iPhone', 'HuaWei', 'Mi']
number = [1, 2, 3]
color = ['白', '黑']
for p in phone:
    for n in number:
        for c in color:
            print(f'{p}{n}{c}', end='  ')

# 调用product实现元素组合，替代for循环
import itertools
for p, n, c in itertools.product(phone, number, color):
    print(f'{p}{n}{c}', end='  ')

Output：

iPhone1白  iPhone1黑  iPhone2白  iPhone2黑  iPhone3白  iPhone3黑  HuaWei1白  HuaWei1黑  HuaWei2白  HuaWei2黑  HuaWei3白  HuaWei3黑  Mi1白  Mi1黑  Mi2白  Mi2黑  Mi3白  Mi3黑  
iPhone1白  iPhone1黑  iPhone2白  iPhone2黑  iPhone3白  iPhone3黑  HuaWei1白  HuaWei1黑  HuaWei2白  HuaWei2黑  HuaWei3白  HuaWei3黑  Mi1白  Mi1黑  Mi2白  Mi2黑  Mi3白  Mi3黑

可以看到，实现相同的功能，for循环使用了三层嵌套，而 product() 只需要一层循环。

product 的结果是生成器，生成器中的每个元素是一个元组，可以直接遍历，也可以遍历时解包取出元组中的数据，还可以与列表推导式配合使用等。

在源码中，对 product 的描述是：Cartesian product of input iterables.  Equivalent to nested for-loops. 翻译成中文：求输入可迭代对象的笛卡尔积，相当于嵌套的for循环。解释一下这句话，第一，product 的输入要是可迭代对象，如字符串、列表、元组等。第二，product 会将可迭代对象中的元素按笛卡尔积进行组合，相当于嵌套的循环。

如果不知道笛卡尔积是什么？这里简单介绍一下。笛卡尔积（Cartesian product）是指数学中将两个集合 X 和 Y 中的对象组合，第一个对象是 X 中的成员而第二个对象是 Y 中的成员，组合完所有可能的有序对。笛卡尔积又称为直积，表示为 X×Y 。例如，假设集合 X={a, b} ，集合 Y={0, 1, 2} ，则两个集合的笛卡尔积为 {(a, 0), (a, 1), (a, 2), (b, 0), (b, 1), (b, 2)} 。

product 类就是专门为求笛卡尔积而量身定做的，用途一致，命名也一致（英文单词一样，见名知意）。

product 使用时可以传入多个可迭代对象，结果会求所有可迭代对象累加的笛卡尔积。product 还有一个 repeat 参数，repeat 用于设置 product() 中每个可迭代对象的重复次数，默认值为1。如果只传入一个可迭代对象，求自身的笛卡尔积，可以使用 repeat 参数指定重复多少次。例如，product(X, Y, repeat=2) 与 product(X, Y, X, Y) 相同，product(X, repeat=4) 与 product(X, X, X, X) 相同。

X = [1, 2]
Y = ['a', 'b']
itertools.product(X, repeat=4)
for combination in itertools.product(X, Y, X, Y):
    print(combination, end=' ')
    
print()
# 使用repeat参数设置重复次数
for combination in itertools.product(X, Y, repeat=2):
    print(combination, end=' ')

Output：

(1, 'a', 1, 'a') (1, 'a', 1, 'b') (1, 'a', 2, 'a') (1, 'a', 2, 'b') (1, 'b', 1, 'a') (1, 'b', 1, 'b') (1, 'b', 2, 'a') (1, 'b', 2, 'b') (2, 'a', 1, 'a') (2, 'a', 1, 'b') (2, 'a', 2, 'a') (2, 'a', 2, 'b') (2, 'b', 1, 'a') (2, 'b', 1, 'b') (2, 'b', 2, 'a') (2, 'b', 2, 'b') 
(1, 'a', 1, 'a') (1, 'a', 1, 'b') (1, 'a', 2, 'a') (1, 'a', 2, 'b') (1, 'b', 1, 'a') (1, 'b', 1, 'b') (1, 'b', 2, 'a') (1, 'b', 2, 'b') (2, 'a', 1, 'a') (2, 'a', 1, 'b') (2, 'a', 2, 'a') (2, 'a', 2, 'b') (2, 'b', 1, 'a') (2, 'b', 1, 'b') (2, 'b', 2, 'a') (2, 'b', 2, 'b')

在内置模块 functools 中，用于将多个可迭代对象中的元素排列组合的类不只 product ，还有三个类提供了类似的功能，共同组成了一组非常有用的高阶工具。下面依次介绍它们并进行对比。

permutations(iterable[, r]): Return successive r-length permutations of elements in the iterable. 返回可迭代对象中元素的长度为 r 的排列，元素不能重复。

combinations(iterable, r): Return successive r-length combinations of elements in the iterable. 返回可迭代对象中元素的长度为 r 的组合，元素不能重复。

combinations_with_replacement(iterable, r): Return successive r-length combinations of elements in the iterable allowing individual elements to have successive repeats. 返回可迭代对象中元素的长度为 r 的组合，允许元素重复。

product 是求笛卡尔积，permutations 是求排列，combinations 是求组合，combinations_with_replacement 是求组合但允许元素重复。它们分别是什么结果？相互之间有什么区别呢？通过下面的代码可以进行对比。

# 笛卡尔积
for p in itertools.product('ABCD', repeat=2):
    print(p, end=' ')

print('\n', '-'*20)
# 排列
for pe in itertools.permutations('ABCD', 2):
    print(pe, end=' ')

print('\n', '-'*20)
# 组合
for c in itertools.combinations('ABCD', 2):
    print(c, end=' ')

print('\n', '-'*20)
# 组合，元素可以重复
for cr in itertools.combinations_with_replacement('ABCD', 2):
    print(cr, end=' ')

Output：

('A', 'A') ('A', 'B') ('A', 'C') ('A', 'D') 
('B', 'A') ('B', 'B') ('B', 'C') ('B', 'D')
('C', 'A') ('C', 'B') ('C', 'C') ('C', 'D') 
('D', 'A') ('D', 'B') ('D', 'C') ('D', 'D') 
 --------------------
('A', 'B') ('A', 'C') ('A', 'D') 
('B', 'A') ('B', 'C') ('B', 'D') 
('C', 'A') ('C', 'B') ('C', 'D') 
('D', 'A') ('D', 'B') ('D', 'C') 
 --------------------
('A', 'B') ('A', 'C') ('A', 'D') 
('B', 'C') ('B', 'D') ('C', 'D') 
 --------------------
('A', 'A') ('A', 'B') ('A', 'C') ('A', 'D') 
('B', 'B') ('B', 'C') ('B', 'D') 
('C', 'C') ('C', 'D') ('D', 'D')

四个生成器返回的结果中都是元组，为了更直观地对比效果，将结果整理如下：

product('ABCD', repeat=2)
AA AB AC AD BA BB BC BD CA CB CC CD DA DB DC DD

permutations('ABCD', 2)
AB AC AD BA BC BD CA CB CD DA DB DC

combinations('ABCD', 2)
AB AC AD BC BD CD

combinations_with_replacement('ABCD', 2)
AA AB AC AD BB BC BD CC CD DD

permutations 与 product 对比，比 product 少了元素相同的情况，从可迭代对象中取出 r 个元素，元素顺序相反属于不同情况，结果中会保留。combinations 与 permutations 对比，combinations 中元素顺序相反的结果属于相同情况，结果中不重复保留，也就是说 combinations （组合）是无序的， permutations （排列）是有序的。combinations_with_replacement 与 combinations 对比，combinations_with_replacement 中允许相同元素重复被取，结果中多了两个元素相同的情况。

这三个类的参数都有且只有一个可迭代对象，不能同时传入多个可迭代对象。另一个参数 r 是从可迭代对象中选取 r 个元素来排列组合，permutations 的 r 不是必传参数，默认为可迭代对象的长度，permutations 和 combinations 的结果中不允许元素重复，所以 r 大于可迭代对象长度时结果为空，combinations_with_replacement 的结果允许元素重复，r 可以大于可迭代对象长度。

1.四个生成器的用法和区别已经介绍完，它们相当于工具箱中的一组高级工具，可以根据不同的场景选用，提高代码的优雅性。

2.在一些特殊场景，我们知道要用多层循环嵌套，但是循环的嵌套层数是动态的，导致无法下手写循环代码，此时可以巧妙地用 product 解决问题。这点后面我会在实际的问题中说明。