n!.txt

将1到N的N个自然数排成一列,共有1*2*3……*N种不同的排列方法,如N=3时,有6种排列方案,分别为123,132,213,231,312,321.试编程序输出1到N的全部排列,假设N<10

将1到N的N个自然数排成一列,共有1*2*3……*N种不同的排列方法,如N=3时,有6种排列方案,分别为123,132,213,231,312,321.试编程序输出1到N的全部排列,假设N<10.   
  为了设计出由计算机输出1到N的全部排列程序,就必须寻找不同排列之间的规律.通过观察N=5(参见本例的运行结果)的排列情况,可以发现,如果把每个排列看作一个自然数,
则所有排列对应的数是按从小到大的顺序排列,从当前的排列产生下一个排列时必然会造成某一位置上的数字变大,这一位置显然应该尽量靠右,
并且在它左边位置上的数字保持不变,这就意味着这一位置变成的数字来自于它的右边,   并且变大的幅度要尽可能小,也就是说在它右边如有几个数同时比它大时,
应该用其中最小的来代替它.由于这一位置是满足上述条件的最右边的一位,所以在它右边的所有数字按逆序排列,即在这些数字的右边没有一个大于它的数.
程序中先从右至左找到第一个位置,该位置上的数比它右边的数小,这个位置就是所要找的满足上述条件的位置,然后再从右到左找到第一个比该位置上的数字大的数字所在的位置,
将这两个位置上的数字交换,再将该位置右边的所有元素颠倒过来,即将它们按从小到大的顺序排列,就得到了下一个排列.       
    
  /*   
    
    
  #include<iostream>   
  using   namespace   std;   
    
  void   main(){   
        int   n;                                     //n个数字的排列;   
        cout<<"input:";   
        cin>>n;   
        int   *p=new   int[n];                   //数组保存各位数字;   
        for(int   i=0;i<n;i++)             //初始化为第一个排列;   
              p[i]=i+1;   
        do{   
              for(i=0;i<n;i++)             //输出排列中的数字   
                    cout<<p[i]<<"   ";   
              cout<<endl;               
              for(int   j=n-1;j>0;j--)       //从右向左;找要交换的位置1(j);   
                    if(p[j]>p[j-1])   break;   
              if(j==0)break;                   //找不到要交换的位置.退出do   
              j--;   
              for(int   k=n-1;k>j;k--)       //在位置1右边;从右向左;   
                                                  //找要交换的位置2(k);   
                    if(p[k]>p[j])break;   
              swap(p[k],p[j]);             //交换位置1和位置2的值;   
              //把位置1后边的所有位反序排列;   
              for(int   x=j+1,y=n-1;x<y;x++,y--)   
                    swap(p[x],p[y]);   
        }while(1);   
  delete   []p;   
  }