1

Kのいくつかの値について、 N個のアイテムを含むベクトルVからk個のアイテムを取り出すすべての組み合わせで反復する必要があります。たとえば、N=6およびk=3の場合、アイテムV 1、V 2、およびV [3]でF（）を呼び出し、次にアイテムV 1、V 2、およびV [4]で呼び出し、V[4で終わる必要があります。 ]、V[5]およびV[6]。

これで、インデックスのすべての組み合わせを簡単に確認できます。k=3およびN=6と言います。次に、最初の要素は1からN-（k-1）に、2番目の要素は2からN-（k-2）に、k番目はkからN（つまり、N -（kk））。

したがって、k = 3の場合、ループは次のようになります。

for (uint a = 1, a <=  N-2, a++)
  for (uint b = a + 1, b <= N-1, b++)
    for (uint c = b + 1, c <= N, c++)
     F(V[a], V[b], V[c])

また、k = 4の場合、反復は次のようになります。

for (uint a = 1, a <=  N-3, a++)
  for (uint b = a + 1, b <= N-2, b++)
    for (uint c = b + 1, c <= N - 1, c++)
       for (uint d = c + 1, d <= N, d++)
          F(V[a], V[b], V[c], V[d])

ただし、問題は次のとおりです。任意のkをハードコーディングせずに（またはコード生成を使用せずに）、このkレベルのネストをどのように実現しますか？

編集：背景については（別名これは宿題ではありません:)）私の数学Stackexchangeの質問に対するハンスエングラーの答えを参照してください： 0-1ナップザックのような-含まれていないすべての手頃なバイナリセレクションのセット

編集：サンプルを提供します。V={1,2,3,4,5}と仮定します。

k = 2の場合、Fを次の順序で呼び出す必要があります：F（1,2）、F（1,3）、F（1,4）、F（1,5）、F（2,3）、 F（2,4）、F（2,5）、F（3,4）、F（3、5）およびF（4,5）。

k = 3の場合、Fを次の順序で呼び出す必要があります：F（1,2,3）、F（1,2,4）、F（1,2,5）、F（2,3,4、 ）、F（2,3,5）、F（3,4,5）

4

2 に答える 2

1

これは宿題のようなにおいがしますが、それは大丈夫ですが、宿題であることを示す必要があります。

いずれにせよ、明確な終わりのない一連のループに飛び込んでいるのを見ると、再帰が役立つ可能性があります。以下のクラスを考えてみましょう。関数F（）の内臓は空のままにしておきますが、妥当なパスを示します（私は思います）。

class Program
{
    private void F(int[] vector, int k)
    {
        if (vector.Length > 0)
        {
            // TO DO: operate on the first k elements of vector
            // Question: what conditions will throw an exception?
            Console.WriteLine("now operating on vector of length: " + vector.Length);

            // Re-define vector and re-apply F()
            vector = vector.Skip(1).Take(vector.Length - 1).ToArray();
            F(vector, k);
        }

    }


    static void Main(string[] args)
    {
        int[] vector = { 0, 1, 1, 2, 3 };
        int k = 3;

        try
        {
            Program p = new Program();
            p.F(vector, k);
        }
        catch (Exception ex)
        {

            Console.WriteLine("Unhandled exception: " + ex.Message);
            System.Environment.Exit(1);
        }
        finally
        {
            if (System.Diagnostics.Debugger.IsAttached)
            {
                Console.Write("Any key to continue...");
                Console.ReadKey();
            }
        }
    }
}
于 2012-11-27T14:29:31.103 に答える
1

コードサンプルは、順列ではなく、一意の組み合わせを生成しています。組み合わせは、順序に関係なく一意です。たとえば、データが次のようになっている場合（123、231、321）、順列を操作していることになります。組み合わせは、二項係数の領域に分類されます。

二項係数を操作するための一般的な関数を処理するクラスをC＃で作成しました。次のタスクを実行します。

  1. すべてのKインデックスを、任意のN選択Kのファイルに適切な形式で出力します。Kインデックスは、より説明的な文字列または文字に置き換えることができます。

  2. Kインデックスを、ソートされた二項係数テーブルのエントリの適切なインデックスに変換します。この手法は、反復に依存する以前に公開された手法よりもはるかに高速です。これは、パスカルの三角形に固有の数学的プロパティを使用して行われます。

  3. ソートされた二項係数テーブルのインデックスを対応するKインデックスに変換します。また、古い反復ソリューションよりも高速であると思います。

  4. マークドミナス法を使用して二項係数を計算します。二項係数はオーバーフローする可能性がはるかに低く、より大きな数値で機能します。

  5. このクラスは.NETC＃で記述されており、ジェネリックリストを使用して問題に関連するオブジェクト（存在する場合）を管理する方法を提供します。このクラスのコンストラクターは、InitTableと呼ばれるbool値を取ります。これは、trueの場合、管理対象のオブジェクトを保持するためのジェネリックリストを作成します。この値がfalseの場合、テーブルは作成されません。上記の4つの方法を使用するために、テーブルを作成する必要はありません。テーブルにアクセスするためのアクセサメソッドが提供されています。

  6. クラスとそのメソッドの使用方法を示す関連するテストクラスがあります。2つのケースで広範囲にテストされており、既知のバグはありません。

このクラスについて読んでコードをダウンロードするには、二項係数の表化を参照してください。

次のコードは、一連の組み合わせを順番に繰り返します。

int N = 6;  // Total number of elements in the set.
int K = 3;  // Total number of elements in each group.
int[] V = new int[N]; // Holds the vector of numbers.
// Create the bin coeff object required to get all
// the combos for this N choose K combination.
BinCoeff<int> BC = new BinCoeff<int>(N, K, false);
int NumCombos = BinCoeff<int>.GetBinCoeff(N, K);
int[] KIndexes = new int[K];
// Loop thru all the combinations for this N choose K case.
for (int Combo = 0; Combo < NumCombos; Combo++)
{
   // Get the k-indexes for this combination.
   BC.GetKIndexes(Loop, KIndexes);
   // Do whatever processing with the V array that needs to be done.
   // Code to print the values out in C#:
   String S = V[KIndexes[0]].ToString() + ", " + V[KIndexes[1]].ToString() + ", " + 
      V[KIndexes[2]].ToString();
   Console.WriteLine(S};
}

このクラスは、選択した言語にかなり簡単に移植できるはずです。目標を達成するために、クラスの一般的な部分を移植する必要はおそらくないでしょう。使用している組み合わせの数によっては、4バイトintよりも大きいワードサイズを使用する必要がある場合があります。

于 2012-11-27T16:34:21.763 に答える