Function to determine number of unordered combinations with non-unqiue choices

Question

I'm trying to determine the function for determining the number of unordered combinations with non-unique choices.

Given:

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

Example... for n=3, r=3, the result would be: (edit: added missing values pointed out by Dav)

000
001
002
011
012
022
111
112
122
222

I know the formula for permutations (unordered, unique selections), but I can't figure out how allowing repetition increases the set.

Answer 1

If you have N unique symbols, and want to select a combination of length R, then you are essentially putting N-1 dividers into R+1 "slots" between cumulative total numbers of symbols selected.

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

The C's are choices, the numbers are the cumulative count of choices made so far. You're essentially putting a divider for each possible thing you could choose of when you "start" choosing that thing (it's assumed that you start with choosing a particular thing before any dividers are placed, hence the -1 in the N-1 dividers).

If you place all of the dividers are spot 0, then you chose the final thing for all of the choices. If you place all of the dividers at spot 3, then you choose the initial thing for all of the choices. In general, if you place the ith divider at spot k, then you chose thing i+1 for all of the choices that come between that spot and the spot of the next divider.

Since we're trying to put N-1 non-unique items (the dividers are non-unique, they're just dividers) around R slots, we really just want to permute N-1 1's and R 0's, which is effectively

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

Thus the final formula is (N+R-1)!/((N-1)!R!) for the number of unordered combinations with non-unique selection of items.

Note that this evaluates to 10 for N=3, R=3, which matches with your result... after you add the missing options that I pointed out in comments above.

Answer 2

In C++ given the following routine:

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;
}

You can then proceed to do the following:

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