Python实现全排列：回溯法与深度优先搜索详解

从n个不同元素中取出m（m≤n）个元素，按特定顺序排列称为排列；当m等于n时，所有可能的排列情况即为全排列。

全排列数量计算公式为f(n)=n!，其中规定0!=1。

回溯法实现全排列

1 递归实现全排列（回溯思想）

1.1 思想

以a,b,c三个字符的全排列为例，结果包括abc,acb,bac,bca,cba,cab共六种。当指针指向第一个元素a时，可与自身或后续元素b、c交换，产生3种分支；确定首元素后，指针移至第二位，该位置可与自身及剩余元素交换，形成更多分支；当指针到达最后一个元素c且无后续元素时，确定一组完整排列并输出。每次输出后需恢复数组原始状态以继续搜索。

1.2 python实现

def permutations(arr, position, end):
  if position == end:
    print(arr)
  else:
    for index in range(position, end):
      arr[index], arr[position] = arr[position], arr[index]
      permutations(arr, position + 1, end)
      arr[index], arr[position] = arr[position], arr[index] # 还原到交换前的状态，为了进行下一次交换
 
 
arr = [1, 2, 3, 4]
permutations(arr, 0, len(arr))

深度优先搜索（DFS）实现全排列

2 深度优先搜索（DFS）实现全排列

2.1 思想

定义问题：输入长度为n的列表arr，输出其全排列。

（1）每种全排列结果列表长度均为n。想象有n个空盒子，需将n个数放入其中，每盒仅放一个数。第一个盒子有n种选择，可通过循环逐一尝试。

for index in range(0, len(arr)): temp[position] = arr[index]

（2）第一个盒子放置后，处理第二个盒子。若第一个盒子放了arr的第一个数，则第二个盒子只能从第2至n个数中选择（避免重复）。为此引入visit列表标记arr中已使用的数字。初始化示例：

visit = [True, True, True, True]

当第一个位置被使用时，在visit中做标记：visit = [False, True, True, True]。

因此，放置第一个盒子的代码可改写为：

  for index in range(0, len(arr)):
    if visit[index] == True:
      temp[position] = arr[index]
      visit[index] = False

（3）第k个盒子处理完毕后，直接调用dfs(k+1)处理下一个盒子，即递归调用。明确当前步骤后，后续步骤自然清晰。

（4）递归必须设定出口，否则无限循环将导致程序崩溃。本例中，当n个盒子全部填满（即处理到第n+1个盒子时）结束递归，并输出当前排列结果。

2.2 python实现

visit = [True, True, True, True]
temp = ["" for x in range(0, 4)]
 
 
def dfs(position):
  # 递归出口
  if position == len(arr):
    print(temp)
    return
  # 递归主体
  for index in range(0, len(arr)):
    if visit[index] == True:
      temp[position] = arr[index]
      visit[index] = False # 试探 
      dfs(position + 1)
      visit[index] = True # 回溯。非常重要
 
 
arr = [1, 2, 3, 4]
dfs(0)

注释中“非常重要”的语句不可省略，否则仅输出[1, 2, 3, 4]单一结果。dfs(k+1)前后的两条语句分别称为试探和回溯。

itertools中permutations与combinations的区别

3 combination和permutations函数的区别

permutations方法侧重排列：

import itertools
n=3
a=[str(i) for i in range(n)]
s=""
s=s.join(a)
for i in itertools.permutations(s,n):
  print (''.join(i))
 
# 结果  
012
021
102
120
201
210

combinations方法侧重组合：

import itertools
n=3
a=[str(i) for i in range(n)]
s=""
s=s.join(a)
for i in itertools.combinations(s,n):
  print (''.join(i))
 
# 结果  
012

以上为Python实现全排列代码（回溯、深度优先搜索）的完整分享，供参考。