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

抛出问题

求任意一个字符串的全排列组合,例如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)

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

方法二:


#字符串任意两个位置字符交换
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
#Python学习交流QQ群:489111204
#递归求结果
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)

......

这个可能我讲的不是特别清楚,理解起来不是特别容易,这种方式经过我的测试,发现他更费时。

自我感觉两种方法区别不大,原理上是一样的,都是先确定前面的部分,处理后边的,从后往前走。

本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:python3实现字符串的全排列的方法(无重复字符)两种解决方法 - Python技术站

(0)
上一篇 2023年3月31日
下一篇 2023年3月31日

相关文章

  • Python中可以用三种方法判断文件是否存在

    通常在读写文件之前,需要判断文件或目录是否存在,不然某些处理方法可能会使程序出错。所以最好在做任何操作之前,先判断文件是否存在。 这里将介绍三种判断文件或文件夹是否存在的方法,分别使用os模块、Try语句、pathlib模块。 1.使用os模块 os模块中的os.path.exists()方法用于检验文件是否存在。 判断文件是否存在 import os os…

    Python开发 2023年4月2日
    00
  • python3教程:默认参数为列表

    默认参数的坑 定义一个函数,传入一个list,添加一个end再返回 def add_end(L=[]): L.append(‘END’) return L 正常调用时,结果似乎不错 print (add_end([1,2,3])) #[1, 2, 3, ‘END’] 使用默认参数调用时,一开始结果也是对的,但是再次调用时,结果就不对了 ”’ 学习中遇到问题…

    Python开发 2023年4月2日
    00
  • Python第三方库安装教程、什么是第三方库

    Python有一个全球社区:https://pypi.org/,在这里我们可以搜索任何主题的Python第三方库。PyPI全称是Python Package Index,指的是Python包的索引,它由PSF(Python Software Foundation)来维护,并且展示全球Python计算生态。 我们需要学会利用PyPI的主站检索,找到我们使用和关…

    python 2023年5月8日
    00
  • Python递归的几个经典案例

    当我们碰到诸如需要求阶乘或斐波那契数列的问题时,使用普通的循环往往比较麻烦,但如果我们使用递归时,会简单许多,起到事半功倍的效果。这篇文章主要和大家分享一些和递归有关的经典案例,结合一些资料谈一下个人的理解,也借此加深自己对递归的理解和掌握一些递归基础的用法。 一、递归的简介 1、递归的百度百科定义 程序调用自身的编程技巧称为递归( recursion)。 …

    Python开发 2023年4月2日
    00
  • Python关于异常处理的教程

    一、什么是异常 异常就是程序运行时发生错误的信号(在程序出现错误时,则会产生一个异常,若程序没有处理它,则会抛出该异常,程序的运行也随之终止),在python中,错误触发的异常如下 1 语法错误 语法错误,根本过不了python解释器的语法检测,必须在程序执行前就改正。 # 语法错误示范一 if # 语法错误示范二 def test: pass # 语法错误…

    Python开发 2023年3月31日
    00
  • Http和Https的区别?

    1.HTTP是什么? http是超文本传输协议用来在web浏览器和网站服务器之间传递数据信息,http以明文的方式发送内容,不提供任何方式的数据加密,如果攻击者截获了Web浏览器和网站服务器之间的传输报文,就可以直接读懂其中的信息,因此,HTTP协议不适合传输一些敏感信息,比如:信用卡号、密码等支付信息。为了解决http协议的这一缺陷,需要使用另一种协议:安…

    Python开发 2023年4月2日
    00
  • Python学习:property装饰器

    1.property 装饰器:装饰器是在不修改被装饰对象源代码以及调用方式的前提下为被装饰对象添加新功能的可调用对象 property是一个装饰器,是用来绑定给对象的方法伪造成一个数据属性 装饰器property,可以将类中的函数“伪装成”对象的数据属性,对象在访问该特殊属性时会触发功能的执行,然后将返回值作为本次访问的结果。 使用property有效地保证…

    Python开发 2023年4月2日
    00
  • Python迭代器是啥?

    迭代器:迭代的工具。迭代是更新换代,如你爷爷生了你爹,你爹生了你,迭代也可以说成是重复,并且但每一次的重复都是基于上一次的结果来的。如计算机中的迭代开发,就是基于软件的上一个版本更新。以下代码就不是迭代,它只是单纯的重复 while True: print(‘*’*10) 一、可迭代对象 python中一切皆对象,如 x = 1 name = ‘nick’ …

    Python开发 2023年3月31日
    00
合作推广
合作推广
分享本页
返回顶部