n から k の要素のすべての組み合わせを返すアルゴリズム 質問する

コンピュータプログラミングの芸術 第 4 巻: 冊子 3私が説明したものよりも、あなたの特定の状況にもっと合うものがたくさんあります。

グレイコード

当然ながら、遭遇する問題はメモリであり、セット内の要素が 20 個になるとすぐに問題が発生します ( ²⁰ C ₃ = 1140)。セットを反復処理する場合は、修正されたグレイ コード アルゴリズムを使用して、すべての要素をメモリに保持しないようにするのが最善です。これらは、前の組み合わせから次の組み合わせを生成し、繰り返しを回避します。さまざまな用途で、このようなアルゴリズムが多数あります。連続する組み合わせ間の差を最大化しますか? 最小化しますか? など。

グレイコードについて説明したオリジナルの論文の一部:

1. いくつかのハミルトン経路と最小変化アルゴリズム
2. 隣接インターチェンジ組み合わせ生成アルゴリズム

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

1. Eades、Hickey、Read Adjacent Interchange の組み合わせ生成アルゴリズムの効率的な実装(PDF、コードはPascal)
2. 組み合わせ発電機
3. 組み合わせグレイコードの調査（ポストスクリプト）
4. グレイコードのアルゴリズム

チェイスの回転（アルゴリズム）

フィリップ・J・チェイス、アルゴリズム 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)になります。したがって、4 つのものの 27 番目の辞書式の組み合わせは {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)

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

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