温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

python求一个字符串的所有排列的实现方法

发布时间:2020-10-01 05:51:07 来源:脚本之家 阅读:515 作者:布欧不欧 栏目:开发技术

题目描述:

设计一个程序,当输入一个字符串时,要求输出这个字符串的所有排列。
例如输入字符串 abc,要求输出由字母 a、b、c 所能排列出来的所有字符串 abc,acb,bac,bca,cab,cba。

方法:递归法

以字符串 abc 为例介绍对字符串进行全排列的方法。
(1) 首先固定第一个字符 a,然后对后面的两个字符 b、c 进行全排列;
(2) 交换第一个字符与其后面的字符,即交换 a 与 b,然后对后面的两个字符 a与c 进行全排列;
(3) 由于第二步交换了 a与b 破坏了字符串原来的顺序,所以需要再次交换 a与b 使其恢复到原来的顺序,然后交换第一个字符与第三个字符(交换a和c),接着固定第一个字符c,对后面的两个字符 a与b 求全排列。
在对字符串求全排列的时候就可以采用递归的方式求解。

python求一个字符串的所有排列的实现方法

在使用递归求解的时候,要注意:
(1) 逐渐缩小问题的规模,并且可以用同样的方法来求解子问题;
(2) 递归一定要有结束条件,否则会导致程序陷入死循环;

代码实现:

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# @Time  : 2020/2/3 9:49
# @Author : buu
# @Software: PyCharm
# @Blog  :https://blog.csdn.net/weixin_44321080
def swap(str, i, j):
  # 交换字符数组下标为i和j对应的字符
  tmp = str[i]
  str[i] = str[j]
  str[j] = tmp


def permutation(str, start):
  """
  对字符串中的字符进行全排列
  :param str: 待排序的字符串,list
  :param start: 待排序的子字符串的首字符下标
  :return:
  """
  if str == None or start < 0:
    return
  if start == len(str) - 1:
    # 完成全排列后输出当前排列的字符串
    print(''.join(str),end=' ')
  else:
    i = start
    while i < len(str):
      # 交换start与i所在位置的字符
      swap(str, start, i)
      # 固定第一个字符,对剩余的字符进行全排列
      permutation(str, start + 1)
      # 还原start与i所在位置的字符
      swap(str, start, i)
      i += 1


def permutation_transe(s):
  str = list(s)
  permutation(str, 0)


if __name__ == '__main__':
  s = 'abc'
  permutation_transe(s)

结果:

python求一个字符串的所有排列的实现方法

算法性能分析:
假设这种方法所需的基本操作数为 f(n),f(n) = n×f(n-1) = …= n!
所以时间复杂度为O(n!);
空间复杂度为O(1);

引申:

如何去掉重复的排列?
当字符串中没有重复的字符的时候,它的所有组合对应的字符串就没有重复的情况;当时当字符串中有重复的字符的时候,例如 ‘baa',此时如果按照上面介绍的算法求全排列会有重复的字符串。
python求一个字符串的所有排列的实现方法

思路:
全排列的主要思路为:从第一个字符起每个字符分别与它们后面的字符进行交换:例如对于“baa”,交换 baa 第一个与第二个字符后得到“aba”,再考虑交换 baa 第一个与第三个字符后得到“aab”,由于 baa 的第二个字符与第三个字符相等,所以会导致两种交换方式得到的 aba 与 aab 对应的全排列是重复的(在固定aba与aab的第一个字符的情况下,它们对应的全排列都为 aba,aab)。
所以可以知道,去掉重复排列的主要思路为:
从第一个字符起,每个字符分别与它后面的非重复出现的字符进行交换。在递归的基础上只需要增加一个判断字符是否重复出现的函数即可。

代码实现:

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# @Time  : 2020/2/3 10:37
# @Author : buu
# @Software: PyCharm
# @Blog  :https://blog.csdn.net/weixin_44321080
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# @Time  : 2020/2/3 9:49
# @Author : buu
# @Software: PyCharm
# @Blog  :https://blog.csdn.net/weixin_44321080
def swap(str, i, j):
  # 交换字符数组下标为i和j对应的字符
  tmp = str[i]
  str[i] = str[j]
  str[j] = tmp

def isDuplicate(str,begin,end):
  """
  判断 [begin,end)区间中是否有字符与 *end相等
  :param begin: 指向字符的指针
  :param end: 指向字符的指针
  :return: 如果有相等的字符True,else False
  """
  i=begin
  while i<end:
    if str[i]==str[end]:
      return True
    else:
      i+=1
  return False


def permutation(str, start):
  """
  对字符串中的字符进行全排列
  :param str: 待排序的字符串,list
  :param start: 待排序的子字符串的首字符下标
  :return:
  """
  if str == None or start < 0:
    return
  if start == len(str) - 1:
    # 完成全排列后输出当前排列的字符串
    print(''.join(str),end=' ')
  else:
    i = start
    while i < len(str):
      # 若有重复字符,则终止当前循环,开始下一次循环
      if isDuplicate(str,start,i):
        i+=1
        continue
      # 交换start与i所在位置的字符
      swap(str, start, i)
      # 固定第一个字符,对剩余的字符进行全排列
      permutation(str, start + 1)
      # 还原start与i所在位置的字符
      swap(str, start, i)
      i += 1


def permutation_transe(s):
  str = list(s)
  permutation(str, 0)


if __name__ == '__main__':
  s = 'baa'
  permutation_transe(s)

结果:

python求一个字符串的所有排列的实现方法

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持亿速云。

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI