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
#递归求结果
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)

......

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

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

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

时间: 2018-07-07

python中字符串数组逆序排列方法总结

python中字符串数组如何逆序排列?下面给大家介绍几种方法: 1.数组倒序: 原始元素的倒序排列 (1)切片 >>> arr = [1,2,3,4,3,4]>>> print (arr[::-1])[4, 3, 4, 3, 2, 1] (2)reverse() >>> arr = [1,2,3,4,3,4]>>> arr.reverse()>>> print (arr)[4, 3, 4, 3, 2, 1] (3)r

Python字符串的全排列算法实例详解

本文实例讲述了Python字符串的全排列算法.分享给大家供大家参考,具体如下: 题目描述 输入一个字符串,按字典序打印出该字符串中字符的所有排列.例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba. 输入描述 输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母. 注意有可能重复,因此需要判断 注意list的append方法和list的+方法的区别 append方法在list后面添加元素 +方法在list后面添加l

python中的decimal类型转换实例详解

[Python标准库]decimal--定点数和浮点数的数学运算 作用:使用定点数和浮点数的小数运算.         Python 版本:2.4 及以后版本 decimal 模块实现了定点和浮点算术运算符,使用的是大多数人所熟悉的模型,而不是程序员熟悉的模型,即大多数计算机硬件实现的 IEEE 浮点数运算.Decimal 实例可以准确地表示任何数,对其上取整或下取整,还可以对有效数字个数加以限制. Decimal 小数值表示为 Decimal 类的实例.构造函数取一个整数或字符串作为参数.使用

java 中模式匹配算法-KMP算法实例详解

java 中模式匹配算法-KMP算法实例详解 朴素模式匹配算法的最大问题就是太低效了.于是三位前辈发表了一种KMP算法,其中三个字母分别是这三个人名的首字母大写. 简单的说,KMP算法的对于主串的当前位置不回溯.也就是说,如果主串某次比较时,当前下标为i,i之前的字符和子串对应的字符匹配,那么不要再像朴素算法那样将主串的下标回溯,比如主串为"abcababcabcabcabcabc",子串为"abcabx".第一次匹配的时候,主串1,2,3,4,5字符都和子串相应的

Python 高级专用类方法的实例详解

Python 高级专用类方法的实例详解 除了 __getitem__ 和 __setitem__ 之外 Python 还有更多的专用函数.某些可以让你模拟出你甚至可能不知道的功能.下面的例子将展示 UserDict 一些其他专用方法. def __repr__(self): return repr(self.data) (1) def __cmp__(self, dict): (2) if isinstance(dict, UserDict): return cmp(self.data, dic

python+requests+unittest API接口测试实例(详解)

我在网上查找了下接口测试相关的资料,大都重点是以数据驱动的形式,将用例维护在文本或表格中,而没有说明怎么样去生成想要的用例, 问题: 测试接口时,比如参数a,b,c,我要先测a参数,有(不传,为空,整形,浮点,字符串,object,过短,超长,sql注入)这些情况,其中一种情况就是一条用例,同时要保证b,c的正确,确保a的测试不受b,c参数的错误影响 解决思路: 符合接口规范的参数可以手动去填写,或者准备在代码库中.那些不符合规范的参数(不传,为空,整形,浮点,字符串,object,过短,超长,

Python内建模块struct实例详解

本文研究的主要是Python内建模块struct的相关内容,具体如下. Python中变量的类型只有列表.元祖.字典.集合等高级抽象类型,并没有像c中定义了位.字节.整型等底层初级类型.因为Python本来就是高级解释性语言,运行的时候都是经过翻译后再在底层运行.如何打通Python和其他语言之间的类型定义障碍,Python的内建模块struct完全解决了所有问题. 知识介绍: 在struct模块中最最常用的三个: (1)struct.pack:用于将Python的值根据格式符,转换为字符串(因

Python字符串格式化%s%d%f详解

关于讨论输出格式化的问题,小编不是一时兴起,之前学习python的时候就经常遇到输出时"%d",一直没有仔细学习,今天又看到了,下面分享一个简单实例,python输出99乘法表: #!/usr/bin/python # -*- coding: UTF-8 -*- for i in range(1, 10): print for j in range(1, i+1): print "%d*%d=%d" % (i, j, i*j), 结果: 1*1=1 2*1=2 2*

KnockoutJS数组比较算法实例详解

这篇文章主要介绍了KnockoutJS数组比较算法实例详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 前端开发中,数组是一种非常有用的数据结构.这篇博客会解释并分析KnockoutJS实现中使用的数据比较算法. 算法的目的 KnockoutJS使用MVVM的思想,view model中的数组元素会对应data model中的数组数据,当用户进行输入或者请求后台时,数组数据会发生变更, 从而带动UI的更新.例如购物车类的页面,用户可以通过点击

Python 通过URL打开图片实例详解

Python 通过URL打开图片实例详解 不论是用OpenCV还是PIL,skimage等库,在之前做图像处理的时候,几乎都是读取本地的图片.最近尝试爬虫爬取图片,在保存之前,我希望能先快速浏览一遍图片,然后有选择性的保存.这里就需要从url读取图片了.查了很多资料,发现有这么几种方法,这里做个记录. 本文用到的图片URL如下: img_src = 'http://wx2.sinaimg.cn/mw690/ac38503ely1fesz8m0ov6j20qo140dix.jpg' 1.用Open

Python命令启动Web服务器实例详解

Python命令启动Web服务器实例详解 利用Python自带的包可以建立简单的web服务器.在DOS里cd到准备做服务器根目录的路径下,输入命令: python -m Web服务器模块 [端口号,默认8000] 例如: python -m SimpleHTTPServer 8080 然后就可以在浏览器中输入 http://localhost:端口号/路径 来访问服务器资源. 例如: http://localhost:8080/index.htm(当然index.htm文件得自己创建) 其他机器