Posted at

組み合わせの順列の列挙


1. 概要

「ポーカにおける ツーペアを強い順に並べよ」のような問題を考える。

ツーペアを決めるのは C(13, 2) 通りあり、キッカー(残りの一枚) を決めるのに C(11, 1)通りあるので全部で C(13,2)*C(11, 1)=858通りある。組み合わせをひとまとまりと考えると組み合わせの順列であると見なせる。これらを列挙したい。


2. 具体例で計算

冒頭の例なら特に何も考えずに実装できる。まずはカードの数字に 0..12 の整数値を割り振る。人間の目に見やすいように以下のような表示関数を定義:

function repr (n) {

switch (n) {
case 12: return 'A';
case 11: return 'K';
case 10: return 'Q';
case 9: return 'J';
case 8: return 'T';
default: return (n + 2).toString();
}
}

ツーペアを i, jとし キッカーを k という変数名で表すと以下のような三重ループを使うと列挙できる:


main.js

for (let i = 12; i >= 0; i--) {

for (let j = i - 1; j >= 0; j--) {
for (let k = 12; k >= 0; k--) {
if (k === i || k === j) continue;
const [I, J, K] = [i, j, k].map(repr);
console.log(`${I} ${I} ${J} ${J} ${K}`);
}
}
}

すると全 858 通りが以下のように出力される

A A K K Q

A A K K J
A A K K T
...
3 3 2 2 6
3 3 2 2 5
3 3 2 2 4


3. 一般化

これまでの事を一般化しよう。まず解きたい課題だが


  • 昇順

  • (実体でなく)インデックスの組み合わせを列挙

としても一般性を失わない。


3-1. 組み合わせの列挙

一度にやるのは大変なので、組み合わせ ${}_n{\rm C}_k$ の列挙から。具体例から考察すると、k重ループが必要だけど、プログラムに落とし込むのはやりにくい(ソースコードに fork回書くのはどうする?)。よって再帰を使う。つまり:


  • 一つを選択する。それを i 番目とする

  • 残り k - 1 個を、 入力の i + 1番目以降から選ぶという問題にする

ということを再帰的に行えばよいことがわかる。


enumerate_k_combination.js

function ekc (n, k) {

if (k === 0) return [[]];
const result = [];
for (let i = 0; i < n; i++) {
if (n - i - 1 < k - 1) continue;
ekc(n - i - 1, k - 1).forEach(js => {
result.push([i, ...js.map(j => j + i + 1)]); // add offset
});
}
return result;
}

例えば ekc(5, 2) は以下のような出力になる

[ [ 0, 1 ], [ 0, 2 ], [ 0, 3 ], [ 0, 4 ], [ 1, 2 ],

[ 1, 3 ], [ 1, 4 ], [ 2, 3 ],[ 2, 4 ], [ 3, 4 ]]


3-2. 組み合わせの順列の列挙

道具が揃ったので、組み合わせの順列の列挙を実装しよう。

まず外部仕様だが、関数名を epc として第一引数に要素数 n と 組み合わせのk数の配列を渡すことにしよう。つまり、ツーペアの列挙では epc(13, [2, 1]) だし、スリーカードの列挙では epc(13, [1, 2])となる。具体的な出力がこうなるようにしたい:

epc(5, [2, 2, 1]);

[ [ 0, 1 ], [ 2, 3 ], [ 4 ] ]
[ [ 0, 1 ], [ 2, 4 ], [ 3 ] ]
[ [ 0, 1 ], [ 3, 4 ], [ 2 ] ]
[ [ 0, 2 ], [ 1, 3 ], [ 4 ] ]
[ [ 0, 2 ], [ 1, 4 ], [ 3 ] ]
[ [ 0, 2 ], [ 3, 4 ], [ 1 ] ]
[ [ 0, 3 ], [ 1, 2 ], [ 4 ] ]
[ [ 0, 3 ], [ 1, 4 ], [ 2 ] ]
...
[ [ 2, 4 ], [ 0, 1 ], [ 3 ] ]
[ [ 2, 4 ], [ 0, 3 ], [ 1 ] ]
[ [ 2, 4 ], [ 1, 3 ], [ 0 ] ]
[ [ 3, 4 ], [ 0, 1 ], [ 2 ] ]
[ [ 3, 4 ], [ 0, 2 ], [ 1 ] ]
[ [ 3, 4 ], [ 1, 2 ], [ 0 ] ]

流れとしては


  • 1つめの組み合わせ c1に対して ekcを呼んで組み合わせを取得し

  • その組み合わせそれぞれについて


    • 入力からその組み合わせを取り除いたものを入力として再帰呼び出し



注意するべきは、再帰呼び出しの結果にオフセットを付けなければならないこと:

function epc (n, ks) {

if (ks.length === 1) return ekc(n, ks[0]).map(x => [x]);
const [k, ...krest] = ks;
const result = [];
ekc(n, k).forEach(c1 => {
// data to adjust offsets
const dict = new Map([...Array(n).keys()] // aka range(n)
.filter(m => !c1.includes(m))
.map((m, i) => [i, m]));
// recurseive call
epc(n - c1.length, krest).forEach(cns => {
result.push([c1, ...cns.map(cn => cn.map(x => dict.get(x)))]);
});
});
return result;
}


4. 適用/再現

前章で実装した epc を使って冒頭のツーペアを再現させよう:


ツーペアの列挙.js

epc(13, [2, 1]).map(([[i, j], [k]]) => {

const inv = n => 12 - n; // desc order
const [I, J, K] = [i, j, k].map(inv).map(repr);
console.log(`${I} ${I} ${J} ${J} ${K}`);
});

出力は 2章と同様になった。