4.9 排列組合的迭代

問題

你想迭代遍歷一個集合中元素的所有可能的排列或組合

解決方案

itertools模塊提供了三個函數(shù)來解決這類問題。其中一個是 itertools.permutations() ，它接受一個集合并產(chǎn)生一個元組序列，每個元組由集合中所有元素的一個可能排列組成。也就是說通過打亂集合中元素排列順序生成一個元組，比如：

>>> items = ['a', 'b', 'c']
>>> from itertools import permutations
>>> for p in permutations(items):
...     print(p)
...
('a', 'b', 'c')
('a', 'c', 'b')
('b', 'a', 'c')
('b', 'c', 'a')
('c', 'a', 'b')
('c', 'b', 'a')
>>>

如果你想得到指定長度的所有排列，你可以傳遞一個可選的長度參數(shù)。就像這樣：

>>> for p in permutations(items, 2):
...     print(p)
...
('a', 'b')
('a', 'c')
('b', 'a')
('b', 'c')
('c', 'a')
('c', 'b')
>>>

使用 itertools.combinations() 可得到輸入集合中元素的所有的組合。比如：

>>> from itertools import combinations
>>> for c in combinations(items, 3):
...     print(c)
...
('a', 'b', 'c')

>>> for c in combinations(items, 2):
...     print(c)
...
('a', 'b')
('a', 'c')
('b', 'c')

>>> for c in combinations(items, 1):
...     print(c)
...
('a',)
('b',)
('c',)
>>>

對于 combinations() 來講，元素的順序已經(jīng)不重要了。也就是說，組合 ('a', 'b') 跟 ('b', 'a') 其實是一樣的(最終只會輸出其中一個)。

在計算組合的時候，一旦元素被選取就會從候選中剔除掉(比如如果元素'a'已經(jīng)被選取了，那么接下來就不會再考慮它了)。而函數(shù) itertools.combinations_with_replacement() 允許同一個元素被選擇多次，比如：

>>> for c in combinations_with_replacement(items, 3):
...     print(c)
...
('a', 'a', 'a')
('a', 'a', 'b')
('a', 'a', 'c')
('a', 'b', 'b')
('a', 'b', 'c')
('a', 'c', 'c')
('b', 'b', 'b')
('b', 'b', 'c')
('b', 'c', 'c')
('c', 'c', 'c')
>>>

討論

這一小節(jié)我們向你展示的僅僅是itertools模塊的一部分功能。盡管你也可以自己手動實現(xiàn)排列組合算法，但是這樣做得要花點腦力。當我們碰到看上去有些復(fù)雜的迭代問題時，最好可以先去看看itertools模塊。如果這個問題很普遍，那么很有可能會在里面找到解決方案！