博客

Python通过内置函数和自写算法DFS实现排列组合

  • Post category:Python

Python通过内置函数和自写算法DFS实现排列组合攻略

什么是排列组合

排列是指从n个不同元素中，取出m个元素（m<=n）进行排列，按照一定的顺序进行排列，其排列方式的个数称为排列数。

排列数 = n^m

组合是指从n个不同元素中，取出m个元素（m<=n）进行组合，不考虑元素之间的顺序，其组合方式的个数称为组合数。

组合数 = C(m,n) = n!/m!(n-m)!

如何在Python中实现排列组合

内置函数实现排列组合

在Python内置的标准库中，有许多用于处理排列组合的函数，如itertools库中的permutations()和combinations()函数。

import itertools

lst = ["A", "B", "C"]
# 生成所有的排列
permutation = itertools.permutations(lst,3)
print(list(permutation))
# 输出 [('A', 'B', 'C'), ('A', 'C', 'B'), ('B', 'A', 'C'), ('B', 'C', 'A'), ('C', 'A', 'B'), ('C', 'B', 'A')]

# 生成所有的组合
combination = itertools.combinations(lst,2)
print(list(combination))
# 输出 [('A', 'B'), ('A', 'C'), ('B', 'C')]

自写算法DFS实现排列组合

我们也可以通过自己编写算法来实现排列组合，这里我们介绍深度优先搜索算法（DFS）。

DFS排列实现示例

lst = ["A", "B", "C"]
n = len(lst)
used = [False for i in range(n)]
path = []
res = []

def dfs_permutation(lst,depth,used,path,res):
    # 产生一个排列
    if depth == n:
        res.append(path.copy())
        return

    for i in range(n):
        if used[i] == False:
            path.append(lst[i])
            used[i] = True
            dfs_permutation(lst,depth+1,used,path,res)
            # 回溯
            used[i] = False
            path.pop()

dfs_permutation(lst,0,used,path,res)
print(res)
# 输出 [['A', 'B', 'C'], ['A', 'C', 'B'], ['B', 'A', 'C'], ['B', 'C', 'A'], ['C', 'A', 'B'], ['C', 'B', 'A']]

DFS组合实现示例

lst = ["A", "B", "C"]
n = len(lst)
used = [False for i in range(n)]
path = []
res = []

def dfs_combination(lst,depth,start,used,path,res):
    # 产生一个组合
    if depth == len(path):
        res.append(path.copy())
        return

    for i in range(start,n):
        if used[i] == False:
            path.append(lst[i])
            used[i] = True
            dfs_combination(lst,depth,i+1,used,path,res)
            # 回溯
            used[i] = False
            path.pop()

for i in range(1,n+1):
    dfs_combination(lst,i,0,used,path,res)
print(res)
# 输出 [['A'], ['B'], ['C'], ['A', 'B'], ['A', 'C'], ['B', 'C']]

以上为Python通过内置函数和自写算法DFS实现排列组合的详细攻略，希望对大家有所帮助。

Tags: