私は、M 内の要素のすべての可能な k 組み合わせのセット C (||M|| = m) を取得し、サブセットの k 組み合わせのセットで C をカバーするアプリケーションに取り組んでいます。 M のうちの N_i、||N_i|| = n < m ∀ N_i
したがって、カバーする (m 選択 k) 組み合わせがあり、n 要素の各セット Q_i には (n 選択 k) 組み合わせが含まれます。
私が望むのは、q が最小化されるようにセット Qi を構築するアルゴリズムです (つまり、(m が k を選択) / (n が k を選択) にできるだけ近くなります)。
したがって、たとえば、m=100、k=3、および n=10 の場合、10 個の要素のセットの最小セットが必要であり、それぞれの 3-組み合わせのセットが (100 が 3 を選択) 3- のセットをカバーするようになります。 Mの組み合わせ。
これが役立つかどうかはわかりませんが、問題が該当するタイプの問題である二項係数を操作するための一般的な関数を処理するクラスを作成しました。次のタスクを実行します。
任意の N choose K について、すべての K-index を適切な形式でファイルに出力します。K インデックスは、よりわかりやすい文字列または文字で置き換えることができます。この方法により、この種の問題を簡単に解決できます。
K インデックスを、並べ替えられた二項係数テーブル内のエントリの適切なインデックスに変換します。この手法は、反復に依存する以前に公開された手法よりもはるかに高速です。これは、パスカルの三角形に固有の数学的性質を使用して行われます。私の論文はこれについて語っています。この手法を発見して公開したのは私が最初だと思いますが、間違っている可能性があります。
ソートされた二項係数テーブルのインデックスを対応する K インデックスに変換します。
Mark Dominusメソッドを使用して二項係数を計算します。これは、オーバーフローする可能性がはるかに低く、より大きな数で機能します。
このクラスは .NET C# で記述されており、問題に関連するオブジェクト (存在する場合) をジェネリック リストを使用して管理する方法を提供します。このクラスのコンストラクターは、InitTable と呼ばれる bool 値を受け取ります。これが true の場合、管理対象のオブジェクトを保持する汎用リストが作成されます。この値が false の場合、テーブルは作成されません。上記の 4 つの方法を実行するためにテーブルを作成する必要はありません。テーブルにアクセスするためのアクセサ メソッドが用意されています。
クラスとそのメソッドの使用方法を示す関連するテスト クラスがあります。2 つのケースで広範囲にテストされており、既知のバグはありません。
このクラスについて読んでコードをダウンロードするには、二項係数の表化を参照してください。
このクラスを選択した言語に変換するのは難しくありません。
問題の説明から、N に対して 1 つのループ (K も変化する場合は別のループ) を設定し、その N、K の組み合わせに対して二項係数オブジェクト (BC) を作成する必要があるようです。組み合わせの合計数を取得するには、BC オブジェクトで GetBinCoeff() の符号なしロング バージョンを呼び出します。次に、各 BC オブジェクトの組み合わせの総数を調べる別のループを設定します。そのループ内で、BC GetKIndexes メソッドを呼び出して各インデックス (組み合わせ) の K-Index を取得し、計算を実行します。何を最小化しようとしているのか正確にはわかりません。私の提案が明確でない、または十分に役に立たない場合は、探している結果を明確に示す、より詳細な例を投稿してみてください。
この質問を数学オーバーフローにクロス投稿しました
これは、被覆設計問題と呼ばれる組合せ論でよく取り上げられる問題であることが判明しました。
一般に、最小値にかなり近いアルゴリズムはありますが、最小値を保証するアルゴリズムはありません。既存の既知のカバーと研究はここで見つけることができます