前言:
此时同学们对“算法中的全排列”大概比较重视,你们都想要剖析一些“算法中的全排列”的相关文章。那么小编也在网上网罗了一些关于“算法中的全排列””的相关文章,希望姐妹们能喜欢,小伙伴们一起来了解一下吧!对一个串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完整代码 #全排列的算法 #全排列的算法是什么