快速计算从n中任选m的所有组合
Posted in 设计
来源： http://lifesinger.org/blog/2009/09/javascript-quick-combine/
Posted on September 25th, 2009 in 前端开发 by lifesinger
/** |
* 快速组合算法 |
* 从 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, 性能立刻提升，在所有浏览器下保持优势。