5

一意でない選択肢を持つ順序付けられていない組み合わせの数を決定する関数を決定しようとしています。

与えられた:

n = number of unique symbols to select from
r = number of choices

例... n = 3、r = 3の場合、結果は次のようになります: (編集: Davによって指摘された欠損値を追加)

000
001
002
011
012
022
111
112
122
222

順列 (順序付けされていない一意の選択) の公式は知っていますが、繰り返しを許可するとセットがどのように増加するのかわかりません。

4

2 に答える 2

7

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

template <typename Iterator>
bool next_combination(const Iterator first, Iterator k, const Iterator last)
{
   /* Credits: Mark Nelson http://marknelson.us */
   if ((first == last) || (first == k) || (last == k))
      return false;
   Iterator i1 = first;
   Iterator i2 = last;
   ++i1;
   if (last == i1)
      return false;
   i1 = last;
   --i1;
   i1 = k;
   --i2;
   while (first != i1)
   {
      if (*--i1 < *i2)
      {
         Iterator j = k;
         while (!(*i1 < *j)) ++j;
         std::iter_swap(i1,j);
         ++i1;
         ++j;
         i2 = k;
         std::rotate(i1,j,last);
         while (last != j)
         {
            ++j;
            ++i2;
         }
         std::rotate(k,i2,last);
         return true;
      }
   }
   std::rotate(first,k,last);
   return false;
}

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

std::string s = "12345";
std::size_t r = 3;
do
{
   std::cout << std::string(s.begin(),s.begin() + r) << std::endl;
}
while(next_combination(s.begin(), s.begin() + r, s.end()));
于 2010-04-13T13:56:24.520 に答える
3

N一意のシンボルがあり、 length の組み合わせを選択したい場合Rは、基本的に、選択されたシンボルの累積総数の間の「スロット」にN-1仕切りを入れています。R+1

0 [C] 1 [C] 2 [C] 3

C は選択肢、数字はこれまでの選択肢の累積数です。基本的に、選択できるものごとに仕切りを配置します (仕切りを配置する前に特定のものを選択することから始めると想定されているため、N-1仕切りの -1 )。

すべての仕切りをスポット 0 に配置すると、すべての選択肢の最後のものを選択したことになります。すべての仕切りをスポット 3 に配置すると、すべての選択肢の最初のものを選択します。一般に、i 番目の仕切りをスポットkに配置すると、その場所と次の仕切りの場所の間にあるすべての選択肢に対してi+1を選択したことになります。

スロットのN-1周りに一意ではないアイテム (仕切りは一意ではなく、単なる仕切りです)を配置しようとしているので、実際には1 と0 を並べ替えるだけで効果的です。RN-1R

(N+R-1) choose (N-1)= (N+R-1)!/((N-1)!R!).

したがって、最終的な式は(N+R-1)!/((N-1)!R!)、項目の選択が一意でない順序付けられていない組み合わせの数です。

これは、N = 3、R = 3 の場合、結果と一致する 10 と評価されることに注意してください...上記のコメントで指摘した不足しているオプションを追加した後。

于 2009-12-25T00:43:34.907 に答える