全排列的经典算法.txt

这个程序是按照离散数学教材上给出的算法写的

全排列的经典算法 
　　这个程序是按照离散数学教材上给出的算法写的，是字典序的全排列算法。空间复杂度是O(n)，时间复杂度基本上是O(n^2)。缺点是只用于打印并没有储存所有的结果。
　　代码如下：

#include <iostream.h>
#define N 5 // C的动态数组比较麻烦，这里就回避了

int a[N+1];
void exchange(int& x);
void swap(int& a, int& b);

void main()
{
　　int i;
　　int y=1;
　　int x;
　　for (i=1;i<=N;i++)
　　　　a=i;
　　do
　　{
　　　　cout<<y<<"　--->　";
　　　　for (i=1;i<=N;i++)
　　　　　　cout<<a;
　　　　cout<<endl;
　　　　x=0;
　　　　y++;
　　　　exchange(x);
　　}while (x!=0);
　　return 0;
}

void exchange(int& x)
{
　　int i;
　　int j;
　　for (i=1;i<=N-1;i++)
　　　　if (a<=a[i+1])
　　　　　　x=i;
　　if (x!=0)
　　{
　　　　for (i=x;i<=N;i++)
　　　　　　if (a[x]<=a)
　　　　　　　　j=i;
　　　　swap(a[x],a[j]);
　　　　for (i=x+1;i<=N;i++)
　　　　{
　　　　　　if (i!=N+x+1-i)
　　　　　　　　swap(a,a[N+x+1-i]);
　　　　　　if ((i+1)*2>N+x+1)
　　　　　　　　break;
　　　　}
　　}
}

void swap (int& a, int& b)
{
　　a=a+b;
　　b=a-b;
　　a=a-b;
}