用于确定具有非unqiue选择的无序组合的数量的函数

Question

我正在尝试确定用于确定具有非唯一选择的无序组合的数量的函数.

鉴于:

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

我知道排列的公式(无序,唯一选择),但我无法弄清楚允许重复如何增加集合.

Answer 1

在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()));

Answer 2

如果您有N唯一的符号，并且想要选择 length 的组合R，那么您实际上是将N-1分隔线放入R+1所选符号的累积总数之间的“槽”中。

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

C 是选择，数字是迄今为止所做选择的累积计数。当您“开始”选择该事物时，您实质上是为您可以选择的每个可能的事物放置一个分隔线（假设您在放置任何分隔线之前先选择特定的事物，因此分隔线中的 -1 N-1）。

如果您将所有分隔线都放置在 0 位置，那么您就为所有选项选择了最后一个。如果您将所有分隔线放在位置 3，那么您将为所有选项选择第一个。一般来说，如果您将第 i 个分隔线放置在位置k处，那么您会为该位置和下一个分隔线位置之间的所有选择选择事物i+1 。

由于我们试图将N-1非唯一项（分隔符不是唯一的，它们只是分隔符）放在R插槽周围，因此我们实际上只想排列N-11 和R0，这实际上是

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

因此，最终公式是(N+R-1)!/((N-1)!R!)具有非唯一项目选择的无序组合的数量。

请注意，对于 N=3、R=3，其计算结果为 10，这与您的结果相匹配...在您添加了我在上面的评论中指出的缺少的选项之后。