11

特に理由はありませんが、1...n の間の k 個の整数のすべての可能な選択肢を生成するアルゴリズムを探すことにしました。ここで、k 個の整数の順序は重要ではありません (n は k のものを選択します)。

まったく同じ理由で、まったく理由はありませんが、C# でも実装しました。私の質問は：

私のアルゴリズムやコードに誤りはありますか? さらに重要なのは、より良いアルゴリズムを提案できますか?

コード自体よりもアルゴリズムに注意を払ってください。これは私がこれまでに書いた中で最も美しいコードではありませんが、エラーが発生した場合は教えてください。

編集：アルゴリズムの説明-

  • k 個のインデックスを保持します。
  • これにより、 forループのネストされた k が作成されます。ここで、ループ i のインデックスは index[i] です。
  • これは、インデックス[i+1] がインデックス[i] のループ内にネストされたループに属するループのkをシミュレートします。
  • インデックス[i] は、インデックス[i - 1] + 1 から n - k + i + 1 まで実行されます。

コード：

public class AllPossibleCombination
{
    int n, k;
    int[] indices;
    List<int[]> combinations = null;

    public AllPossibleCombination(int n_, int k_)
    {
        if (n_ <= 0)
        {
            throw new ArgumentException("n_ must be in N+");
        }
        if (k_ <= 0)
        {
            throw new ArgumentException("k_ must be in N+");
        }
        if (k_ > n_)
        {
            throw new ArgumentException("k_ can be at most n_");
        }

        n = n_;
        k = k_;
        indices = new int[k];
        indices[0] = 1;
    }

    /// <summary>
    /// Returns all possible k combination of 0..n-1
    /// </summary>
    /// <returns></returns>
    public List<int[]> GetCombinations()
    {
        if (combinations == null)
        {
            combinations = new List<int[]>();
            Iterate(0);
        }
        return combinations;
    }

    private void Iterate(int ii)
    {
        //
        // Initialize
        //
        if (ii > 0)
        {
            indices[ii] = indices[ii - 1] + 1;
        }

        for (; indices[ii] <= (n - k + ii + 1); indices[ii]++)
        {
            if (ii < k - 1)
            {
                Iterate(ii + 1);
            }
            else
            {
                int[] combination = new int[k];
                indices.CopyTo(combination, 0);
                combinations.Add(combination);
            }
        }
    }
}

長い質問で申し訳ありません。ブログ投稿に適しているかもしれませんが、ここでコミュニティの意見を求めています。

ありがとう、
アサフ

4

4 に答える 4

9

C ++では、次のルーチンが与えられます。

template <typename Iterator>
inline bool next_combination(const Iterator first, Iterator k, const Iterator last)
{
   /* Credits: Thomas Draper */
   if ((first == last) || (first == k) || (last == k))
      return false;
   Iterator itr1 = first;
   Iterator itr2 = last;
   ++itr1;
   if (last == itr1)
      return false;
   itr1 = last;
   --itr1;
   itr1 = k;
   --itr2;
   while (first != itr1)
   {
      if (*--itr1 < *itr2)
      {
         Iterator j = k;
         while (!(*itr1 < *j)) ++j;
         std::iter_swap(itr1,j);
         ++itr1;
         ++j;
         itr2 = k;
         std::rotate(itr1,j,last);
         while (last != j)
         {
            ++j;
            ++itr2;
         }
         std::rotate(k,itr2,last);
         return true;
      }
   }
   std::rotate(first,k,last);
   return false;
}

その後、次の手順に進むことができます。

std::string s = "123456789";
std::size_t k = 3;
do
{
   std::cout << std::string(s.begin(),s.begin() + k) << std::endl;
}
while(next_combination(s.begin(),s.begin() + k,s.end()));
于 2009-10-25T20:18:09.173 に答える
2

アサフ、

あなたは私たちにあなたのアルゴリズムを評価するように求めていますが、コードのコメントでさえ、あなたのアルゴリズムを説明していません. では、回答する前に質問を理解できるように、コードからアルゴリズムをリバース エンジニアリングするために、全員に 1 時間以上かけてもらいたいということですか?

質問を編集してアルゴリズムを説明してください。

明らかなことの 1 つは、コードのメモリ フットプリントが恐ろしいことです。n の値が小さい場合でも、組み合わせの数は簡単に数十億になり、ほとんどのコンピューターよりも多くのメモリが必要になります。さらに、動的に成長する配列を使用しているため、成長するにつれて再割り当てとコピーが繰り返されます。さらに、プログラムは異なる配列でサブセットを生成し、それらをマージします。全体として、プログラムはリストを保存するために理想的に必要とされる量の何倍ものメモリを必要とし、データを前後にコピーするだけでほとんどの時間を費やします。

一度に配列内のすべての値を取得する必要がある場合は、少なくとも、必要な配列のサイズを計算することから始めます -- n! /（nk）！/k！--そして、それを埋めるだけです。

さらに良いのは、必要に応じてシーケンスの各メンバーを「怠惰に」計算するコードです。関連する質問サイドバーからこの質問を参照してください

于 2009-02-14T04:40:17.867 に答える
1

この男は、C# (CodeProject) を使用して組み合わせ論で真剣な仕事をしたようです:

C# ジェネリックを使用した順列、組み合わせ、バリエーション

于 2010-03-19T16:24:03.943 に答える
-1

これは、私が少し前に C で書いた比較的単純で効率的な nCr プログラムです。

main(n,k){float t=0,r=1;for(scanf("%d, %d",&n,&k);t++<k;r*=(1+n-t)/t);printf("%.0f\n",r);}

わかりました...読み取り可能なバージョン。=] (これが上記と 1:1 で対応しているかどうかはわかりません。)

void nCr(int n, int k) {
    float curK = 0, r = 1;
    while(curK < k) {
        ++curK;
        printf("%.0f\n", r);
        r *= (1 + n - curK) / curK;
    }
}

印刷する代わりにyield、リストに何か（C＃はわかりません）を追加できます。

于 2009-02-14T04:20:59.413 に答える