python3实现字符串的全排列的方法(无重复字符)
作者:7749ha 时间:2022-04-14 19:47:56
最近在学一些基础的算法,发现我的数学功底太差劲了,特别是大学的这一部分,概率论、线性代数、高数等等,这些大学学的我是忘得一干二净(我当时学的时候也不见得真的懂),导致现在学习算法,非常的吃力。唉!不说了,补习中。。。
抛出问题
求任意一个字符串的全排列组合,例如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
#递归求结果
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)
......
这个可能我讲的不是特别清楚,理解起来不是特别容易,这种方式经过我的测试,发现他更费时。
自我感觉两种方法区别不大,原理上是一样的,都是先确定前面的部分,处理后边的,从后往前走。
来源:http://www.cnblogs.com/7749ha/p/9011093.html
标签:python,字符串,全排列
0
投稿
猜你喜欢
SQL Server中ISNULL函数介绍
2009-09-09 21:23:00
CSS样式表中继承关系的空格与不空格
2007-12-12 13:05:00
白鸦:界面烂还是界面设计烂?
2008-04-03 16:05:00
plsql与tsql的语法不同
2009-09-13 17:33:00
10个值得深思的PHP面试题
2023-11-15 00:35:37
列表模块是否需要标题
2009-06-25 14:11:00
在Python程序中进行文件读取和写入操作的教程
2023-05-22 10:31:56
用 onerror 获取错误信息 js Debug
2008-11-03 19:08:00
PHP商品秒杀问题解决方案实例详解【mysql与redis】
2023-09-27 10:49:04
python装饰器代替set get方法实例
2023-01-25 15:40:37
ASC码对照表
2008-08-07 13:07:00
另类读写:ACCESS中Field对象的标题属性
2008-11-28 16:47:00
Python实现Tracert追踪TTL值的方法详解
2023-06-24 13:08:14
js中的文档模式-document.compatMode
2009-08-14 20:30:00
Python绘制3d螺旋曲线图实例代码
2022-12-22 01:30:23
在Python中使用NLTK库实现对词干的提取的教程
2022-11-04 15:13:53
python PyTorch预训练示例
2022-07-06 18:24:02
WINDOWS 同时安装 python2 python3 后 pip 错误的解决方法
2023-07-01 11:01:00
SQL Server的BUILTIN\\Administrators用户
2009-02-04 13:51:00
python使用KNN算法手写体识别
2022-06-28 05:30:56