编程珠玑-01互换法解决m选n组合问题

dangerace · 发表于 2020-11-5 17:04:35

本帖最后由 dangerace 于 2020-11-5 23:10 编辑

目前论坛上能找到的解决m选n组合问题，基本都采用的递归算法。众所周知递归算法存在一定的局限性，性能也并不出色，所以就有了一些其他算法的出现。

我这个算法是仿照《编程珠玑》中第二章中，编程解决组合问题里的一个思路，就是01交换法来求组合数。

使用0或1表示集合中的元素是否出现在选出的集合中，因此一个0/1列表即可表示选出哪些元素。例如：[1 2 3 4 5]，选出的元素是[1 2 3]那么列表就是[1 1 1 0 0]。

使用01交换法的思路是，首先用一个数组用于记录集合中某元素是否被选中。因为需要在m个元素中选择n个，所以这个数组中总共有n个为1的元素，其他均为0。因此在初始化过程中，将该数组前n个元素赋值为1，其余m-n个元素赋值为0。然后从左到右扫描数组元素值的“10”组合，找到第一个“10”组合后将其变为“01”组合，同时将其左边的所有“1”全部移动到数组的最左端。当第一个“1”移动到数组的m-n+1的位置，即n个“1”全部移动到最右端时，就得到了最后一个组合。

代码写的比较烂，里面变量命名也不规范，运行效率一般，我感觉还有提升空间，但是意思到了，也尽量写了很详细的注释，希望各位大佬批评指正。

这个算法相比递归算法的最大好处是，对大数据的运算能力比较强。用递归算法，当数据量很大，递归层数太多时，就容易出现堆栈溢出的情况，而这个算法面对大量数据，虽然可能会慢，但稳定性好，只要等，就会一直算。

编程珠玑-01互换法-m选n组合算法.e (6.31 KB, 下载次数: 78)

cqcc · 发表于 2022-4-22 16:54:54

支持开源

ghost12 · 发表于 2022-2-4 00:01:00

感谢发布原创作品，精易因你更精彩！

云韵 · 发表于 2020-11-9 21:32:28

感谢发布原创作品，精易因你更精彩！

oursn · 发表于 2020-11-8 23:39:49

支持开源~！感谢分享

wxj213 · 发表于 2020-11-8 14:18:56

感谢分享了~~~~~~~~~~~~~

罗泠雨人 · 发表于 2020-11-5 22:50:35

感谢分享了~~~~~~~~~~~~~

dangerace · 发表于 2020-11-5 20:05:11

Maxximal 发表于 2020-11-5 19:58
求字体！！！

我这字体真的很特别？我明天到单位电脑上看一看，我记得就是普通的宋体啊

Maxximal · 发表于 2020-11-5 19:58:46

求字体！！！

dangerace · 发表于 2020-11-5 19:35:36

呆阿狸发表于 2020-11-5 17:37
这个字体不错哦，能否分享下

没有特殊字体，就是windows自带的宋体吧

hehehero · 发表于 2020-11-5 18:20:23

感谢发布原创作品，精易因你更精彩！

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

[2020开源大赛(第五届)] 编程珠玑-01互换法解决m选n组合问题

点评

评分

本帖被以下淘专辑推荐: