an algorithm for selecting a certain number of elements from groups (combination)

select.js

// WW XXXX YYY ZZ -> get four characters (e.g. WXXZ)
// var G = [2, 4, 3, 2] // each stands for the number of W, X, Y, Z
// select(G, 4); // get all possible combinations
//   [  [2,2,0,0],  [2,1,1,0], [2,1,0,1] ... ] // each stands for the number of selected W, X, Y, Z

function sum(G) {
  return G.reduce(function(t,v){return v+t},0);
}
function copy(a) {
  return a.slice();
}

function select(G, N) {
  var Lg = G.length; // length of Groups
  var T = G.reduce(function(total, v) { return total * (v+1) }, 1); // number of cases
  var s = G.map(function() {return 0}); // possible selection (default: [0,0,0,...])
  var S = []; // set of valid selections
  var i,j,k;  // cursor

  for (i=0; i<T; i++) {
    if (sum(s) == N) S.push(s);
    s = copy(s);
    for (j=0; j<Lg; j++) {
      if (s[j] < G[j]) {
        s[j]++;
        for (k=0;k<j;k++) {
          s[k] = 0;
        }
        break;
      }
    }
  }
  return S;
}

おお、なるほど！
concatの内部実装はわかりませんが...(どこみればいいんだろう)

多分、関数呼び出しのコストが高いので、ナイーブに全てさらっているselectの方が早くなっているのだと思います。

例えば

console.time("select");
for (var i=0; i<10000; i++) select([1,2,3,4], 4)
console.timeEnd("select");

console.time("select");
for (var i=0; i<10000; i++) select([10,2,3,4], 4)
console.timeEnd("select");

console.time("select2");
for (var i=0; i<10000; i++) select2([1,2,3,4], 4)
console.timeEnd("select2");

console.time("select2");
for (var i=0; i<10000; i++) select2([10,2,3,4], 4)
console.timeEnd("select2");

だと、
select: 714.000ms
select: 3693.000ms
select2: 816.000ms
select2: 1232.000ms
という結果でした。(on Surface Pro)

select([1,2,3,4], 4).length -> 20
select([10,2,3,4], 4).length -> 30
にほぼ対応してます。

というわけで、問題セットによってアルゴリズム使い分けるのがよいと思います！笑

面白い問題でした！