代码收藏家 Python排列与组合
本文简要总结在 Python 中实现排列与组合的方法。
Update: 2022 / 11 / 21
Python | 排列与组合
总览
在做数据分析的时候，可能会碰到类似于高中所学过的取小球问题。这时候可以使用已有的库 ( itertools, numpy 等 ) 与函数或者自己构造相应的方法来达到目的。
方法
比如，我们要实现 1，2，3，4 的排列组合，利用高中曾学过的知识，我们可以很容易写出来 1，如下表：
| 考虑顺序与否 | 元素个数 | 组合 |
|---|---|---|
F |
1 | (1,), (2,), (3,), (4,) |
| 2 | (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4) |
|
| 3 | (1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4) |
|
T |
1 | (1,), (2,), (3,), (4,) |
| 2 | (1, 2), (1, 3), (1, 4), (2, 1), (2, 3), (2, 4), (3, 1), (3, 2), (3, 4), (4, 1), (4, 2), (4, 3) |
|
| 3 | (1, 2, 3), (1, 2, 4), (1, 3, 2), (1, 3, 4), (1, 4, 2), (1, 4, 3), (2, 1, 3), (2, 1, 4), (2, 3, 1), (2, 3, 4), (2, 4, 1), (2, 4, 3), (3, 1, 2), (3, 1, 4), (3, 2, 1), (3, 2, 4), (3, 4, 1), (3, 4, 2), (4, 1, 2), (4, 1, 3), (4, 2, 1), (4, 2, 3), (4, 3, 1), (4, 3, 2) |
itertools
itertools 模块下提供了一些用于生成排列组合的工具函数 2。
用法
| 方法 | 含义 |
|---|---|
product(p, q, … [repeat=1]) |
用序列 p、q、…序列中的元素进行排列（元素会重复）。就相当于使用嵌套循环组合。 |
permutations(p[, r]) |
从序列 p 中取出 r 个元素的组成全排列，组合得到元组作为新迭代器的元素。 |
combinations(p, r) |
从序列 p 中取出 r 个元素组成全组合，元素不允许重复，组合得到元组作为新迭代器的元素。 |
combinations_with_replacement(p, r) |
从序列 p 中取出 r 个元素组成全组合，元素允许重复，组合得到元组作为新迭代器的元素。 |
示例
以下面的列表为例，
import itertools
L = [1, 2, 3, 4]
不考虑顺序
comb1 = list(itertools.combinations([1,2,3,4],1))
'''
[(1,), (2,), (3,), (4,)]
'''
comb2 = list(itertools.combinations([1,2,3,4],2))
'''
[(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]
'''
comb3 = list(itertools.combinations([1,2,3,4],3))
'''
[(1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4)]
'''
考虑顺序
comb1 = list(itertools.permutations([1,2,3,4],1))
'''
[(1,), (2,), (3,), (4,)]
'''
comb2 = list(itertools.permutations([1,2,3,4],2))
'''
[(1, 2), (1, 3), (1, 4), (2, 1), (2, 3), (2, 4), (3, 1), (3, 2), (3, 4), (4, 1), (4, 2), (4, 3)]
'''
comb3 = list(itertools.permutations([1,2,3,4],3))
'''
[(1, 2, 3), (1, 2, 4), (1, 3, 2), (1, 3, 4), (1, 4, 2), (1, 4, 3), (2, 1, 3), (2, 1, 4), (2, 3, 1), (2, 3, 4), (2, 4, 1), (2, 4, 3), (3, 1, 2), (3, 1, 4), (3, 2, 1), (3, 2, 4), (3, 4, 1), (3, 4, 2), (4, 1, 2), (4, 1, 3), (4, 2, 1), (4, 2, 3), (4, 3, 1), (4, 3, 2)]
'''
numpy
示例
以下面的列表为例，
import numpy as np
import random
L = [1, 2, 3, 4]
不考虑顺序
elecnt = len(L)
cnt = 2
A = np.product(np.arange(1, elecnt+1))
B = np.product(np.arange(1, elecnt+1-cnt)) * np.product(np.arange(1, 1+cnt))
combcnt = int(A/B)
def combinations(combcnt, elecnt, cnt):
trials = combcnt
rslt = []
while trials > 0:
sample = sorted(random.sample(list(range(1, 1+elecnt)), cnt))
if sample in rslt:
continue
else:
if len(rslt) == combcnt:
break
else:
rslt.append(sample)
trials -= 1
return sorted(rslt)
#
comb = combinations(combcnt=combcnt, elecnt=elecnt, cnt=cnt)
print(f"self-defined: #{len(comb)}: {comb}")
'''
self-defined: #6: [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
'''
import itertools
comb = list(itertools.combinations(L, 2))
print(f'itertools : #{len(comb)}: {comb}')
'''
itertools : #6: [(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]
'''
利用上文介绍到的 itertools.combinations 的方法，检验自定义函数 combinations 的结果的准确程度。
考虑顺序
参考这里 3
array_L = np.array(L)
cnt = 3
comb = np.unique(np.array(np.meshgrid(array_L, array_L, array_L)).T.reshape(-1, cnt), axis=0)
print(f"\ncomb:\n{comb}")
'''
[[1 1 1]
[1 2 1]
[1 3 1]
[1 4 1]
[2 1 1]
[2 2 1]
......
[4 1 4]
[4 2 4]
[4 3 4]
[4 4 4]]
# shape, (64, 3)
'''
import itertools
comb = list(itertools.product(L, repeat=cnt))
'''
[[1 1 1]
[1 2 1]
[1 3 1]
[1 4 1]
[2 1 1]
[2 2 1]
......
[4 1 4]
[4 2 4]
[4 3 4]
[4 4 4]]
# shape, (64, 3)
'''
利用上文介绍到的 itertools.product 的方法，检验使用 numpy 所得结果的准确程度。
