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

yipeiwu_com5年前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)

......

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

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

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持【听图阁-专注于Python设计】。

相关文章

15行Python代码实现网易云热门歌单实例教程

15行Python代码实现网易云热门歌单实例教程

0. 引言 马上314情人节就要来了,是否需要一首歌来抚慰你,受伤或躁动的心灵。来吧,今天教你用15行代码搞定热门歌单。学起来并听起来吧。 本文使用的是Selenium模块,它是一个自...

Python实现正则表达式匹配任意的邮箱方法

Python实现正则表达式匹配任意的邮箱方法

首先来个简单的例子,利用Python实现匹配163邮箱的代码: #-*- coding:utf-8 -*- __author__ = '杨鑫' import re text = in...

Python实现螺旋矩阵的填充算法示例

Python实现螺旋矩阵的填充算法示例

本文实例讲述了Python实现螺旋矩阵的填充算法。分享给大家供大家参考,具体如下: afanty的分析: 关于矩阵(二维数组)填充问题自己动手推推,分析下两个下表的移动规律就很容易咯。...

一个Python最简单的接口自动化框架

一个Python最简单的接口自动化框架

故事背景 读取一个Excel中的一条数据用例,请求接口,然后返回结果并反填到excel中。过程中会生成请求回来的文本,当然还会生成一个xml文件。具体的excel文件如下: 代码方案...

对python pandas读取剪贴板内容的方法详解

我使用的Python3.5,32版本win764位系统,pandas0.19版本,使用df=pd.read_clipboard()的时候读不到数据,百度查找解决方法,找到了一个比较靠谱的...