排列组合的 python 实现

大家好，欢迎来到IT知识分享网。

排列组合是数学中很基本的知识点。所谓排列，就是指从给定个数的元素中取出指定个数的元素进行排序。组合则是指从给定个数的元素中仅仅取出指定个数的元素，不考虑排序。

排列：从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。当 m=n 时所有的排列情况叫全排列。

组合：从n个不同元素中任取m（m≤n）个元素，叫做从n个不同元素中取出m个元素的一个组合。

我们先来看看全排列，即对于 n 个不同元素，将它们按照一定顺序进行排列，能出现的所有情况。举个例子，比如数组 [1, 2, 3]，它按照不同顺序的排列有六种：
[1, 2, 3]、[1, 3, 2]、[2, 1, 3]、[2, 3, 1]、[3, 1, 2]、[3, 2, 1]

那么怎样去实现上面的过程呢？

细细来看，其实原理挺简单。对于 [1, 2, 3]，先把元素 1 取出来，再对剩余的 [2, 3] 做全排列，再将 1 加到上面，得到 [1, 2, 3] 和 [1, 3, 2]；同理，把元素 2 取出来，对剩余的 [1, 3] 做全排列，再将 2 加到上面，得到 [2, 1, 3] 和 [2, 3, 1]；把元素 3 取出来，对剩余的 [3, 1, 2] 做全排列，再将 3 加到上面，得到 [3, 1, 2] 和 [3, 2, 1]。

Python 代码如下：

# (递归实现) def Perm(arrs): # 若输入 [1,2,3]，则先取出1，将剩余的 [2,3]全排列得到 [[2,3],[3,2]]， # 再将 1加到全排列 [[2,3],[3,2]]上变成 [[1,2,3],[1,3,2]] # 同理，取出2或者3时，得到的分别是 [[2,1,3],[2,3,1]]和 [[3,1,2],[3,2,1]] if len(arrs)==1: return [arrs] result = [] # 最终的结果（即全排列的各种情况） for i in range(len(arrs)): rest_arrs = arrs[:i]+arrs[i+1:] # 取出arrs中的第 i个元素后剩余的元素 rest_lists = Perm(rest_arrs) # 剩余的元素完成全排列 lists = [] for term in rest_lists: lists.append(arrs[i:i+1]+term) # 将取出的第 i个元素加到剩余全排列的前面 result += lists return result 

其实，如果不是想实现算法的过程，而是仅仅想得到结果的话，可以将算法过程看作一个黑箱，直接调用 python 中的函数即可，代码如下：

import itertools print(list(itertools.permutations([1,2,3], 3))) 

相应地，如果不是全排列，比如从数组 [1, 2, 3] 中取出两个元素进行排列，那么只需将上面的代码的数字 3 改成 2 就行了。

import itertools print(list(itertools.permutations([1,2,3], 2))) 

具体的算法实现过程，Python 代码如下：

# (递归实现) def Perm_k(arrs, k): # 若输入 [1,2,3]，则先取出1这个元素，将剩余的 [2,3]中取出另一个元素得到 [[1,2],[1,3]] # 同理，取出2或者3时，得到的分别是 [[2,1],[2,3]]和 [[3,1],[3,2]] if len(arrs)==1: return [arrs] if k==1: return list(map(lambda s:[s], arrs)) # 当 k 为 1 时，每(单)个元素都可以被选取 result = [] # 最终的结果（即全排列的各种情况） for i in range(len(arrs)): rest_arrs = arrs[:i]+arrs[i+1:] # 取出arrs中的第 i个元素后剩余的元素 rest_lists = Perm_k(rest_arrs, k-1) # 剩余的元素选取 k-1元素 lists = [] for term in rest_lists: lists.append(arrs[i:i+1]+term) # 将取出的第 i个元素加到剩余全排列的前面 result += lists return result 

有了上面关于排列的算法实现，那么组合也就很容易了。用符号 $P(n,k)$ 表示从 $n$ 个元素中选取 $k$ 个元素进行排列的所有情况，用符号 $C(n,k)$ 表示从 $n$ 个元素中选取 $k$ 个元素进行组合的所有情况。这两个符号之前的关联如下：
$$C(n,k)=\frac{P(n,k)}{k!}$$
所以 $C(n,k)$ 的计算用代码实现的话，可以直接用上面关于 $P(n,k)$ 的计算结果，再除以 $k!$ 就可以得到。

当然，也可以直接调用 python 中封装好的函数，如下：

import itertools print(list(itertools.combinations([1,2,3,4],3))) # 表示从 [1,2,3,4] 中选出 3个元素的组合情况 

关于排列和组合的算法思路，除了按照上面的直接迭代的方法外，还可以用搜索迭代。
Python 代码如下：

def Perm(arrs, d, k, used, result): # d 表示搜索深度，k 是设定的最大深度，即 P(n, k)中需要选取的个数 if d == k: print(result) for i in range(len(arrs)): if used[i]: continue used[i] = True result.append(arrs[i]) Perm(arrs, d+1, k, used, result) result.pop() used[i] = False arrs = [1, 2, 3, 4] Perm(arrs, 0, 2, [False]*4, []) 

上面是关于排列的实现，而关于组合的实现跟排列类似，代码如下：

def Comb(arrs, d, k, s, result): # d 表示搜索深度，k 是设定的最大深度，即 C(n, k)中需要选取的个数 if d == k: print(result) for i in range(s, len(arrs)): result.append(arrs[i]) Comb(arrs, d+1, k, i+1, result) result.pop() arrs = [1, 2, 3, 4] Comb(arrs, 0, 3, 0, [])