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;
}

再帰を使って、下みたいに書いてもいいと思います！
想定通りの動作でしょうか？(ちゃんとテストしてないので自信ないです）

function sum(G) { return G.reduce(function (t, v) { return v + t }, 0);}
// 文字の組み合わせを列挙する ex, XX YYY ZZZ W から
// G: 使用可能な文字数 ex, [2, 3, 3, 1]
// N: 使う文字数　ex, 3
// return: ex, [[2,1,0,0],[2,0,1,0],...]
function select2(G, N) {
    if (N == 0) return [G.map(function (x) { return 0; })];
    var result = [];
    var new_G = G.slice(1);
    for (var i = Math.max(0,N - sum(new_G)); i < 1 + Math.min(G[0], N); i++) {
        result = result.concat(select2(new_G, N - i).map(function (x) { return [i].concat(x); }));
    }
    return result;
}

ベンチとったら若干遅いみたい。
console.time("select");
for (var i=0; i<100000; i++) select([1,2,3,4], 4)

console.timeEnd("select");

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

select: 2424ms
select2: 3285ms

多分concatの内部実装が遅いんだと思います....
select2のほうが、余計な計算省けるかと

おお、なるほど！
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
にほぼ対応してます。

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

面白い問題でした！