1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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]

$\endgroup$
1
  • 1
    $\begingroup$ Thanks so much for this - it works completely. $\endgroup$ – Green Cloak Guy Jun 1 '17 at 17:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.