F#

組み合わせの列挙

More than 1 year has passed since last update.

組み合わせを列挙しようとして手が止まりました。基本的なアルゴリズムのはずなのに、いざ実装しようとすると思いのほか難しいです。検索してみると同じように感じた方が多いようで、色々な実装が出て来ました。屋上屋を架すことにはなりますが、試みた実装を説明します。

F#
let combination n k =
    let rec f i = function
    | [] -> []
    | x::xs ->
        match f (i + 1) xs with
        | [] -> if x + k - i > n then [] else [x + 1 .. x + k - i]
        | ys -> x::ys
    let rec g = function
    | [] -> []
    | xs -> xs :: g (f 0 xs)
    g [1..k]

printfn "%A" (combination 4 2)
実行結果
[[1; 2]; [1; 3]; [1; 4]; [2; 3]; [2; 4]; [3; 4]]

方針

手作業で組み合わせを列挙する場合、次のように考えます。

【例】 {1,2,3,4} から2個を取り出した組み合わせ

組み合わせ.png

これをなるべく素直に実装してみようと考えました。

特徴

挙動を観察すると、次のような特徴が分かります。

  • 左の数字<右の数字(組み合わせでは順番を区別しないため、便宜的な取り決め)
  • 2桁の数字を数えるのに似ている。右の数字がカウントアップして、繰り上がると左の数字がカウントアップする。

実装

カウントアップの考え方で次の組み合わせを求めてみます。最後まで行けば空リストを返します。

let next n cur =
    let k = List.length cur
    let rec f i = function
    | [] -> []
    | x::xs ->
        match f (i + 1) xs with
        | [] -> if x + k - i > n then [] else [x + 1 .. x + k - i]
        | ys -> x::ys
    f 0 cur

printfn "%A" (next 4 [1;2])
printfn "%A" (next 4 [1;4])
printfn "%A" (next 4 [3;4])
実行結果
[1; 3]
[2; 3]
[]

x + k - i がポイントです。変数の意味は次のようになっています。

変数 意味
n 上限
k 全体の桁数
i 現在桁の位置(0 始まり)
x 現在桁の値

繰り上がった時の次の値は上位桁に依存するため、下位桁だけで決めることはできません。たとえば 14 の場合、次の組み合わせを求めるとき 4 で繰上りが発生したことが上位桁に通知され 23 を生成します。このときの最下位桁 3 の値が x + k - i です。同様に 34 の場合は 45 になりそうですが、5 は上限 4 を超えているためそこで終了です。そのため n と比較してチェックしています。

f を使って、初期リストを与えて空リストになるまでカウントアップを繰り返せば、列挙が得られます。これが冒頭の実装です。