[解決済み] nからk個の要素の組み合わせをすべて返すアルゴリズム

質問

文字の配列を引数に取り、その中からいくつかを選択する関数を書きたい。

8文字の配列を与えて、その中から3文字を選びたいとします。すると、こうなるはずだ。

8! / ((8 - 3)! * 3!) = 56

3文字ずつからなる配列(または単語)を返す。

解き方は？

Art of Computer Programming 第4巻：Fascicle 3 は、私が説明した方法よりも、あなたの特定の状況に合うかもしれないこれらのトンを持っています。

グレーコード

もちろん、メモリの問題もありますし、すぐに20個の要素で問題が発生します。 ²⁰ C <サブ 3 = 1140. また、セットを繰り返し使用する場合は、メモリにすべてを保持しないように、修正グレーコードアルゴリズムを使用することが最善です。これは、前の組み合わせから次の組み合わせを生成し、繰り返しを避けるものです。このようなアルゴリズムは用途に応じてたくさんあります。連続する組み合わせの差を最大化したいのか、最小化したいのか、などなど。

グレーコードを記述した原著論文の一部。

1. ハミルトンパスと最小変化量アルゴリズム
2. 隣接インターチェンジ組合せ生成アルゴリズム

このトピックを扱った他の論文を紹介します。

1. Eades, Hickey, Read Adjacent Interchange Combination Generation Algorithmの効率的な実装 (PDF, Pascalによるコード付き)
2. 組合せジェネレータ
3. 組合せグレー符号の調査 (ポストスクリプト)
4. グレーコードのためのアルゴリズム

チェイス・ツィドル（アルゴリズム）

フィリップ・ジェイ・チェイス、` アルゴリズム 382: N個のオブジェクトのうちM個のオブジェクトの組合せ ' (1970)

C言語によるアルゴリズム ...

組合せの字句順索引（バックルズアルゴリズム515）

また、組み合わせはインデックス（辞書順）で参照することもできます。 インデックスを元に右から左へある程度変化することを理解すれば、組み合わせを復元するようなものを作ることができます。

そこで、集合 {1,2,3,4,5,6} があり、3つの要素が欲しいとします。1,2,3}とすると、要素間の差は1であり、順当かつ最小であると言えるでしょう。{1,2,4}は変化が1つで、辞書的には2番です。つまり、最後の場所の「変化」の数は、辞書的順序の1つの変化を占めます。2位の{1,3,4}は変化が1つですが、2位なのでより多くの変化を占めます（元の集合の要素数に比例します）。

私が説明した方法は分解です。集合からインデックスへ、逆を行う必要があるようですが、これはもっと厄介なことです。これは、次のような方法です。 バックル が問題を解決してくれます。いくつか書いてみました を計算するためのC言語 集合を表すのに数値の範囲ではなく、集合のインデックスを使ったので、常に0...nから作業していることになります。 注意してください。

1. 組み合わせは順序付けされないので、{1,3,2} = {1,2,3} --辞書的になるように順序付けします。
2. このメソッドには、最初の差分のセットを開始するための暗黙の0があります。

組合せの字句順索引（McCaffrey）

があります。 別の方法 しかし、Bucklesのような最適化機能はありません。幸いなことに、重複する組み合わせは生成されない。

セット を最大化するような ここで .

一例として 27 = C(6,4) + C(5,3) + C(2,2) + C(1,1) . つまり、27番目の辞書的な組み合わせは、4つのものです。{1,2,5,6}で、これが調べたい集合のインデックスになります。以下の例(OCaml)では、以下のものが必要です。 choose 関数、左から読者へ。

(* this will find the [x] combination of a [set] list when taking [k] elements *)
let combination_maccaffery set k x =
    (* maximize function -- maximize a that is aCb              *)
    (* return largest c where c < i and choose(c,i) <= z        *)
    let rec maximize a b x =
        if (choose a b ) <= x then a else maximize (a-1) b x
    in
    let rec iterate n x i = match i with
        | 0 -> []
        | i ->
            let max = maximize n i x in
            max :: iterate n (x - (choose max i)) (i-1)
    in
    if x < 0 then failwith "errors" else
    let idxs =  iterate (List.length set) x k in
    List.map (List.nth set) (List.sort (-) idxs)

小さくてシンプルな組み合わせのイテレータ

次の2つのアルゴリズムは、教則的な目的で提供されています。これらは、イテレータと（より一般的な）フォルダ全体の組み合わせを実装しています。 これらは可能な限り高速で、計算量は O( ⁿ C <サブ k ). メモリ消費量は、以下のように制限されます。 k .

まずイテレータから始め、各組み合わせに対してユーザーが提供する関数を呼び出します。

let iter_combs n k f =
  let rec iter v s j =
    if j = k then f v
    else for i = s to n - 1 do iter (i::v) (i+1) (j+1) done in
  iter [] 0 0

より一般的なバージョンでは、初期状態から始めて、ユーザが提供した関数を状態変数とともに呼び出すことになります。異なる状態間で状態を受け渡す必要があるため、forループは使用せず、代わりに再帰を使用します。

let fold_combs n k f x =
  let rec loop i s c x =
    if i < n then
      loop (i+1) s c @@
      let c = i::c and s = s + 1 and i = i + 1 in
      if s < k then loop i s c x else f c x
    else x in
  loop 0 0 [] x