函数确定具有非非齐次选择的无序组合的数量

如果你有 N 唯一符号,并希望选择长度组合 R ,那么你基本上是在 N-1 分割成 R+1 所选符号的累计总数之间的“槽”。

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

C是选项,数字是迄今为止所做选择的累计计数。基本上,当你“开始”选择某个对象时,你会为每个可能选择的对象放置一个分隔符(假设你先选择一个特定的对象,然后再放置任何分隔符,因此在 N-1 除法器)。

如果你把所有的分隔符都放在0点,那么你就为所有的选择选择选择了最后一件事。如果你把所有的分频器都放在3号位置,那么你就为所有的选择选择选择最开始的东西。一般来说,如果你把 伊思 现场除法器 K ,然后你选择了 I+ 1 对于所有在那个点和下一个分隔符的点之间的选择。

因为我们想 N-1型 非唯一物品(分隔器是非唯一的,它们只是分隔器)周围 R 吃角子老虎机,我们真的只是想换个位置 N-1 1和 R 0,这是有效的

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

因此,最后的公式是 (n+r-1)!/((N-1)!R!) 对于具有非唯一项选择的无序组合的数目。

请注意,对于n=3,r=3,此值为10,这与您的结果匹配…在你添加了我在上面评论中指出的缺失选项之后。

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