#include

#include

//2013-4-21

//n个数全排列

//使用穷举法实现 假设 n=3 的情况,根据n使用不同层的for循环

void Brute_Force_Full_Array()

{

int i,j,k,n,count;

n = 3; count = 0;

for (i = 1; i<=n;i++)

{

for (j = 1;j<=n;j++)

{

//在i!=j的情况下，穷举第三个数

for (k = 1;i!=j && k<=n;k++)

{

//在第三个和第一个、第二个均不同的情况下，输出

if (k!=i && k!=j)

{

printf("count,%d:%d %d %d\n",++count,i,j,k);

}

}

}

}

}

//使用穷举法，只适合n值较小的情况。因而，一般情况，选择使用递归实现

//递归实现，主要思想是利用动态规划，不断地交换数字的位置

//此方法不仅能实现数字全排列，还能实现任意字母组合全排列

//只要在修改data数字输入部分即可。例如:abc acb bac bca cab cba

int data[10];//存放1...9

int n;

void Swap(int& a,int& b)

{

int temp;

temp = a; a = b; b = temp;

}

void Recursion_Full_Array(int t)

{

int i;

//输出一个排列

if (t == n)

{

for (int i = 1;i<=n;i++)

{

printf("%d",data[i]);

}

printf("\n");

return;

}

for (i = t;i<=n;i++)

{

Swap(data[i],data[t]);

Recursion_Full_Array(t+1);

Swap(data[i],data[t]);//恢复到交换前状态

}

}

int main()

{

//穷举实现全排列

//Brute_Force_Full_Array();

//递归实现全排列

int i;

scanf("%d",&n);

//初始化数据

for(i = 1;i<=n;i++)

data[i] = i;

Recursion_Full_Array(1);//从第一个数据开始

return 0;

}