詳解Python中的排列組合生成器

在實(shí)際的開(kāi)發(fā)場(chǎng)景中，經(jīng)常需要遍歷多個(gè)數(shù)組中的元素，將它們組合在一起使用。要取完所有可能的組合，最基本的方法是使用嵌套的循環(huán)，有多少個(gè)數(shù)組就嵌套多少層循環(huán)。嵌套循環(huán)是基本的原理，但不夠簡(jiǎn)潔，Python中有更優(yōu)雅的方式來(lái)實(shí)現(xiàn)這種功能。

在Python的內(nèi)置模塊 functools 中，提供了高階類 product() ，用于實(shí)現(xiàn)多個(gè)可迭代對(duì)象（列表、字符串等）中元素的組合，返回可迭代對(duì)象中元素組合的笛卡爾積，效果相當(dāng)于嵌套的循環(huán)。為了更直觀地看出效果，下面用代碼對(duì)比來(lái)看 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='??')

#?調(diào)用product實(shí)現(xiàn)元素組合，替代for循環(huán)
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黑

可以看到，實(shí)現(xiàn)相同的功能，for循環(huán)使用了三層嵌套，而 product() 只需要一層循環(huán)。

product 的結(jié)果是生成器，生成器中的每個(gè)元素是一個(gè)元組，可以直接遍歷，也可以遍歷時(shí)解包取出元組中的數(shù)據(jù)，還可以與列表推導(dǎo)式配合使用等。

在源碼中，對(duì) product 的描述是：Cartesian product of input iterables. ?Equivalent to nested for-loops. 翻譯成中文：求輸入可迭代對(duì)象的笛卡爾積，相當(dāng)于嵌套的for循環(huán)。解釋一下這句話，第一，product 的輸入要是可迭代對(duì)象，如字符串、列表、元組等。第二，product 會(huì)將可迭代對(duì)象中的元素按笛卡爾積進(jìn)行組合，相當(dāng)于嵌套的循環(huán)。

如果不知道笛卡爾積是什么？這里簡(jiǎn)單介紹一下。笛卡爾積（Cartesian product）是指數(shù)學(xué)中將兩個(gè)集合 X 和 Y 中的對(duì)象組合，第一個(gè)對(duì)象是 X 中的成員而第二個(gè)對(duì)象是 Y 中的成員，組合完所有可能的有序?qū)?。笛卡爾積又稱為直積，表示為 X×Y 。例如，假設(shè)集合 X={a, b} ，集合 Y={0, 1, 2} ，則兩個(gè)集合的笛卡爾積為 {(a, 0), (a, 1), (a, 2), (b, 0), (b, 1), (b, 2)} 。

product 類就是專門為求笛卡爾積而量身定做的，用途一致，命名也一致（英文單詞一樣，見(jiàn)名知意）。

product 使用時(shí)可以傳入多個(gè)可迭代對(duì)象，結(jié)果會(huì)求所有可迭代對(duì)象累加的笛卡爾積。product 還有一個(gè) repeat 參數(shù)，repeat 用于設(shè)置 product() 中每個(gè)可迭代對(duì)象的重復(fù)次數(shù)，默認(rèn)值為1。如果只傳入一個(gè)可迭代對(duì)象，求自身的笛卡爾積，可以使用 repeat 參數(shù)指定重復(fù)多少次。例如，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參數(shù)設(shè)置重復(fù)次數(shù)
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')

在內(nèi)置模塊 functools 中，用于將多個(gè)可迭代對(duì)象中的元素排列組合的類不只 product ，還有三個(gè)類提供了類似的功能，共同組成了一組非常有用的高階工具。下面依次介紹它們并進(jìn)行對(duì)比。

permutations(iterable[, r]): Return successive r-length permutations of elements in the iterable. 返回可迭代對(duì)象中元素的長(zhǎng)度為 r 的排列，元素不能重復(fù)。

combinations(iterable, r): Return successive r-length combinations of elements in the iterable. 返回可迭代對(duì)象中元素的長(zhǎng)度為 r 的組合，元素不能重復(fù)。

combinations_with_replacement(iterable, r): Return successive r-length combinations of elements in the iterable allowing individual elements to have successive repeats. 返回可迭代對(duì)象中元素的長(zhǎng)度為 r 的組合，允許元素重復(fù)。

product 是求笛卡爾積，permutations 是求排列，combinations 是求組合，combinations_with_replacement 是求組合但允許元素重復(fù)。它們分別是什么結(jié)果？相互之間有什么區(qū)別呢？通過(guò)下面的代碼可以進(jìn)行對(duì)比。

#?笛卡爾積
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)
#?組合，元素可以重復(fù)
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')

四個(gè)生成器返回的結(jié)果中都是元組，為了更直觀地對(duì)比效果，將結(jié)果整理如下：

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 對(duì)比，比 product 少了元素相同的情況，從可迭代對(duì)象中取出 r 個(gè)元素，元素順序相反屬于不同情況，結(jié)果中會(huì)保留。combinations 與 permutations 對(duì)比，combinations 中元素順序相反的結(jié)果屬于相同情況，結(jié)果中不重復(fù)保留，也就是說(shuō) combinations （組合）是無(wú)序的， permutations （排列）是有序的。combinations_with_replacement 與 combinations 對(duì)比，combinations_with_replacement 中允許相同元素重復(fù)被取，結(jié)果中多了兩個(gè)元素相同的情況。

這三個(gè)類的參數(shù)都有且只有一個(gè)可迭代對(duì)象，不能同時(shí)傳入多個(gè)可迭代對(duì)象。另一個(gè)參數(shù) r 是從可迭代對(duì)象中選取 r 個(gè)元素來(lái)排列組合，permutations 的 r 不是必傳參數(shù)，默認(rèn)為可迭代對(duì)象的長(zhǎng)度，permutations 和 combinations 的結(jié)果中不允許元素重復(fù)，所以 r 大于可迭代對(duì)象長(zhǎng)度時(shí)結(jié)果為空，combinations_with_replacement 的結(jié)果允許元素重復(fù)，r 可以大于可迭代對(duì)象長(zhǎng)度。

1.四個(gè)生成器的用法和區(qū)別已經(jīng)介紹完，它們相當(dāng)于工具箱中的一組高級(jí)工具，可以根據(jù)不同的場(chǎng)景選用，提高代碼的優(yōu)雅性。

2.在一些特殊場(chǎng)景，我們知道要用多層循環(huán)嵌套，但是循環(huán)的嵌套層數(shù)是動(dòng)態(tài)的，導(dǎo)致無(wú)法下手寫循環(huán)代碼，此時(shí)可以巧妙地用 product 解決問(wèn)題。這點(diǎn)后面我會(huì)在實(shí)際的問(wèn)題中說(shuō)明。