文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 人文社科 > 哲学/历史 > 排列组合问题通用算法
侵权投诉

排列组合问题通用算法

排列组合问题通用算法

排列组合问题通用算法

2009-10-15 20:31尽管排列组合是生活中经常遇到的问题,可在程序设计时,不深入思考或者经验不足都让人无从下手。由于排列组合问题总是先取组合再排列,并且单纯的排列问题相对简单,所以本文仅对组合问题的实现进行详细讨论。以在n个数中选取m(0<m<=n)个数为例,问题可分解为:

1. 首先从n个数中选取编号最大的数,然后在剩下的n-1个数里面选取m-1个数,直到从n-(m-1)个数中选取1个数为止。

2. 从n个数中选取编号次小的一个数,继续执行1步,直到当前可选编号最大的数为m。 很明显,上述方法是一个递归的过程,也就是说用递归的方法可以很干净利索地求得所有组合。

下面是递归方法的实现:

/// 求从数组a[1..n]中任选m个元素的所有组合。

/// a[1..n]表示候选集,n为候选集大小,n>=m>0。

/// b[1..M]用来存储当前组合中的元素(这里存储的是元素下标),

/// 常量M表示满足条件的一个组合中元素的个数,M=m,这两个参数仅用来输出结果。 void combine( int a[], int n, int m, int b[], const int M )

{

for(int i=n; i>=m; i--) // 注意这里的循环范围

{

b[m-1] = i - 1;

if (m > 1)

combine(a,i-1,m-1,b,M);

else // m == 1, 输出一个组合

{

for(int j=M-1; j>=0; j--)

cout << a[b[j]] << " ";

cout << endl;

}

}

}

因为递归程序均可以通过引入栈,用回溯转化为相应的非递归程序,所以组合问题又可以用回溯的方法来解决。为了便于理解,我们可以把组合问题化归为图的路径遍历问题,在n个数中选取m个数的所有组合,相当于在一个这样的图中(下面以从1,2,3,4中任选3个数为例说明)求从[1,1]位置出发到达[m,x](m<=x<=n)位置的所有路径:

1 2 3 4

2 3 4

3 4

上图是截取n×n右上对角矩阵的前m行构成,如果把矩矩中的每个元素看作图中的一个节点,我们要求的所有组合就相当于从第一行的第一列元素[1,1]出发,到第三行的任意一列元素作为结束的所有路径,规定只有相邻行之间的节点,并且下一行的节点必须处于上一行节点右面才有路径相连,其他情况都无路径相通。显然,任一路径经过的数字序列就对应一个符合要求的组合。

下面是非递归的回溯方法的实现:

第1页

你可能喜欢

  • 高中数学排列组合问题
  • 高中排列组合公式
  • 高考数学难点突破
  • 排列组合知识点总结
  • JAVA编程题全集及答案
  • 组合数学论文

热门文档

相关文档

  • 解决排列组合问题的通用算法

    如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 解决排列组合问题的通用算法 有用就下啊,多多支持。有用就下啊,多多...

  • 排列组合问题经典题型与通用方法

    排列组合问题经典题型与通用方法_理学_高等教育_教育专区。排列组合问题经典题型与通用方法 解析版 1.相邻问题捆绑法 相邻问题捆绑法: 1.相邻问题捆绑法:题目中...

  • 排列组合问题经典题型与通用方法

    涉县第一中学高二数学 I 级部 选修 2-3 第一章计数原理 组题人:张利梅 排列组合问题经典题型与通用方法 1.相邻问题捆绑法:题目中规定相邻的几个元素捆绑成一...

  • 【论文】有关排列组合问题的一个算法

    有关排列组合问题的一个算法_专业资料 暂无评价

  • 组合数学之排列组合生成算法

    数学排列组合问题种方法 6页 免费喜欢此文档的还喜欢 排列组合问题通用算法 4...《组合数学》 组合数学》第二讲 排列组合生成算法 1 第二讲: 第二讲: 排列...

  • (教师版)排列组合问题经典题型与通用方法

    (教师版)排列组合问题经典题型与通用方法_高三数学_数学_高中教育_教育专区。排列组合问题经典题型与通用方法 (教师版) 1.相邻问题捆绑法:题目中规定相邻的几个...

  • 排列组合公式排列组合计算公式

    2.理解排列、组合的意义,掌握排列数、组合数的计算公式和组合数的性质, 并能用它们解决一些简单的问题. 3.掌握二项式定理和二项式系数的性质, 并能用它们计算和...

  • Java实现通用组合算法

    www.bj-accp.com Java 实现通用组合算法想索取更多相关资料请加 qq:649085085 或登录 http://www.bj-accp.com PS;本文档由北大青鸟广安门收集自互联网,仅作...

  • 排列组合和排列组合计算公式

    排列组合公式/排列组合计算公式排列 P---和顺序有关 组合 C ---不牵涉到顺序的问题 排列分顺序,组合不分 例如 把 5 本不同的书分给 3 个人,有几种分法....

  • 排列组合和排列组合计算公式

    2.理解排列、组合的意义,掌握排列数、组合数的计算公式和 组合数的性质,并能用它们解决一些简单的问题. 3.掌握二项式定理和二项式系数的性质,并能用它们计算和论...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email