Javascript 组合算法

[cc lang="javascript"]
/**
* 递归排列
* 从 arr[1...n] 中任选 num(0 < num <= n) 个数的所有排列
*/
function recursion_permutate(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; i++) {
f(t.concat(a[i]), a.slice(0, i).concat(a.slice(i + 1)), n - 1);
}
})([], arr, num);
return r;
}

/**
* 递归组合
* 从 arr[1...n] 中任选 num(0 < num <= n) 个数的所有组合
*/
function recursion_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;
}

/**
* 快速组合 - 字符串
*/
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;
}

/**
* 快速组合 - 纯位移
*/
function bit_quick_combine(n, m) {
var t = (1 << n + 1) - (1 << n - m), // 故意多留一个 1，免得补零
r = [], o, p1, p2;

while((o = t.toString(2).slice(1), r.push(o), p1 = o.indexOf("1"), p2 = o.indexOf("10")) >= 0){
t ^= ((p1 ? ((1 << p2) - (1 << p1) ^ (1 << p2 - p1) - 1) << 2 : 0) | 3) << n - p2 - 2;
}

return r;

}

/**
* 进位法
*/
function carry_combine(n, m) {
var r = [], t = [], i, p, max;

// seed
for(i = 0; i < m; i++) t.push(i);
r.push(t.concat());

while(p = m - 1, max = n - 1) {
// increase
while(t[p] < max) {
t[p]++;
r.push(t.concat());
}

// carry
while(t[--p] === --max){}
t[p]++;
for(i = p + 1; i < m; i++) t[i] = t[p] + i - p;
r.push(t.concat());

// done
if(t[0] === n - m) break;
}

return r;
}

/**
* 沙漏法
*/
function sandglass_combine(n, m) {
var p = [], r = [] , i, j;

for(i = m - 1, j = 0; i >= 0; i--, j++) {
p[j] = n - i - 1;
}

r.push(p.concat());
//5,4,3 5,4,2 5,4,1 5,4,0->5,3,2 5,3,1 5,3,0->5,2,1 5,2,0->5,1,0->5,0,0->4,3,2...

while (p[m - 1] >= m) {
if (--p[0] >= 0) {
r.push(p.concat());
}
else {
for (i = 1; i < m; i++) {
if (p[i] > i) {
p[i]--;
for (j = i - 1; j >= 0; j--) {
p[j] = p[j + 1] - 1;
}

r.push(p.concat());
break;
}
}
}
}
return r;
}

/**
* DP 组合
* @ref: http://bbs.51js.com/viewthread.php?tid=85574
* C(n, m) = C(n - 1, m) + C(n - 1, m - 1)
*/
function dp_combine(a, m) {
var t = [[]], r = [];

for (var i = 0, n = a.length; i < n; ++i) {
for (var j = 0, l = t.length; j < l; ++j) {
(t[j].length < m - 1 ? t : r).push(t[j].concat([a[i]]));
}
}
return r;
}
[/cc]