字典序组合.txt

来自「acm常用模板」· 文本 代码 · 共 22 行

//字典序组合与序号的转换
//comb为组合数C(n,m),必要时换成大数,注意处理C(n,m)=0|n<m
int comb(int n,int m){
	int ret=1,i;
	m=m<(n-m)?m:(n-m);
	for (i=n-m+1;i<=n;ret*=(i++));
	for (i=1;i<=m;ret/=(i++));
	return m<0?0:ret;
}

int comb2num(int n,int m,int *c){
	int ret=comb(n,m),i;
	for (i=0;i<m;i++)
		ret-=comb(n-c[i],m-i);
	return ret;
}

void num2comb(int n,int m,int* c,int t){
	int i,j=1,k;
	for (i=0;i<m;c[i++]=j++)
		for (;t>(k=comb(n-j,m-i-1));t-=k,j++);
}