Python的排列组合调用内置函数、自写算法DFS实现

排列组合是数学中的一种常见的计算方法，用于求出从给定的元素中选取若干个元素的所有可能的排列或组合。在Python中，有多种方式可以实现排列组合的计算。

本文将介绍两种主要的方法：调用内置函数和自写算法DFS实现。

目录

调用内置函数

自写算法DFS实现

调用内置函数

Python标准库中提供了一个模块itertools，该模块包含了许多用于生成迭代器的工具函数，其中就有2个函数可以用于计算排列组合，分别是：

- permutations(p [, r])：从序列p中取出r个元素的组成全排列，组合得到元组作为新迭代器的元素。
- combinations(p, r)：从序列p中取出r个元素组成全组合，元素不允许重复，组合得到元组作为新迭代器的元素。

这2个函数都返回一个迭代器对象，可以使用list()函数将其转换为列表，或者使用for循环遍历其元素。下面是一个简单的例子：

对于1到n个数进行排列，使用内置函数permutations(iterable,r=None)；

permutations(iterable,r=None) 连续返回iterable序列中的元素生成的长度为r的排列，如果r未指定或者为None，则默认值为iterable的长度。

1.  
   from itertools import *
2.  
   s = [1,2,3,4,5]
3.  
   for element in permutations(s,2):
4.  
   a = "".join(str(element))
5.  
   print(a,end="")
6.  
   out[1]:(1, 2)(1, 3)(1, 4)(1, 5)(2, 1)(2, 3)(2, 4)(2, 5)(3, 1)(3, 2)(3, 4)(3, 5)(4, 1)(4, 2)(4, 3)(4, 5)(5, 1)(5, 2)(5, 3)(5, 4)

如果需要枚举的数少的情况，可以直接通过暴力法

1.  
   for i in range(5):
2.  
   for j in range(5):
3.  
   if i!=j:
4.  
   print(s[i],s[j])

暴力法对于数字少的情况，效果好且简单。

对于1到n个数进行组合，使用内置函数combinations(iterable,r=None)

1.  
   In [30]: from itertools import *
2.  
   s = {1,2,3,4}
3.  
   for element in combinations(s,3):
4.  
   a = "".join(str(element))
5.  
   print(a,end="")
6.  
   (1, 2, 3)(1, 2, 4)(1, 3, 4)(2, 3, 4)

自写算法DFS实现

除了使用内置函数外，我们也可以自己编写算法来实现排列组合的计算。一种常见的算法是使用深度优先搜索（DFS）来遍历所有可能的情况，并将满足条件的结果保存下来。下面是一个使用DFS实现全排列和全组合的例子：

1.  
   a = [1,2,3,4,5]
2.  
   def dfs(s,t):
3.  
   if s==2:
4.  
   for i in range(0,2):
5.  
   print(a[i],end="")
6.  
   print(" ")
7.  
   return
8.  
   for i in range(s,t 1):
9.  
   a[s],a[i] = a[i],a[s]
10.  
    dfs(s 1,t)
11.  
    a[s],a[i] = a[i],a[s]
12.  
    dfs(0,4)

 上述代码虽然很短，但有个缺点就是不能从小到大输出排列。

改进之后的代码：实现从小到大输出

1.  
   a = [1,2,3,4,5]
2.  
   b = [0] * 10
3.  
   vis = [0] * 20
4.  
   def dfs(s,t):
5.  
   if s==2:
6.  
   for i in range(0,2):
7.  
   print(b[i],end="")
8.  
   print(" ")
9.  
   return
10.  
    for i in range(0,t):
11.  
    if not vis[i]:
12.  
    vis[i] = True
13.  
    b[s] = a[i]
14.  
    dfs(s 1,t)
15.  
    vis[i] = False
16.  
    dfs(0,5)

自写算法实现组合：

1.  
   # 首先，我们定义一个函数dfs，它接受五个参数：
2.  
   # - cur: 当前遍历到的元素的下标，初始为0
3.  
   # - m: 要选出的元素个数
4.  
   # - cur_list: 保存当前已选出的元素的列表
5.  
   # - original_list: 给定的n个元素的列表
6.  
   # - result_list: 保存最终结果的列表
7.  
    
8.  
   def dfs(cur, m, cur_list, original_list, result_list):
9.  
   # 如果已经选出了m个元素，就把当前列表添加到结果列表中，并返回
10.  
    if m == 0:
11.  
    result_list.append(list(cur_list))
12.  
    return
13.  
    # 如果还没有选出m个元素，就从当前下标开始，遍历原始列表中的每个元素
14.  
    for i in range(cur, len(original_list)):
15.  
    # 把当前元素添加到当前列表中
16.  
    cur_list.append(original_list[i])
17.  
    # 递归地调用dfs函数，更新下标和剩余元素个数
18.  
    dfs(i 1, m - 1, cur_list, original_list, result_list)
19.  
    # 回溯时，把当前元素从当前列表中移除
20.  
    cur_list.pop()
21.  
     
22.  
    # 然后，我们定义一个测试函数，给定一个原始列表和一个目标个数，调用dfs函数，并打印结果列表
23.  
     
24.  
    def test(original_list, m):
25.  
    # 初始化结果列表为空列表
26.  
    result_list = []
27.  
    # 调用dfs函数，传入初始下标为0，空的当前列表和结果列表
28.  
    dfs(0, m, [], original_list, result_list)
29.  
    # 打印结果列表
30.  
    print(result_list)
31.  
     
32.  
    # 最后，我们用一个例子来测试一下我们的算法，假设原始列表为[1, 2, 3, 4]，目标个数为2
33.  
     
34.  
    test([1, 2, 3, 4], 3)
35.  
     
36.  
    # 输出结果为：
37.  
    # [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
38.  
     
39.  
    # 可以看到，我们的算法成功地找到了所有的组合，并用DFS的方式遍历了它们。

这篇好文章是转载于：学新通技术网