xmu 1005 解题

这个题从网上看到了一些 算法的解释，稍微改变了一下，其实质是一样的。

1. 排列 1 2 ； 1 2 、和 2 1

2. 排列 1 2 3； 1 2 3 、1 3 2、2 1 3、2 3 1、3 1 2 、3 2 1
上面的可以看作 1（2 3 ）、2 （1 3 ）、3 （1 2）
其中（ a b ）表示a和b两个数的排列

3. 排列 1 2 3 4 ，就有4！= 24种了
可以看作 1 (2 3 4) 、2（1 3 4 ）、3（1 2 4 ）、4
（1 2 3），这四种可能的全排列；其中（a b c）就是这三个数 a b c 的全排列。请注意他们的顺。这个很重要。因为在该题中，要求是按字典顺序来给出排列，在代码中就能发现，简单交换是不能满足这个题目要求的。

4. 排列（a1 a2 a3 a4 a5 a6 .......an) ，从上面总结的规律递推：
a1 (a2 a3 a4 a5 a6 ........an)
a2 (a1 a3 a4 a5 a6 ........an)
a3 (a1 a2 a4 a5 a6 ........an)
a4 (a1 a2 a3 a5 a6 ........an)
a5 (a1 a2 a3 a4 a6 ........an)
. . . .
. . . .
. . . .
an(a1 a2 a3 a4 a5 a6 ........an-1)
代码在右侧给出，不怎么精炼啊，请见谅！

#include<iostream>
#include<cstdlib>
using namespace std ;
void swap(int *list,int p, int q)
{
     int temp ;
     temp = list[q];
     if(p!=q){
     for(int i=q;i>p;i--)
     list[i]=list[i-1];
     list[p]=temp;
     }
}
void iswap(int *list,int p , int q)
{
     int temp ;
     temp = list[p];
     if(p!=q){
     for(int i=p;i<q;i++)
     list[i]=list[i+1];
     list[q]=temp;
     }
}
void perm(int* list,int m, int n)
{
     if(m==n) { //only one elemnt

     for(int i=0;i<=n;i++)
     cout<<list[i]<<" ";
     cout<<endl;
     }
     else {
     for(int j=m;j<=n;j++) {
     swap(list,m,j);
     perm(list,m+1,n);
     iswap(list,m,j);
     }
     }
}
int main()
{
    int N ;
    int array[10];
    cin>>N ;
    if(N>0) {
    for(int i=0;i<N;i++) //initialize the array
    array[i]=i+1;
    perm(array,0,N-1);
    }
    system("pause");
    return 0 ;
}