4.9 排列组合的迭代

问题

你想迭代遍历一个集合中元素的所有可能的排列或组合

解决方案

itertools模块提供了三个函数来解决这类问题。其中一个是 itertools.permutations() ,它接受一个集合并产生一个元组序列,每个元组由集合中所有元素的一个可能排列组成。也就是说通过打乱集合中元素排列顺序生成一个元组,比如:

  1. >>> items = ['a', 'b', 'c']
  2. >>> from itertools import permutations
  3. >>> for p in permutations(items):
  4. ... print(p)
  5. ...
  6. ('a', 'b', 'c')
  7. ('a', 'c', 'b')
  8. ('b', 'a', 'c')
  9. ('b', 'c', 'a')
  10. ('c', 'a', 'b')
  11. ('c', 'b', 'a')
  12. >>>

如果你想得到指定长度的所有排列,你可以传递一个可选的长度参数。就像这样:

  1. >>> for p in permutations(items, 2):
  2. ... print(p)
  3. ...
  4. ('a', 'b')
  5. ('a', 'c')
  6. ('b', 'a')
  7. ('b', 'c')
  8. ('c', 'a')
  9. ('c', 'b')
  10. >>>

使用 itertools.combinations() 可得到输入集合中元素的所有的组合。比如:

  1. >>> from itertools import combinations
  2. >>> for c in combinations(items, 3):
  3. ... print(c)
  4. ...
  5. ('a', 'b', 'c')
  6.  
  7. >>> for c in combinations(items, 2):
  8. ... print(c)
  9. ...
  10. ('a', 'b')
  11. ('a', 'c')
  12. ('b', 'c')
  13.  
  14. >>> for c in combinations(items, 1):
  15. ... print(c)
  16. ...
  17. ('a',)
  18. ('b',)
  19. ('c',)
  20. >>>

对于 combinations() 来讲,元素的顺序已经不重要了。也就是说,组合 ('a', 'b')('b', 'a') 其实是一样的(最终只会输出其中一个)。

在计算组合的时候,一旦元素被选取就会从候选中剔除掉(比如如果元素’a’已经被选取了,那么接下来就不会再考虑它了)。而函数 itertools.combinations_with_replacement() 允许同一个元素被选择多次,比如:

  1. >>> for c in combinations_with_replacement(items, 3):
  2. ... print(c)
  3. ...
  4. ('a', 'a', 'a')
  5. ('a', 'a', 'b')
  6. ('a', 'a', 'c')
  7. ('a', 'b', 'b')
  8. ('a', 'b', 'c')
  9. ('a', 'c', 'c')
  10. ('b', 'b', 'b')
  11. ('b', 'b', 'c')
  12. ('b', 'c', 'c')
  13. ('c', 'c', 'c')
  14. >>>

讨论

这一小节我们向你展示的仅仅是 itertools 模块的一部分功能。尽管你也可以自己手动实现排列组合算法,但是这样做得要花点脑力。当我们碰到看上去有些复杂的迭代问题时,最好可以先去看看itertools模块。如果这个问题很普遍,那么很有可能会在里面找到解决方案!

原文:

http://python3-cookbook.readthedocs.io/zh_CN/latest/c04/p09_iterate_over_combination_or_permutation.html