12

からの一連の数字があるとし[0, ....., 499]ます。現在、組み合わせは C++ を使用して順次生成されていますstd::next_permutation。参考までに、私が引き出している各タプルのサイズは 3 なので、 のような順次結果を返してい[0,1,2], [0,1,3], [0,1,4], ... [497,498,499]ます。

ここで、これが含まれているコードを並列化したいので、これらの組み合わせの順次生成は機能しなくなります。ith500 個の数字から 3 個の組み合わせを計算する既存のアルゴリズムはありますか?

取得するループの反復に関係なく、各スレッドが、反復する に基づいてスタンドアロンの組み合わせを計算できるようにしたいと考えていますi。したがってi=38、スレッド 1 での組み合わせが必要な場合は、スレッド 2 で を計算[1,2,5]しながら同時にを計算できます。i=0[0,1,2]

編集以下のステートメントは無関係です、私は自分自身を混同しました

階乗を利用して個々の要素を左から右に絞り込むアルゴリズムを見てきましたが、これらを500として使用することはできません! 確かにメモリに収まりません。助言がありますか？

4

3 に答える 3

5

これが私のショットです：

int k = 527; //The kth combination is calculated
int N=500; //Number of Elements you have
int a=0,b=1,c=2; //a,b,c are the numbers you get out

while(k >= (N-a-1)*(N-a-2)/2){
    k -= (N-a-1)*(N-a-2)/2;
    a++;
}
b= a+1;
while(k >= N-1-b){
    k -= N-1-b;
    b++;
}

c = b+1+k;


cout << "["<<a<<","<<b<<","<<c<<"]"<<endl; //The result

次の数が増えるまでに何通りの組み合わせがあるか考えてみました。ただし、3 つの要素に対してのみ機能します。それが正しいとは保証できません。それをあなたの結果と比較して、フィードバックをお寄せいただければ幸いです。

于 2013-02-25T02:38:55.640 に答える
2

順列ではなく、一意の組み合わせの辞書式インデックスまたはランクを取得する方法を探している場合、問題は二項係数に該当します。二項係数は、合計 N 個の項目を持つ K 個のグループで一意の組み合わせを選択する問題を処理します。

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

  1. 任意の N choose K について、すべての K-index を適切な形式でファイルに出力します。K インデックスは、よりわかりやすい文字列または文字で置き換えることができます。

  2. K インデックスを適切な辞書式インデックスまたは並べ替えられた二項係数テーブル内のエントリのランクに変換します。この手法は、反復に依存する以前に公開された手法よりもはるかに高速です。これは、パスカルの三角形に固有の数学的プロパティを使用して行われ、セットの反復処理に比べて非常に効率的です。

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

  4. Mark Dominusメソッドを使用して二項係数を計算します。これは、オーバーフローする可能性がはるかに低く、より大きな数で機能します。

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

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

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

次のテスト済みコードは、一意の組み合わせごとに反復します。

public void Test10Choose5()
{
   String S;
   int Loop;
   int N = 500;  // Total number of elements in the set.
   int K = 3;  // Total number of elements in each group.
   // 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);
   // The Kindexes array specifies the indexes for a lexigraphic element.
   int[] KIndexes = new int[K];
   StringBuilder SB = new StringBuilder();
   // 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(Combo, KIndexes);
      // Verify that the Kindexes returned can be used to retrive the
      // rank or lexigraphic order of the KIndexes in the table.
      int Val = BC.GetIndex(true, KIndexes);
      if (Val != Combo)
      {
         S = "Val of " + Val.ToString() + " != Combo Value of " + Combo.ToString();
         Console.WriteLine(S);
      }
      SB.Remove(0, SB.Length);
      for (Loop = 0; Loop < K; Loop++)
      {
         SB.Append(KIndexes[Loop].ToString());
         if (Loop < K - 1)
            SB.Append(" ");
      }
      S = "KIndexes = " + SB.ToString();
      Console.WriteLine(S);
   }
}

このクラスは、かなり簡単に C++ に移植できるはずです。目標を達成するために、クラスのジェネリック部分を移植する必要はおそらくないでしょう。500 choose 3 のテスト ケースでは、4 バイトの int に収まる 20,708,500 の一意の組み合わせが得られます。500 choose 3 が単なる例であり、3 より大きい組み合わせを選択する必要がある場合は、long または固定小数点 int を使用する必要があります。

于 2013-02-25T02:37:07.477 に答える
0

500 個のオブジェクトのうち 3 個の特定の選択をトリプルとして記述することが(i, j, k)できますi。j最初)、k0 から 497 までの範囲 (最後のインデックス、以前に選択された両方の番号をスキップ)。(0,0,0)それを考えると、可能なすべての選択肢を列挙するのは実際には非常kに簡単です:独自の最大値; 次に、両方をインクリメントしてリセットし、続行します。jkjjijk

この説明がおなじみのように聞こえる場合は、基数がはるかにファンキーであり、実際には基数が桁ごとに異なることを除いて、基数 10 の数値をインクリメントするのとまったく同じ方法であるためです。この洞察を使用して、アイデアの非常にコンパクトなバージョンを実装できますn。0 から 500*499*498 までの任意の整数について、次を取得できます。

struct {
  int i, j, k;
} triple;

triple AsTriple(int n) {
  triple result;
  result.k = n % 498;
  n = n / 498;
  result.j = n % 499;
  n = n / 499;
  result.i = n % 500;  // unnecessary, any legal n will already be between 0 and 499
  return result;
}

void PrintSelections(triple t) {
  int i, j, k;
  i = t.i;
  j = t.j + (i <= j ? 1 : 0);
  k = t.k + (i <= k ? 1 : 0) + (j <= k ? 1 : 0);
  std::cout << "[" << i << "," << j << "," << k << "]" << std::endl;
}

void PrintRange(int start, int end) {
  for (int i = start; i < end; ++i) {
    PrintSelections(AsTriple(i));
  }
}

シャードにするには、0 から 500*499*498 までの数値を取り、それらを任意の方法でサブ範囲に分割し、各シャードにそのサブ範囲内の各値の順列を計算させることができます。

このトリックは、サブセットを列挙する必要がある問題に対して非常に便利です。

于 2013-02-25T02:25:11.440 に答える