全排列算法解析

欢迎大家来到IT世界,在知识的湖畔探索吧!

对一个串abc, 它的全排列是：

abc, acb, bac, bca, cab, cba

共有3X2 = 6种。如何从代码层面实现这样的功能呢？设permutate(E)表示E的一个全排列,对abc来说，它的全排列可以表示成：

permutate({a, b, c}) = {a+permutate({b, c}), b + permutate({a, c}), c + permutate({a, b})}

又

permutate({b, c}) = {b + permutate({c}, c + permutate({b}))}

以此类推。可以看到子问题和主问题是同样的模式，这时，我们的脑海里应该闪现出递归这两个字。是的，递归是解决这个问题的好办法。说到递归，我们就要解决两个问题；一个是递归的base，也就是最基本的操作问题，第二个是规模减小的问题，因为递归总是将大问题变成同样的小问题，至到base。对全排列来说，base就是只剩一个元素的时候，

permutate({b}) = b

permutate({c}) = c

一个元素的全排列是它本身，没毛病。那当元素个数大于1时，我们可以设Ei表示集体E移除元素i之后的的集合，对集体E={a b c}来说, 其全排列可表示成：

a+permutate(Ea), b + permutate(Eb), c + permutate(Ec)

可以看到，需要将每个元素作为前缀，然后，对除该元素之外的其它元素进行全排列, 在这个过程中，集合的size会不断变小直至为1，perfect!

那么，伪代码思路应该是

permutate(T list[], size) {

if size == 1 then return list[0]

else {

for i from 0 to size – 1 do

{

swap(list[0], list[i])

permutate(list + 1, size -1)

swap(list[0], list[i])

}

}

}

思路是这样，没毛病。细节上会不会有问题呢？好像是有的，上面的伪代码中, permutate(list + 1, size -1)这儿有点小问题，那就是子问题不知道自己的前缀是什么，怎么办？有几种办法，一种是用全局的东西来记住前缀，另一种是传递位置变量进去。这儿选用第二种方法。至此，算法的思维流程已完，开始C++代码表演。

欢迎大家来到IT世界,在知识的湖畔探索吧!

运行结果如下

看起来很6，mission completed!