对组合排列问题的小结

(1)求组合排列数
问题一:
从n个不同数中取k个的组合数,排列数?
简单组合排列公式
问题二:
从n1个a1,n2个a2,n3个a3,……,nk个ak中(a1,a2……允许相等):
取k个数的组合方案数?(用母函数求解)
取k个的排列方案数?(指数型母函数)
(2)输出组合排列方案
问题三:
n个不同数取k个的全部组合?
可以使用dfs求解

//n个不同元素取k个进行组合
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
int queue[10000];
int iq=0;
int depth=0;
int k,n;
int a[10000];
void dfs(int cur,int pre)
{
	int i,j;
	depth++;
	if(depth==k+1)
	{
		for(i=0;i<=iq-1;i++)
			printf("%d ",queue[i]);
		printf("\n");
		return;
	}
	for(j=cur+1;j<=n-(k-depth);j++)
	{
	        queue[iq++]=a[j];
		dfs(j,cur);
		iq--;
		depth--;
	}
return;
}
int main()
{
	while(scanf("%d %d",&n,&k)!=EOF)
	{
		int i;
		iq=0;
		depth=0;
		for(i=1;i<=n;i++)
		{
			scanf("%d",&a[i]);
		}
		sort(a+1,a+1+n);
		dfs(0,-1);
	}



//system("pause");
return 0;
}

问题四:
n个不同数取k个的全部排列?
很简单,在上述程序中,当找到一种组合时,用next_permutation()求出该组合的全排列即可
问题五:
n个可重复地数取k个的全部组合?
依然是在上述程序基础上修改

//n个可重元素取k个进行组合
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
int queue[10000];
int iq=0;
int depth=0;
int k,n;
int a[10000];
void dfs(int cur,int pre)
{
	int i,j;
	depth++;
	if(depth==k+1)
	{
		for(i=0;i<=iq-1;i++)
			printf("%d ",queue[i]);
		printf("\n");
		return;
	}
	for(j=cur+1;j<=n-(k-depth);j++)
	{
		if(!(cur!=j-1 && a[j]==a[j-1]))//关键句,如果上一个选的数不是a[j-1],但现在要选的数a[j]和a[j-1]相等,则放弃选择a[j].
		{
			queue[iq++]=a[j];
			dfs(j,cur);
			iq--;
			depth--;
		}
	}
return;
}
int main()
{
	while(scanf("%d %d",&n,&k)!=EOF)
	{
		int i;
		iq=0;
		depth=0;
		for(i=1;i<=n;i++)
		{
			scanf("%d",&a[i]);
		}
		sort(a+1,a+1+n);
		dfs(0,-1);
	}



//system("pause");
return 0;
}

问题六:
n个可重复数取k个的全部排列?
同问题四。。