get a specific combination with replacement

Question

I know how to calculate the total number of combinations of n different objects taken k at a time, with replacement:

(n+k-1)!/k!/(n-1)!

What I need is a formula or algorithm to recover the i-th such combination from an ordered list.

Say I have an ordered list of all combinations of a,b,c taken 3 at a time (so n=3 and k=3):

1 aaa 2 aab 3 aac 4 abb 5 abc 6 acc 7 bbb 8 bbc 9 bcc 10 ccc

How would I calculate the i-th (say 7-th) combination in this list, without first enumerating them all ? Enumerating will be very inefficient for any but the simplest cases, if I am only interested in a few specific combinations. For instance, there are 119,877,472 combinations of 64 items taken 6 at a time. Needless to say, I need a solution for arbitrary n, k and i. The reverse function (given the combination, how to calculate its index) would also be interesting.

I found one similar question, but it was about permutations, not combinations: I want to get a specific combination of permutation? And there are many ways to list all the combinations, such as mentioned here: How to generate all permutations and combinations with/without replacement for distinct items and non distinct items (multisets) But they don't give the functions I need

Answer 1

The algorithm you are interested in is very easy to implement. The first thing you should understand is why actually C(k, n + k - 1) = C(n - 1, n + k - 1) = (n + k - 1)! / k! / (n - 1)! formula works. Formula says that the number of ways to take k items out of n is the same as to take n-k items out of n.

Lets say your objects are balls of some color. There are n different colors numbered from 1 to n. You need to calculate the number of ways to have k balls. Imagine initially k white balls (without any color) so you need to paint them in different ways. Arrange the balls in a row. Choose some k₁ ≥ 0 balls from the left to paint in color #1, next k₂ ≥ 0 balls we paint in #2, and so on... We have ∑k_i = k. A series of k₁ balls painted in color #1 is followed by k₂ of color #2, next by k₃ of color #3 etc...

We can do the same painting in a slightly different way however. In order to separate k_i-1- and k_i-colored balls we would use delimiters. In total we should have n - 1 such delimiters to be placed among the balls. The delimiters are ordered, one that separates 1-colored and 2-colored balls should appear before another that separates 2-colored and 3-colored. If some k_i = 0 then corresponding delimiters appear one by one. We have to arrange delimiters and balls in some way.

Interestingly we can imagine now that both n - 1 delimiters and k balls are just objects initially placed in a row. We have to choose either n - 1 of them to declare selected objects to be delimiters or k objects to be balls. And that's where well-known combination formula can be applied.

---

Example for your case:

o - ball
. - delimiter
a, b, c - colors

We have:
ooo.. => aaa
oo.o. => aab
oo..o => aac
o.oo. => abb
o.o.o => abc
o..oo => acc
.ooo. => bbb
.oo.o => bbc
.o.oo => bcc
..ooo => ccc

Notice the pattern how delimiters move from right to left.

---

Algorithm

Now to the question of how to get the p-th arrangement. Efficient algorithm description follows. Remember that we have k balls and nd = n - 1 delimiters. We will be placing delimiters one by one first trying their rightmost positions. Consider leaving current delimiter at its current position, calculate the number of combinations to place the remaining objects to the right, let the number be some N. Compare N with p, if p is greater or equal to N then reduce p by N (p <- p - N) and we should move current delimiter left by 1. Else if p is lower than N then we will not move current delimiter but proceed to the next one trying to move it again from the rightmost position. Note that p-th arrangement is zero-based.

Having "converted" some i-th object to j-th delimiter we have N = C(nd - j, nd + k - i) number of ways to arrange remaining k - i + j balls and nd - j delimiters.

Since we'll often refer to binomial coefficients we'd better make their precalculation.

The reverse function may be implemented accordingly. You have positions for every delimiter. Accumulate the number of ways to arrange remaining objects while moving ordinary delimiter to its place from the rightmost position.

Example:

3 balls, 2 delimiters, find 7-th arrangement (which is bbc or .oo.o)

Place delimiters to the rightmost position: ooo... Let first delimiter be current.

Calculate N = C(1, 1) = 1, p ≥ N so we reduce p by N getting p = 6. At the same time we move current delimiter 1 pos left getting oo.o..

Calculate N = C(1, 2) = 2, p ≥ N, reduce p by N getting p = 6 - 2 = 4. Move getting o.oo..

Calculate N = C(1, 3) = 3, p ≥ N once again, move and reduce p getting p = 1 and .ooo..

Calculate N = C(1,4) = 4, p < N. Good, we've found final position for the first delimiter so leave it there and take second delimiter as current.

Calculate N = C(0,0) = 1, p ≥ N, p = 1 - 1 = 0, move, .oo.o.

Calculate N = C(0,1) = 1, p < N, found final position for the second delimiter. Resulting arrangement is .oo.o => bbc.

EDIT #1. Changed the algo description and added example.

Answer 2

here is the function (not optimized but working):

findcomb <- function(n, k, p) {
  # n = nr of object types (colors, letters etc)
  # k = number of objects (balls) to select
  # p = 0-based index of target combination
  # return = positions of delimiters at index p
  nd <- n-1 #nr of delimiters: 1 - nr of colors
  pos <- seq(n+k-nd, n+k-1) #original positions of delimiters, all at right
  for (j in 1:(nd-1)) {
    s <- 0 #cumulative nr of accounted-for combinations with this delimiter
    while (TRUE) {
      N <- choose(nd+k-pos[j], nd-j)
      if (s + N <= p) {
        pos[j] <- pos[j] - 1
        s <- s + N
      } else break
    }
    p <- p - s
  }
  #last delimiter:
  pos[nd] <- pos[nd] - p
  pos
}