|
来源:www.cncfan.com | 2006-4-28 | (有9668人读过)
Author: kingwei @ ECUST
Date： 2005.8.15
E-mail: jx_kingwei@sina.com
2 组合问题
2.1 一般组合
输入n个数，从中选出m个数可构成集合，输出所有这样的集合。
输入样例
4 3
1 2 3 4
输出样例
1 2 3
1 2 4
1 3 4
2 3 4
代码
#include <stdio.h>
#define MAX_N 10
int n, m; //从n个数中选出m个构成组合
int rcd[MAX_N]; //记录每个位置填的数
int num[MAX_N]; //存放输入的n个数
void select_combination(int l, int p)
{
int i;
if (l == m) //若选出了m个数，则打印
{
for (i=0; i<m; i++)
{
printf("%d", rcd[i]);
if (i < m-1)
printf(" ");
}
printf("\n");
return;
}
for (i=p; i<=n-(m-l); i++) //上个位置填的是num[p-1]，本次从num[p]开始试探
{
rcd[l] = num[i]; //在l位置放上该数
select_combination(l+1, i+1); //填下一个位置
}
}
int read_data()
{
int i;
if (scanf("%d%d", &n, &m) == EOF)
return 0;
for (i=0; i<n; i++)
scanf("%d", &num[i]);
return 1;
}
int main()
{
while (read_data())
select_combination(0, 0);
return 0;
}
因为在组合生成过程中引入了变量p，保证了每次填入的数字在num中的下标是递增的，所以不需要使用used进行标记，共C(n, m)种组合。另外，循环终止条件变为i>n-(m-l)，减去了不必要的分枝。
2.2 全组合
输入n个数，求这n个数构成的集合的所有子集。
输入样例
3
1 2 3
输出样例
1
1 2
1 2 3
1 3
2
2 3
3
代码
#include <stdio.h>
#define MAX_N 10
int n; //共n个数
int rcd[MAX_N]; //记录每个位置填的数
int num[MAX_N]; //存放输入的n个数
void full_combination(int l, int p)
{
int i;
for (i=0; i<l; i++) //每次进入递归函数都输出
{
printf("%d", rcd[i]);
if (i < l-1)
printf(" ");
}
printf("\n");
for (i=p; i<n; i++) //循环同样从p开始，但结束条件变为i>=n
{
rcd[l] = num[i]; //在l位置放上该数
full_combination(l+1, i+1); //填下一个位置
}
}
int read_data()
{
int i;
if (scanf("%d", &n) == EOF)
return 0;
for (i=0; i<n; i++)
scanf("%d", &num[i]);
return 1;
}
int main()
{
while (read_data())
full_combination(0, 0);
return 0;
}
全组合，共2^n种，包含空集和自身。与全排列一样，若输入的n个数有重复，那么在输出的2^n种组合中，必然存在重复的项。避免重复的方法与不重复排列算法中使用的类似。
2.3 不重复组合
输入n个数，求这n个数构成的集合的所有子集，不允许输出重复的项。
输入样例
3
1 1 3
输出样例
1
1 1
1 1 3
1 3
3
代码
#include <stdio.h>
#define MAX_N 10
int n, m; //输入n个数，其中本质不同的有m个
int rcd[MAX_N]; //记录每个位置填的数
int used[MAX_N]; //标记m个数可以使用的次数
int num[MAX_N]; //存放输入中本质不同的m个数
void unrepeat_combination(int l, int p)
{
int i;
for (i=0; i<l; i++) //每次都输出
{
printf("%d", rcd[i]);
if (i < l-1)
printf(" ");
}
printf("\n");
for (i=p; i<m; i++) //循环依旧从p开始，枚举剩下的本质不同的数
if (used[i] > 0) //若还可以用，则
{
used[i]--; //可用次数减1
rcd[l] = num[i]; //在l位置放上该数
unrepeat_combination(l+1, i); //填下一个位置
used[i]++; //可用次数恢复
}
}
int read_data()
{
int i, j, val;
if (scanf("%d", &n) == EOF)
return 0;
m = 0;
for (i=0; i<n; i++)
{
scanf("%d", &val);
for (j=0; j<m; j++)
if (num[j] == val)
{
used[j]++;
break;
}
if (j == m)
{
num[m] = val;
used[m] = 1;
m++;
}
}
return 1;
}
int main()
{
while (read_data())
unrepeat_combination(0, 0);
return 0;
}
需要注意的是递归调用时，第二个参数是i，不再是全组合中的i+1了，想想为什么？
3 应用
搜索问题中有很多本质上就是排列组合问题，只不过加上了某些剪枝和限制条件。
解这类题目的基本算法框架常常是类循环排列、全排列、一般组合或全组合。
而不重复排列与不重复组合则是两种非常有效的剪枝技巧。
TOJ 1032 等式问题
类循环排列问题
TOJ 1002 全排序问题
全排列问题
TOJ 1017 石子归并
全组合问题
ZOJ 1002 Fire Net
每个位置可以取放或者不放，因此能够化为全组合问题，也可以化为类循环排列问题
POJ 1256 Anagram
不重复排列问题
ZOJ 1711 Sum It Up
不重复组合问题
ZOJ 1694 Shredding Company
每个间隔位置可以选择切或者不切
ZOJ 1457 Prime Ring Problem
全排列问题，注意n为奇数时无解
ZOJ 1204 Additive equations
全组合问题，注意剪枝
ZOJ 2192 T-shirt Gumbo
类似于全排列问题，循环控制有所不同，搜索前应先排序，以加快搜索速度。
ZOJ 1909 Square
全组合问题，只是需要做三次。使用不重复组合剪枝技巧和有序化，可以达到很好的效果。
|
