python3实现字符串的全排列的方法(无重复字符)

枫铃3年前 (2021-09-30)Python239

抛出问题

求任意一个字符串的全排列组合，例如a='123',输出 123，132，213，231，312，321。（暂时假定字符串没有重复）

解决方案

目前有两种解决的方法

方法一：

def str_sort(s=''):
  if len(s) <= 1:
    return [s]
  str_list = []
  for i in range(len(s)):
    for j in str_sort(s[0:i] + s[i + 1:]):
      str_list.append(s[i] + j)
  return str_list
 
 
str_list = str_sort('abc')
print(len(str_list), str_list)

这种理解起来非常好理解，就是循环遍历每个字符，让每个字符打头，然后继续递归遍历后边的字符

方法二：

'''
遇到问题没人解答？小编创建了一个Python学习交流QQ群：778463939
寻找有志同道合的小伙伴，互帮互助,群里还有不错的视频学习教程和PDF电子书！
'''
#字符串任意两个位置字符交换
def str_replace(str, x, y):
  if x == y:
    return str
  x_val = str[x:x+1]
  y_val = str[y:y+1]
  if x < y:
    str = str[0:x] + y_val + str[x+1:y] + x_val + str[y+1:len(str)]
  else:
    str = str[0:y] + x_val + str[y+1:x] + y_val + str[x+1:len(str)]
  return str
#递归求结果
def str_sort(str,x):
  if x == len(str):        #当x为字符串的最大长度时返回当前字符交换的结果
    global str_list
    str_list.append(str)
    return
  for i in range(x,len(str)):
    str = str_replace(str,i,x) #递归遍历第i个字符，
    str_sort(str,x+1)
    str = str_replace(str,x,i) #恢复字符串原来的顺序，便于下次遍历
s = 'abc'
global str_list
str_list = []
str_sort(s,0)
print(len(str_list), str_list)

这种方法在求解的思路上就已经有了很大的提升，不是像上一个靠“蛮力”去解决问题，这是递归的一种方式，大概原理就是，先保持前I个字符不变，遍历交换后边的字符，这样一直递归到，最后两个字符，然后再返回去改变倒数第三个字符，再次遍历后边的两位，直到三个字符的全部输出，也就是这样的顺序，

第一次输出　　X(n),X(n-1),X(n-2),......X(3),X(2),X(1)

第二次输出　　X(n),X(n-1),X(n-2),......X(3),X(1),X(2)

第三次输出　　X(n),X(n-1),X(n-2),......X(2),X(3),X(1)

第四次输出　　X(n),X(n-1),X(n-2),......X(2),X(1),X(3)

......