学步园

排列组合，具体问题描述：http://acm.hdu.edu.cn/showproblem.php?pid=1521

此类问题用到指数型母函数：http://wenku.baidu.com/view/f302ccefe009581b6bd9eb4e.html

注意区别排列与组合以及全排列与部分排列（从n个数字中选m个的全排列）；

#include <iostream>
#include <iomanip>
using namespace std;
const int MAX = 11;
double fac[MAX],ans[MAX],tmp[MAX];
void InitFac()
{
	fac[0] = 1;
	for(int i=1;i<MAX;++i)
		fac[i] = fac[i-1]*i;
}
int main()
{
	InitFac();//计算阶乘
	int n,m,i,j,k;
	int Num[MAX];
	while(cin>>n>>m)
	{
		memset(Num,0,sizeof(Num));
		for(i=0;i<n;++i) cin>>Num[i];
		memset(ans,0,sizeof(ans));
		memset(tmp,0,sizeof(tmp));
		for(i=0;i<=Num[0];++i)//第一种物品选
			ans[i] = 1.0/fac[i];
		for(i=1;i<n;++i)//其余种类的物品
		{
			for(j=0;j<MAX;++j) //x的j次方
				for(k=0;(k<=Num[i])&&(k+j<MAX);++k)//x的k次方
					tmp[j+k] += ans[j]/fac[k];
			for(j=0;j<MAX;++j)
			{ans[j] = tmp[j];tmp[j]=0;}
		}
		cout<<fixed<<setprecision(0)<<(ans[m]*fac[m])<<endl;
	}
	return 0;
}

全排列的实现：

#include<fstream> 
using namespace std;

int count = 0;
ifstream fin("input.txt");
ofstream fout("output.txt");

void swap(char &a, char &b) {
	char temp;
	temp = a;
	a = b;
	b = temp;
}

void perm(char c[], int start, int end) {
	if(start==end) ｛
		for( int i=0; i<=end; i++)
			fout<<c[i];
		fout<<endl;
		count++;
	}else {
		for(int i=start; i<=end; i++) {
			int flag=0;
			for(int j=start; j < i; j ++) {
				if(c[j] == c[i]) {
					flag=1;
					break;
				}
			}
			if(1==flag) 
				continue;
			swap(c[start], c[i]);
			perm(c, start+1, end);
			swap(c[start], c[i]);
		}
	}
}

int main()
{
	int n;
	fin>>n;
	char c[16];
	if(1 <= n && n <= 15) {
		for( int i = 0; i < n; i ++) {
			fin>>c[i];
		}
	}
	perm(c, 0, n - 1);
	fout<<count<<endl;
	
	system("pause");
	return 0;
}