本文简要总结在 Python 中实现排列与组合的方法。

Update: 2022 / 11 / 21

Python | 排列与组合

  • 总览
  • 方法
    • itertools
      • 用法
      • 示例
        • 不考虑顺序
        • 考虑顺序
    • numpy
      • 示例
        • 不考虑顺序
        • 考虑顺序
  • 参考链接

总览

在做数据分析的时候，可能会碰到类似于高中所学过的取小球问题。这时候可以使用已有的库 ( itertools, numpy 等 ) 与函数或者自己构造相应的方法来达到目的。

方法

比如，我们要实现 1，2，3，4 的排列组合，利用高中曾学过的知识，我们可以很容易写出来 1，如下表：

考虑顺序与否元素个数组合
F1(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)
T1(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 itertoolsL = [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 npimport randomL = [1, 2, 3, 4]

不考虑顺序

elecnt = len(L)cnt = 2A = 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 itertoolscomb = 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 = 3comb = 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 itertoolscomb = 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 所得结果的准确程度。

参考链接

  1. 用python实现排列组合 ↩︎

  2. Python的排列组合函数 ↩︎

  3. How to build an array of all combinations of two NumPy arrays? ↩︎