Python实现字符串全排列：字典序与去重算法解析

一颗松果

发布时间：2026-10-13 | 2人浏览过

原创

本文详解Python实现字符串全排列的算法，重点解析如何处理含重复字符的情况及字典序输出。通过对比list的append与+运算区别，结合递归交换策略生成所有排列，并利用sorted函数高效实现字典序排序，最终提供完整的AC代码示例供参考。

本文通过具体实例介绍Python中字符串全排列的实现方法，旨在为读者提供清晰的参考与学习材料。

题目描述

要求输入一个字符串，并按字典序打印出该字符串中所有字符的全排列。以输入字符串“abc”为例，需输出由字符a、b、c组成的所有可能排列，包括abc、acb、bac、bca、cab和cba。

输入描述

输入为一个字符串，其长度不超过9。字符串中可能包含重复字符，且仅由大小写英文字母组成。

需要注意字符串中可能存在重复字符，因此算法需具备去重判断逻辑。此外，需明确区分list的append方法与+运算符的区别：append方法用于在列表末尾添加单个元素；而+运算符用于合并两个列表。若错误地使用append(list)，会导致整个列表作为一个单一元素被插入，而非展开添加。

swap函数负责将新元素与已有元素进行交换，并返回包含新排列的列表。每次交换操作后，通过append方法将结果元素插入到结果集中。

def swap(self, newElem, Elem):
 result = []
 listElem = list(Elem)
 listElem.insert(0, newElem)
 result.append(''.join(listElem))
 for i in range(1, len(listElem)):
 preList = listElem[:] #注意这个地方
 listElem[0], listElem[i] = listElem[i], listElem[0]
 if listElem != preList: #处理重复情况
 result.append(''.join(listElem))
 listElem[0], listElem[i] = listElem[i], listElem[0]
 return result

若错误地使用+方法进行拼接：

def swap(newElem, Elem):
 result = []
 listElem = list(Elem)
 listElem.insert(0, newElem)
 #result.append(''.join(listElem))
 result += ''.join(listElem)
 for i in range(1, len(listElem)):
 preList = listElem[:] # 注意这个地方
 listElem[0], listElem[i] = listElem[i], listElem[0]
 if listElem != preList: # 处理重复情况
  #result.append(''.join(listElem))
  result += ''.join(listElem)
 listElem[0], listElem[i] = listElem[i], listElem[0]
 return result
print(swap('1', '234'))
>>>>['1', '2', '3', '4', '2', '1', '3', '4', '3', '2', '1', '4', '4', '2', '3', '1']

通过递归调用函数来生成排列。

此处必须使用+号，因为每次递归调用的结果是一个包含多个元素的列表，需要将它们合并。若错误地使用append，则无法正确展开列表元素。

def recurtionPermutation(self, ss, index):
 result = []
 if index == 0:
 result.append(ss[0])
 else:
 previousList = self.recurtionPermutation(ss, index - 1)
 newElem = ss[index]
 #print(previousList)
 for Elem in previousList:
 result += self.swap(newElem, Elem) #这里返回的是一个数组，数组加数组使用+，数组加元素使用append符号
 return result

对生成的排列结果进行字典序排序。

虽然可以使用冒泡排序实现字典序，但这并非必要。直接比较字符大小并调用sorted函数即可更高效地完成排序。

使用sorted函数既便捷又高效。

def BubbleSortByDic(self, result):
 for i in range(len(result)):
 for j in range(len(result) - 1, i, -1):
 if result[j] < result[i]:
  result[i], result[j] = result[j], result[i]
 return result

AC代码：

class Solution:

 def swap(self, newElem, Elem):
 result = []
 listElem = list(Elem)
 listElem.insert(0, newElem)
 result.append(''.join(listElem))
 for i in range(1, len(listElem)):
  preList = listElem[:] #注意这个地方
  listElem[0], listElem[i] = listElem[i], listElem[0]
  if listElem != preList: #处理重复情况
  result.append(''.join(listElem))
  listElem[0], listElem[i] = listElem[i], listElem[0]
 return result
 def recurtionPermutation(self, ss, index):
 result = []
 if index == 0:
  result.append(ss[0])
 else:
  previousList = self.recurtionPermutation(ss, index - 1)
  newElem = ss[index]
  #print(previousList)
  for Elem in previousList:
  result += self.swap(newElem, Elem) #这里返回的是一个数组，数组加数组使用+，数组加元素使用append符号
 return result
 # def BubbleSortByDic(self, result):
 # for i in range(len(result)):
 #  for j in range(len(result) - 1, i, -1):
 #  if result[j] < result[i]:
 #   result[i], result[j] = result[j], result[i]
 # return result
 def Permutation(self, ss):
 # write code here
 if ss == '':
  return []
 #return self.BubbleSortByDic(self.recurtionPermutation(ss, len(ss) - 1))
 return sorted(self.recurtionPermutation(ss, len(ss) - 1))
print(Solution().Permutation('acdfb'))

更多关于Python相关内容感兴趣的读者可查看本站专题：《Python数学运算技巧总结》、《Python数据结构与算法教程》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程》

希望本文所述对大家Python程序设计有所帮助。