龙空技术网

全排列算法解析

hittlle 86

前言:

此时同学们对“算法中的全排列”大概比较重视,你们都想要剖析一些“算法中的全排列”的相关文章。那么小编也在网上网罗了一些关于“算法中的全排列””的相关文章,希望姐妹们能喜欢,小伙伴们一起来了解一下吧!

对一个串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++代码表演。

运行结果如下

看起来很6,mission completed!

标签: #算法中的全排列 #全局配算法 #递归求全排列c完整代码 #全排列的算法 #全排列的算法是什么