显然,对于具有n个元素的集合R,R={r1,r2,r3…rn},其排列方式有n!种。 如:R = {1,2,3},其全排列如下: 1,2,3 1,3,2 2,1,3 2,3,1 3,1,2 3,2,1
从上边的排列中可以看出规律,以集合中某一元素作为第一个数字,集合当中的其余数字做全排列。而其余数字组成的集合可以看作是子集合,子集合中的第一个元素作为第一个数字,子集合当中的其余数字做全排列。可以看出,这是一个递归过程。有了上面的思想,可以容易的写出一个递归算法解决全排列的问题。 代码实现:
#include<cstdio>
//交换数组的i项和j项
void swap(int A[],int i,int j){
int temp = A[i];
A[i] = A[j];
A[j] = temp;
}
void show(int A[],int n){
for(int i=0;i < n;++i){
printf("%d ",A[i]);
}
printf("\n");
}
//对数组做排列,p,q之间做全排列
void permutation(int A[],int p,int q){
//递归出口,只有一个元素时。全排列就是其本身
if(p == q){
show(A,q+1);//数组是从0下标开始的
}
for(int i=p;i <= q;++i){
swap(A,p,i);
perm(A,p+1,q);//子集合做全排列
swap(A,p,i);//恢复,否则会有重复
}
}
test1.c
int main(){
int arr[] = {1,2,3};
permutation(arr,0,2);
return 0;
}
test2.c