Unique combinations of $n$ non-unique elements in $k$ non-unique buckets with $c$ capacity

Question

I have $n$ non-unique elements, and I have $k$ unordered buckets that can hold anywhere from $0$ to $c$ elements, such that $c * k \geq n$. I would like to find all possible combinations.

For example, given $n=10$, $k=4$, and $c=4$, there are 7 possible distributions:

• 3322
• 3331
• 4222
• 4321
• 4330
• 4411
• 4420

where "3322", for example, means that two buckets have three elements each and the other two buckets have two elements each.

Another way to look at it, is that I want to find unique combinations of $k$ numbers less than or equal to $c$ such that their sum is equal to $n$.

Ideally I'd like an algorithm to be able to generate a list of all acceptable combinations, but knowing a formula for finding the number of combinations given arbitrary $n$, $k$, and $c$ would be helpful. Other answers generally assume buckets have to have a minimum capacity of 1, or they deal with unique elements to some degree, which are not the case here.

Answer 1

First, it is important to note that all solutions can be arranged in descending sorted order. This is useful for the algorithm I will describe, such that it only searches for sorted answers.

Essentially, we start at the first bucket and assign it some item count $0\leq i\leq c$. Now, we realize that assigning the remaining items to the remaining buckets is essentially the same problem, except now we have $n-i$ items, $k-1$ buckets, and each remaining bucket can now only hold up to $i$ items, because if it were to hold anymore, the solution would be unsorted.

Only when we reach the end (no buckets and no items left) do we have a proper solution. This algorithm can also be sped up by realizing that if $\frac{n-i}{k-1}>i$, there is no continuing from this point, as the remaining items can not fit in the remaining buckets without going over $i$.

Below is a solution in Python,

def buckets(n,k,c,solution=[]):
    total = 0
    for i in range(min(c,n),-1,-1):
        if k-1 != 0 and float(n-i)/(k-1) > i:
            #Can't fit remaining items
            break
        solution.append(i)
        if n-i == 0 and k-1 == 0:
            #We've reached the end of the buckets and have a solution
            print(solution)
            solution.pop()
            return 1
        elif k-1 != 0:
            #If there's still buckets left, try assigning them
            total += buckets(n-i,k-1,i,solution)
        #Done checking this bucket assignment
        solution.pop()
    return total

buckets(10,4,4)

[4, 4, 2, 0]

[4, 4, 1, 1]

[4, 3, 3, 0]

[4, 3, 2, 1]

[4, 2, 2, 2]

[3, 3, 3, 1]

[3, 3, 2, 2]