数据结构之栈与递归的应用（全排列递归解法）

今天药忘吃喽~ 2022-05-31 06:13 183阅读 0赞

上一节讲了一下汉诺塔的递归实现，这一节说一下全排列递归解法。

参考了[Casionx][]的博客，给博主带来的不便请原谅。[全排列算法思路解析][Link 1]

全排列递归解法

**全排列的定义和公式：**从n个数中选取m（m<=n）个数按照一定的顺序进行排成一个列，叫作从n个元素中取m个元素的一个排列。由排列的定义，显然不同的顺序是一个不同的排列。从n个元素中取m个元素的所有排列的个数，称为排列数。从n个元素取出n个元素的一个排列，称为一个全排列。全排列的排列数公式为n!，通过乘法原理可以得到。

我们现在做这样的一个假设，假设给定的一些序列中第一位都不相同，那么就可以认定说这些序列一定不是同一个序列，这是一个很显然的问题。有了上面的这一条结论，我们就可以同理得到如果在第一位相同，可是第二位不同，那么在这些序列中也一定都不是同一个序列。  
那么，这个问题可以这样来看。对 *T*=【*x*1,*x*2,*x*3,*x*4,*x*5,........*xn*−1,*xn*】  
我们获得了在第一个位置上的**所有情况**之后(注：是所有的情况)，对每一种情况，抽去序列*T*中的第一个位置，那么对于剩下的序列可以看成是一个全新的序列 *T*1=【*x*2,*x*3,*x*4,*x*5,........*xn*−1,*xn*】序列*T*1可以认为是与之前的序列毫无关联了。同样的，我们可以对这个*T*1进行与*T*相同的操作，直到*T*中只一个元素为止。这样我们就获得了所有的可能性。所以很显然，这是一个递归算法。第一位的所有情况：无非是将*x*1与后面的所有数*x*2,*x*3,.......*xn*依次都交换一次。

算法思路：全排列可以看做固定前i位，对第i+1位之后的再进行全排列，比如固定第一位，后面跟着n-1位的全排列。那么解决n-1位元素的全排列就能解决n位元素的全排列了，这样的设计很容易就能用递归实现。

void permutation(char s[], int b, int e)
    {
        if( (0 <= b) && (b <= e) )
        {
            if( b == e )
            {
                printf("%s\n", s);
            }
            else
            {
                int i = 0;
                
                for(i=b; i<=e; i++)
                {
                    char c = s[b];
                    s[b] = s[i];
                    s[i] = c;
                    
                    permutation(s, b+1, e);
                    
                    c = s[b];
                    s[b] = s[i];
                    s[i] = c;
                }
            }
        }
    }

我们来仔细推敲一下循环体里的代码，当我们对序列进行交换之后，就将交换后的序列除去第一个元素放入到下一次递归中去了，递归完成了再进行下一次循环。这是某一次循环程序所做的工作，这里有一个问题，那就是在进入到下一次循环时，序列是被改变了。可是，如果我们要假定第一位的所有可能性的话，那么，就必须是在建立在这些序列的初始状态一致的情况下,所以每次交换后，要还原，确保初始状态一致。

[递归应用C语言实现代码][C]

[Casionx]: http://blog.csdn.net/summerxiachen
[Link 1]: http://blog.csdn.net/summerxiachen/article/details/60579623
[C]: http://download.csdn.net/download/u014754841/10246751