全排列生成算法

wikipedia上提供的一种方法

这个方法可以以字典序生成一组数的全排列。方法非常简便，在14世纪由Narayana Pandita发现。

1. Find the largest index k such that a[k] < a[k + 1]. If no such index exists, the permutation is the last permutation.

2. Find the largest index l greater than k such that a[k] < a[l].

3. Swap the value of a[k] with that of a[l].

4. Reverse the sequence from a[k + 1] up to and including the final element a[n].

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41

   #include<stdio.h> int n; int a[1010]; void swap(int* x,int* y){ *x^=*y^=*x^=*y; return; } int main(){ scanf("%d",&n); for(int i=0;i<n;i++){ a[i]=i+1; printf("%d ",a[i]); } printf("\n"); int k=0,l=0; for(;;){ k=-1,l=-1; for(int i=n-1-1;i>=0;i--){ if(a[i]<a[i+1]){ k=i; break; } } if(k==-1)break; for(int i=n-1;i>k;i--){ if(a[i]>a[k]){ l=i; break; } } swap(&a[k],&a[l]); for(int i=k+1;i<(k+1+n-1+1)/2;i++){ swap(&a[i],&a[k+1+n-1-i]); } for(int i=0;i<n;i++){ printf("%d ",a[i]); } printf("\n"); } return 0; }

   然后是常规的递归生成方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include<stdio.h>
int n;
int flag,a[100];
void dfs(int t){
	if(t==n+1){
		for(int i=1;i<=n;i++)printf("%d ",a[i]);
		printf("\n");
		return ;
	}
	for(int i=1;i<=n;i++){
		if(!(flag&(1<<i))){
			a[t]=i;
			flag|=1<<i;
			dfs(t+1);
			flag^=1<<i;			
		}
	}
	return ;
}
int main(){
	scanf("%d",&n);
	dfs(1);
	return 0; 
}