3

順序付けられた組み合わせをランク付け/ランク解除できるライブラリを探しています。ランク付けとは、組み合わせから、グレイコードまたは辞書式またはその他のアルゴリズムからのn番目の組み合わせを提供することを意味し、ランク付け解除は逆のプロセスです。

グレイ コード、辞書式、rev-辞書式、enup などの多くのアルゴリズムを実行するライブラリを探しています。

生成だけならアルゴリズムもたくさんあってもいい。

FXT ライブラリを見つけましたが、順序付きの組み合わせを使用していません。それは構成を行いますが、必要に応じてランキングのアルゴリズムを実行しないようです。ランク付け/ランク付けされていない順序付けられていない組み合わせに匹敵します。

4

2 に答える 2

2

それはあなたの質問に対する完全な答えではありませんが、まさにこのトピックに関する優れた本Combinatorial Algorithms: Generation, Enumeration, and Search があります。

アルゴリズム/数学的な側面と実際の実装の間でバランスが取れています。ほとんどの例は、C のような手続き型言語で非常に短い時間で記述できるほど単純です。

于 2010-08-09T17:56:08.403 に答える
1

次のようなものが必要ですか。

// get a combination of a rank
// n number k choices N rank

void unrankComb(int* &K, int n, int k, int N)
{
 int e, N2, t, m, p;

 e = nCr(n,k);
 N2 = e-1-N;
 e = ((n - k)*e)/n;
 t = n - k + 1;
 m = k;
 p = n -1;
 do
 {
  if(e <= N2)
  {
   K[k-m] = n - t - m + 2;
   if(e > 0)
   {
    N2 = N2 -e;
    e = (e * m) / p;
   }
   m = m -1;
   p = p -1;
  }
  else
  {
   e = ((p - m)*e) / p;
   t = t - 1;
   p = p - 1;
  }

 }while(m != 0);
}
于 2010-09-23T07:00:17.753 に答える