您现在的位置:首页 --> JavaScript --> JavaScript 快速组合算法
JavaScript 快速组合算法
浏览:1733次 出处信息
/** * 快速组合算法 * 从 n 中任选 m(0 < m <= n) 个数的所有组合 */ function quick_combine(n, m) { var t = ((1 << n) - (1 << n - m)).toString(2), r = [], s, p1, p2; while((r.push(t), p1 = t.indexOf("10")) >= 0) { s = t.slice(0, p1); p2 = s.indexOf("1"); t = (p2 > 0 ? ((1 << p1) - (1 << p2)).toString(2) : s) + "01" + t.slice(p1 + 2); } return r; }
算法思路:
假设场景为从 [a, b, c, d, e] 里, 5 选 3.
先设定第一个和最后一个组合为:
s = 1 1 1 0 0 // a,b,c
e = 0 0 1 1 1 // c,d,e
Step1. 从左到右找出第 i 个组合中的 10, 转换为 01, 并将 01 左边的 1 全部移动到最左边,得到新组合 t
Step2. 如果 t 不为 e, 继续 Step1
按照以上思路,可以得到:
1 1 1 0 0
1 1 0 1 0
1 0 1 1 0
0 1 1 1 0
1 1 0 0 1
1 0 1 0 1
0 1 1 0 1
1 0 0 1 1
0 1 0 1 1
0 0 1 1 1
共 10 种组合
网上流传的递归方案(好像是月影写的?没找到源头):
/** * 递归组合算法 * 从 arr[1...n] 中任选 num(0 < num <= n) 个数的所有组合 */ function combine(arr, num) { var r = []; (function f(t, a, n) { if (n == 0) return r.push(t); for (var i = 0, l = a.length; i <= l - n; i++) { f(t.concat(a[i]), a.slice(i + 1), n - 1); } })([], arr, num); return r; }
两种方案的性能对比: combine-test.html
在 Firefox, Chrome, Safari 浏览器中,快速组合算法优势非常明显。
在 IE 浏览器中,计算量比较小时,快速组合算法依旧有优势;但计算量大时,无优势,甚至不如递归。
2009-09-27: 修改快速组合算法,用 Math 代替 regex replace, 性能立刻提升,在所有浏览器下保持优势。
51js 讨论贴:http://bbs.51js.com/viewthread.php?tid=85574
QQ技术交流群:445447336,欢迎加入!
扫一扫订阅我的微信号:IT技术博客大学习
扫一扫订阅我的微信号:IT技术博客大学习
<< 前一篇:JS代码优化的层次
后一篇:Loop Benchmarks >>
文章信息
- 作者:lifesinger 来源: 岁月如歌
- 标签: 快速组合
- 发布时间:2009-10-13 22:52:51
近3天十大热文
- [67] Go Reflect 性能
- [67] Oracle MTS模式下 进程地址与会话信
- [67] 如何拿下简短的域名
- [61] IOS安全–浅谈关于IOS加固的几种方法
- [60] 图书馆的世界纪录
- [59] android 开发入门
- [59] 【社会化设计】自我(self)部分――欢迎区
- [56] 视觉调整-设计师 vs. 逻辑
- [49] 给自己的字体课(一)——英文字体基础
- [47] 界面设计速成