28

问答题 28 /50

求1~20的整数的全排列。

参考答案

整数的全排列问题:循环移位法,递归
循环移位法是一种很容易理解的非有序全排列算法,它的原理是:如果已经生成了K-1个元素的排列,则在每个排列后添加元素k使之成为k个元素的排列,然后将每个排列循环左移,每移动一次就产生一个新的排列。
例如2个元素的排列是 1 2 和 2 1,在1 2后加上成为新排列 1 2 3,将它循环左移可再生成新排列 2 3 1、3 1 2, 同样 2 1 可生成新排列 2 1 3、 1 3 2和3 2 1.
代码也很简单,使用了递归穷举思想,下面是一个循环左移的算法:
void Permutation(int n)
 {
     unsigned int *a = new unsigned int[n];//用来存储n个自然数
     for (int i=0; i<n; i++) //存储全排列的元素值,并计算全排列的数量
     {
         a[i] = i + 1;
     }
    
     Recursion(a, n, 1);  
     delete []a;
 }
  
 void Recursion(unsigned int a[], int n, int k)
 {
     if (k > n)
         Print(a, n);
     else
     {
         int temp;
         for (int i=0; i<k; i++)//循环左移
         {
             temp = a[0];
             for (int j=1; j<k; j++)
                 a[j-1] = a[j];
             a[k-1] = temp;           
             Recursion(a, n, k+1);
         }
     }
 }
非递归算法
#include <stdio.h>
 void swap(int &a, int &b)
 {
     int temp;
     temp = a;
     a = b;
     b = temp;
 }
 bool nextPermutation(int *p, int n)
 {
     int last=n-1;
     int i,j,k;
     //从后向前查找,看有没有后面的数大于前面的数的情况,若有则停在后一个数的位置。
     i=last;
     while(i>0&&p[i]<p[i-1])
         i--;
     //若没有后面的数大于前面的数的情况,说明已经到了最后一个排列,返回false。
     if(i==0)
         return false;
     //从后查到i,查找大于p[i - 1]的最小的数,记入k
     k=i;
     for(j=last; j>=i; j--)
         if(p[j]>p[i-1]&&p[j]<p[k])
             k =j;
     //交换p[k]和p[i - 1]
     swap(p[k],p[i-1]);
     //倒置p[last]到p[i]
    
     return true;
 }
 //显示一个排列
 void showPermutation(int *p, int n)
 {
     for(int i=0; i<n; i++)
         printf("%d ",p[i]);
     printf("\n");
 }
 int main(int argc, char *argv[])
 {
     int n;
     int *p;
     scanf("%d",&n);
     p = new int[n];
     for (int i = 0; i < n; i++)
         p[i] = i + 1;
     showPermutation(p, n);
     while(nextPermutation(p, n))
     {
         showPermutation(p, n);
     }
     //delete[] p;
     return 0;
 }
主要的任务在nextPermuation()中完成。这其中的思想是,提供一个已经有的全排列P,求出P的“下一个”全排列。这里“下一个”的意思是说,在n个数的n!个全排列在数字上从小到大的一个序列中,p的下一个数字上比它大的一个排列。
那么由此,提供一个初始的n个数的全排列P1 = p1p2…pn,有pi > pi – 1(1 < i < n – 1),反复运行nextPermuation()找出比P的“下一个”全排列,直到Pn! = p1’p2’…pn’,pi < pi – 1
(1 < i < n – 1)为止。所找到的所有的排列就是n的全排列。
下面要考虑的问题,是如何从一个已知的排列P = p1p2…pn,找到它的下一个排列
Q = q1q2…qn。我们要让排列从小到大生成,简单说,要让排列的趋势从p1p2…pn,pi > pi – 1(1 < i < n – 1),到p1’p2’…pn’,pi < pi – 1(1 < i < n – 1)。因此:
1. 从低位到高位(从后向前),找出“不符合趋势”的数字。即找到一个pi,使pi – 1 < pi。若找不到这样的pi,说明我们已经找到最后一个全排列,可以返回了。
2. 把pi - 1替换成从pn到pi几个数字中“刚刚好大于pi-1”的数字。这里的目的是找出准确的P的下一个排列Q。所谓“刚刚好大于”,我们就查找从pi到pn中大于pi-1的最小的数字。然后将找到的数字与pi-1交换。
3. 还没有结束。交换后,pi-1pi…pn并不是准确的后一个排列。因为根据第一步的查找,我们有pi > pi+1 > … > pn,否则查找在i~n就会停下来了。这样的一个排列显然不是最小的。实际上,原来的pi…pn,已经是这一部分最大的一个排列了。但我们现在换了最高位pi-1,因此要让后面的数字变的最小。方法很简单,根据上面的推理,我们只须将pi~pn的数列倒置即可(最大的排列倒置就变成了最小的排列)。这样,我们计算出了准确的下一个排列。
ps:这个主要的思想就是,当每次我们交换完之后,交换之后的后面的部分是一个符合趋势的排列,为了得到所有的排列,我们将其反转,那就相当于对其部分再进行一次方向最大排列的问题。倒过来再倒过去从而达到了遍历。