基础知识
排列组合问题在中学数学中有所介绍，其中排列是考虑顺序的，组合是无顺序的。
譬如甲乙丙三个人，安排其中两个人去完成任务，可以有的组合方法有：甲乙、甲丙、乙丙，共 3 种。可以用数学记号来表示。
如果是安排他们三人选两人来拍照，而且拍照考虑站位的顺序，那么就有 6 种，可以用数学记号来表示。
对于个互不相同的元素，从其中选取
个，那么
组合数为
排列数为
基本算法
组合问题
如果是输出全部的组合，我们可以用二进制的思路。譬如安排甲乙丙丁去参加活动：
- 0000代表谁都不去
- 0001代表丁去，其它人不去
- 0010代表丙去，其它人不去
- 0011代表丙丁去，甲乙不去
…… 以此类推，一共种情况。
如果是要从个人中挑选
个，我们可以用深度优先搜索的方法。对于第 0 个人，我们可以分别讨论它进入不进入；对于第 1 个……
排列问题
一般使用回溯法，需要用vis数组来存储哪些人已经加入了排列。
以上都是传统与套路化的算法。在一般的算法题中常见，但是在开发过程中，我们不妨调用现有的库。
Python的itertools工具
Python提供了迭代工具itertools，可以很灵活地处理排列组合问题。
itertools提供了三个方面的工具，分别是：
- 无穷迭代器
- 根据最短输入序列长度停止的迭代器
- 排列组合迭代器
本文主要关注排列组合迭代器。
它包含四个迭代器： -
product()笛卡尔积 -
permutations()排列 -
combinations()组合 -
combinations_with_replacement可以重复使用同一个元素的组合
product()
所谓笛卡尔积，指的是有集合和
，其各出一个元素，考虑所有的情况，得到的新集合：
product()实现笛卡尔积，例如
import itertools
for elem in itertools.product("ABCD", "123"):
print(elem, end=" ")
输出('A', '1') ('A', '2') ('A', '3') ('B', '1') ('B', '2') ('B', '3') ('C', '1') ('C', '2') ('C', '3') ('D', '1') ('D', '2') ('D', '3')
其中的每一个elem是一个元组，这样输出看起来不舒服，改为
for elem in itertools.product("ABCD", "123"):
print(elem[0] + elem[1], end=" ")
输出A1 A2 A3 B1 B2 B3 C1 C2 C3 D1 D2 D3，类似于地铁出站口有ABCD四个，每个都有123的子出口。
可以迭代的对象都可以作为参数传入，例如
for elem in itertools.product(['语文','数学','英语'], range(1,7)):
print(elem[0] + str(elem[1]), end=" ")
输出语文1 语文2 语文3 语文4 语文5 语文6 数学1 数学2 数学3 数学4 数学5 数学6 英语1 英语2 英语3 英语4 英语5 英语6。
product()可以实现自己对自己的笛卡尔积。使用repeat参数来重复：
for elem in itertools.product("ABCD", repeat=2):
print(elem[0] + elem[1], end=" ")
输出AA AB AC AD BA BB BC BD CA CB CC CD DA DB DC DD
permutations()
permutations()实现排列，排列是区分顺序的。
例如
for elem in itertools.permutations("ABCD", 2):
print(elem[0] + elem[1], end=" ")
输出AB AC AD BA BC BD CA CB CD DA DB DC。
combinations()
combinations()实现组合，组合不区分顺序。
例如
for elem in itertools.combinations("ABCD", 2):
print(elem[0] + elem[1], end=" ")
输出AB AC AD BC BD CD
combinations_with_replacement()
combinations_with_replacement()实现可以重复利用同一个元素的组合。譬如我现在有ABCD四个人，我需要去办两个事，我可以请同一个人去办两次。
for elem in itertools.combinations_with_replacement("ABCD", 2):
print(elem[0] + elem[1], end=" ")
输出AA AB AC AD BB BC BD CC CD DD
网友评论