python3实现字符串的全排列的方法(无重复字符)
作者:7749ha 发布时间:2022-04-14 19:47:56
标签:python,字符串,全排列
最近在学一些基础的算法,发现我的数学功底太差劲了,特别是大学的这一部分,概率论、线性代数、高数等等,这些大学学的我是忘得一干二净(我当时学的时候也不见得真的懂),导致现在学习算法,非常的吃力。唉!不说了,补习中。。。
抛出问题
求任意一个字符串的全排列组合,例如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
0
投稿
猜你喜欢
- 一直在期待这本书,一直希望国内能有一本正视WEB标准,并且全面阐述WEB标准书籍。而这本书是我觉得国内最全面的一本关于WEB标准的书籍,这本
- 汉字转换为UTF-8的一段代码终于找到这段代码了,一个ASP写的中文转UTF-8,大家可以试试function chinese2u
- 效果图:作用:将页面中的电话号码生成图片格式。<%Public Sub Com_CreatValidCode(pT
- 笔者日积月累了许多精彩、实用的Web特效的制作,这些特效几乎都是比较常用的网页特效。现在我就把这些经过
- 代码如下:---这是一个人事系统中的示例,要求记录一下员工的缺勤情况 ---1.要在表中记录一下缺勤计分,是对经常缺勤者的一种处
- 本文介绍了使用XMlhttp技术来生成html页面,值得借鉴。相关函数:<% ’定义xmlhttp funct
- think-queue是ThinkPHP官方提供的一个消息队列服务,是专门支持队列服务的扩展包。think-queue消息队列适用于大并发或
- 1. lr_scheduler相关lr_scheduler = WarmupLinearSchedule(optimizer, warmup
- default-character-set=gbk #或gb2312,big5,utf8 然后重新启动mysql 运行->servic
- /*Bresenham画圆算法*/var arc = function(x0,y0,r){/*起点坐标x0,y
- <%dim ylj,ywj,Mlpath,Shell,rarcomm,RetCode,cmd,comm,fsoM
- 今天搭了个“发短信”的页面,找朋友测试,没想到一位大侠直接弄了本长篇小说发我手机上……为了我的宝贝手机能继续健康澎湃,给文本区域(texta
- 学习目的: 掌握文本框的用法 初次接触try…catch…语法 今天内容很轻松,用一个例子,输入年月日,判断输入是否正确 图片如下: 用个
- 在项目开发中,经常出现这样的需求。在新增或修改一个主表数据时,对应的从表也要进行同步,此时我们是怎么操作的了?典型的方法就是对于主表的各数据
- 有时候,我们需要将文本转换为图片,比如发长微博,或者不想让人轻易复制我们的文本内容等时候。目前类似的工具已经有了不少,不过我觉得用得都不是很
- 索引( Index )是常见的数据库对象,它的设置好坏、使用是否得当,极大地影响数据库应用程序和Database 的性能。虽然有许多资料讲索
- 1.认识数组数组就是某类数据的集合,数据类型可以是整型、字符串、甚至是对象Javascript不支持多维数组,但是因为数组里面可以包含对象(
- JavaScript Dom编程 学习书籍选择JavaScript Dom编程学习,很多朋友无疑对如何选择入门的书籍,比较头疼。或许也是他们
- 实现代码如下:# -*- coding: utf-8 -*-import math, random,timeimport threading
- python中的列表和元组# 1.列表的格式# [数据1,数据2,数据3,···]# 列表 可变数据类型# 列表可以存储多个数据,数据之间的