电脑爱好者,提供IT资讯信息及各类编程知识文章介绍,欢迎大家来本站学习电脑知识。 最近更新 | 联系我们 RSS订阅本站最新文章
电脑爱好者
站内搜索: 
当前位置:首页>> c语言>>递归方法求解排列组合问题(2):

递归方法求解排列组合问题(2)

来源:www.cncfan.com | 2006-4-28 | (有9045人读过)

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

全组合问题,只是需要做三次。使用不重复组合剪枝技巧和有序化,可以达到很好的效果。
c语言热门文章排行
网站赞助商
购买此位置

 

关于我们 | 网站地图 | 文档一览 | 友情链接| 联系我们

Copyright © 2003-2022 电脑爱好者 版权所有 备案号:鲁ICP备09059398号