学步园

#include <iostream>
using namespace std;

int count = 0;
#define MAX 4

void swap( char *a, char *b){
	char tmp;
	tmp = *a;
	*a = *b;
	*b = tmp;
}

/**
* （全排列:A(m,n)且m==n）
* 全排列是这样的：第一个位置有n种方法，第二个位置n-1种方法...
* 从第一个位置开始，循环将每一个后面的值都交换到第一个位置来，
* 每次放好第一个位置之后，递归求解接下来后面的序列的全排列。
* 每次递归用k来指明正在放的是哪个位置。
*
* 每次递归的时候，剩下的元素里面，每个元素都有机会放在第一个位置(交换)。
*/
void permutation(char a[], int n, int begin){
	if(begin == n){
		//递归结束，输出当前排列好的序列
		for(int i=0;i<n;i++)
			cout<<a[i];
		cout<<"  ";
		count++;
	}
	else{
		//注意从位置k开始
		for(int i=begin;i<n;i++){
			swap(&a[begin], &a[i]);
			permutation(a, n, begin+1);    //递归求解位置begin+1开始的全排列
			swap(&a[begin], &a[i]);        //还原
		}
	}
}

/**
* （可重复的全排列）
* 第一个位置有n中方法，第二个位置有n中方法，...第n个位置有n中方法
* 重新声明一个同样大小的数组来存放结果，每次递归用k来指明正在放的
* 是哪个位置。
*/
void permutation_2(char a[], char b[], int begin, int n){
    //n个位置全部放置完成，输出  
	if(begin == n){
		for(int i=0;i<n;i++)
			cout<<b[i];
		cout<<"("<<count<<") ";
		count++;
	}
	else{
		//在第k个位置尝试放置每一个a[i]
		for(int i=0;i<n;i++){
			b[begin] = a[i];
			permutation_2(a,b,begin+1,n); //递归处理第begin+1个位置
		}
	}
}

int number = 0;
void sub_set2(char a[], int n, char b[], int begin, int k){
	if(k == 0){
		//放置完成，输出
		for(int i=0;i<begin;i++)
			cout<<b[i];
		cout<<"("<<number++<< ")  ";
		return;
	}
	
	//在位置begin尝试每一个a[i]
	for(int i=0;i<n;i++){
		b[begin] = a[i];
		sub_set2(a, n, b, begin+1, k-1); //递归下一个位置
	}
}

/**
* {a,b,c,d}: 子排列，A(1,n),A(2,n)...A(n,n) 并且可重复
* 即a,b,c,d, aa,ab,ac,ad,ba,bb,bc,bd, aaa,aab ,aac,aad,aba, abb...
*/
void permutation_3(char a[]){
	char b[MAX];
	count = 0;
	for(int i=1;i<=MAX;i++)
		sub_set2(a, MAX, b, 0, i);
}


int main(){
	char a[MAX] = {'a' ,'b' ,'c' ,'d' };
	char b[MAX];
	
	cout<<"\n=== 全排列 ===" <<endl;
	permutation(a, MAX, 0);
	cout<<"count:" <<count<<endl;
	
	cout<<"\n=== 可重复的全排列 ===" <<endl;
	count = 0;
	permutation_2(a, b, 0, MAX);
	cout<<"count:" <<count<<endl ;
	
	cout<<"\n=== 子全排列 ===" <<endl;
	permutation_3(a);
	return 0;
}