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

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

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


Author: kingwei @ ECUST

Date: 2005.8.15

E-mail: jx_kingwei@sina.com



1 排列问题

1.1 类循环排列



输入样例

3 2



输出样例

0 0 0

0 0 1

0 1 0

0 1 1

1 0 0

1 0 1

1 1 0

1 1 1



代码

#include <stdio.h>

#define MAX_N 10



int n, m; //相当于n重循环,每重循环长度为m

int rcd[MAX_N]; //记录每个位置填的数



void loop_permutation(int l)

{

int i;

if (l == n) //相当于进入了n重循环的最内层

{

for (i=0; i<n; i++)

{

printf("%d", rcd[i]);

if (i < n-1)

printf(" ");

}

printf("\n");

return;

}

for (i=0; i<m; i++) //每重循环长度为m

{

rcd[l] = i; //在l位置放i

loop_permutation(l+1); //填下一个位置

}

}



int main()

{

while (scanf("%d%d", &n, &m) != EOF)

loop_permutation(0);

return 0;

}



实际上,这样的方法是用递归实现多重循环,本递归程序相当于n重循环,每重循环的长度为m的情况,所以输出共有m^n行。



1.2 全排列

对输入的n个数作全排列。



输入样例

3

1 2 3



输出样例

1 2 3

1 3 2

2 1 3

2 3 1

3 1 2

3 2 1



代码

#include <stdio.h>

#define MAX_N 10



int n; //共n个数

int rcd[MAX_N]; //记录每个位置填的数

int used[MAX_N]; //标记数是否用过

int num[MAX_N]; //存放输入的n个数



void full_permutation(int l)

{

int i;

if (l == n)

{

for (i=0; i<n; i++)

{

printf("%d", rcd[i]);

if (i < n-1)

printf(" ");

}

printf("\n");

return;

}

for (i=0; i<n; i++) //枚举所有的数(n个),循环从0开始

if (!used[i]) //若num[i]没有使用过,则

{

used[i] = 1; //标记为已使用

rcd[l] = num[i]; //在l位置放上该数

full_permutation(l+1); //填下一个位置

used[i] = 0; //清标记

}

}



int read_data()

{

int i;

if (scanf("%d", &n) == EOF)

return 0;

for (i=0; i<n; i++)

scanf("%d", &num[i]);

for (i=0; i<n; i++)

used[i] = 0;

return 1;

}



int main()

{

while (read_data())

full_permutation(0);

return 0;

}

程序通过used数组,标记数是否被用过,可以产生全排列,共有n!种。

但是,通过观察就会发现,若输入的n个数有重复,那么在输出的n!种排列中,必然存在重复的项,若不允许输出重复的项,该怎么做呢?



1.3 不重复排列

输入n个数,输出由这n个数构成的排列,不允许出现重复的项。



输入样例

3

1 1 2



输出样例

1 1 2

1 2 1

2 1 1



代码

#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_permutation(int l)

{

int i;

if (l == n) //填完了n个数,则输出

{

for (i=0; i<n; i++)

{

printf("%d", rcd[i]);

if (i < n-1)

printf(" ");

}

printf("\n");

return;

}

for (i=0; i<m; i++) //枚举m个本质不同的数

if (used[i] > 0) //若数num[i]还没被用完,则

{

used[i]--; //可使用次数减1

rcd[l] = num[i]; //在l位置放上该数

unrepeat_permutation(l+1); //填下一个位置

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_permutation(0);

return 0;

}

本程序将全排列中的used标记数组,改为记录输入中,每个本质不同的数出现的次数,并在递归函数中使用。需要注意的是,在输入过程中,应剔除重复的数值。

实际上,重复排列的产生是由于同一个位置被多次填入了相同的数,并且这多次填入又是在同一次循环过程中完成的。本方法通过统计每个本质不同的数的个数,使得循环长度由n变为m,这样,i一旦自增,就再也不会指向原先填入过的数了。

这种方法剪去了重复项的生成,从而加快了搜索速度,是深度优先搜索中常用的剪枝技巧。
c语言热门文章排行
网站赞助商
购买此位置

 

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

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