最近在学一些基础的算法，发现我的数学功底太差劲了，特别是大学的这一部分，概率论、线性代数、高数等等，这些大学学的我是忘得一干二净（我当时学的时候也不见得真的懂），导致现在学习算法，非常的吃力。唉！不说了，补习中。。。
抛出问题
求任意一个字符串的全排列组合，例如a='123',输出 123，132，213，231，312，321。（暂时假定字符串没有重复）
解决方案
目前有两种解决的方法
方法一：
|
1
2
3
4
5
6
7
8
9
10
11
12
|
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_liststr_list = str_sort('abc')print(len(str_list), str_list) |
这种理解起来非常好理解，就是循环遍历每个字符，让每个字符打头，然后继续递归遍历后边的字符
方法二：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
#字符串任意两个位置字符交换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_liststr_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
