[已解决]如何列出m个不同值的组合数

吕?布 · 发表于 2009-11-19 08:21

本帖最后由爱疯于 2011-10-14 20:34 编辑

如题，用什么算法列出从m个值(值各不相同)里取n(0<n<=m)个值的组合呢。

经测试，代码运行正确的30BB，本贴评一个最佳

送BB贴到时另开

[hide]

我现在想到的是

for i=1 to 2^m

sTmp=i转换成2进制字串

按sTmp的各位的值决定是否取m里相应数值

next i

[/hide ]

最佳答案

amulee

2009-11-19 12:34

本帖最后由爱疯于 2012-11-4 18:05 编辑

更新一种非递归算法[hide]

JdvZoRph.rar (12.9 KB, 下载次数: 380)

零点★沉思 · 发表于 2009-11-19 09:06

我的思路是定义个数组arr(1 to m , 1 to 2),其中arr(i,1)用于存储数组的数，arr(i,2)用来标记数组是否被选中（选中为1，否则为0）

初始化的时候将arr(i,2),i=1,2,……n，标记为1，作为第一组组合，再遍历数组标记arr(i,2),i=1,2,……m-1，找出满足条件arr(1,2)=1 and arr(i,2)=1 and arr(i+1,2)=0时，就重新赋值arr(i+1,2)=1,arr(i,2)=0

如果遍历数组标记arr(i,2),i=1,2,……m-1，出现如下条件arr(1,2)=0 and arr(i,2)=1 and arr(i+1,2)=0时，重新赋值arr(i+1,2)=1,arr(i,2)=0，并且arr(k,2),k=1,2,……i-2，arr(k,2)=arr(k+1,2)

最后当再遍历数组arr(i,2),i=1,2,……m，如果arr(i,2)=0(i=1,2,……m-n)时，即相当于arr(i,2)=1(i= m-n+1,……m)，就相当于完成了所有的组合，得到最后一个组合了

表达的不是很好，不知道大家能不能看懂，请见谅！

amulee · 发表于 2009-11-19 09:07

本帖最后由爱疯于 2011-10-15 19:10 编辑

给你一个递归算法

[hide]

XrE4PUec.rar (8.36 KB, 下载次数: 176)

amulee · 发表于 2009-11-19 12:34

本帖最后由爱疯于 2012-11-4 18:05 编辑

更新一种非递归算法[hide]

JdvZoRph.rar (12.9 KB, 下载次数: 380)

顾征 · 发表于 2011-4-21 15:02

程序看了哈，从这个程序可以了解下递归哈，感谢提供程序的哈，所谓递归就是自己循环自己，但是要有个能够结束的条件哈，第二个算法相对来说更好理解，但是算法的思路不知道怎么来的，就是01换位，挺新颖的哈

阿童木 · 发表于 2011-4-21 15:22

算法是前人总结的，怎么来的我也不清楚。反正数学方法应该能证明。

		自动登录	找回密码
密码			注册