在實(shí)驗(yàn)室閑的無聊，隨意寫了個(gè)全排列和組合數(shù)的函數(shù)模板，就當(dāng)娛樂一下。這2個(gè)函數(shù)本身實(shí)現(xiàn)很簡單，唯一要注意的就是都用到了“回溯”的技巧。
全排列n!:
1 #include <iostream>
2 using namespace std;
3
4 void Perm(int k,int n,int a[]){
5 if(k==n){
6 for(int i=0;i<n;i++)
7 cout<<a[i]<<' ';
8 cout<<endl;
9 return;
10 }
11 for(int i=k;i<n;i++){
12 swap(a[k],a[i]);
13 Perm(k+1,n,a);
14 swap(a[i],a[k]); //回溯
15 }
16 }
17 int main(){
18 int i,n,a[10];
19 while(cin>>n,n){
20 for(i=0;i<n;i++) a[i]=i+1;
21 Perm(0,n,a);
22 }
23 return 0;
24 }
組合數(shù)C(n,k):
1 #include <iostream>
2 using namespace std;
3
4 bool visited[10];
5 void dfs(int pos,int cnt,int n,int k,int a[]){
6 if(cnt==k){
7 for(int i=0;i<n;i++)
8 if(visited[i]) cout<<a[i]<<' ';
9 cout<<endl;
10 return;
11 }
12 if(pos==n) return;
13 if(!visited[pos]){
14 visited[pos]=true;
15 dfs(pos+1,cnt+1,n,k,a);
16 visited[pos]=false; //回溯
17 }
18 dfs(pos+1,cnt,n,k,a);
19 }
20 int main(){
21 int i,n,k,a[10];
22 while(cin>>n>>k,n||k){
23 for(i=0;i<n;i++) a[i]=i+1;
24 dfs(0,0,n,k,a);
25 }
26 return 0;
27 }