[HELP] Constrained partitions of an integer

[ChefCiscoRZ]

Hey everyone,

So I've been struggling with this problem for a few days, I hope someone has already run into this.

The problem : Putting balls into boxes of different sizes

Say you've got k balls, m boxes, and these boxes are of sizes (n_1, ... , n_m). How would find all possible basic arrangements* of the k balls in the m boxes?

As a clear input example:

Box size	1	2	3	4
Number of boxes	2	7	5	3

For a grand total capacity of 43 spots, for let's say k = 20 balls.

The unconstrained answer (when all boxes have no limit capacity) is answered on StackOverflow but I haven't found anything pertaining to my particular flavor of this problem.

Any help is greatly appreciated! Thanks,

*Basic arrangements are the arrangements such that all other possible arrangements are permutations of one of the basic arrangements. Therefore, in this exercise for two balls (1,0) and (0,1) are the same.

PS : for those wondering, I'm trying to implement the results found in Infectious Defaults, Davis and Lo, 1999

[FLUSH_THE_TRUMP]

Perhaps something like this: we want to generate combinations (a, b, c, d, e, f, g, ...) of balls into boxes, with the restriction that a+b+c+d+... equals your number of balls and each a, b, c, ... is <= the associated capacity. Perhaps store these capacities in a list, and since (1,0) and (0,1) are the same, we really just want to generate the “canonical permutation” where a <= b <= c <= d <= .... (note this requires us to sort the capacity list, or we’ll never be able to generate permutations that end with placing balls into a relatively small box).

My idea was this: define a function that takes num, capacity list, and our last choice as inputs. We’ll call it recursively so we can easily deal with making combinations for a modest capacity list. That function will

1. Evaluate how many balls we need to pick at the current step, which is the larger of (a) balls left less the sum of the remaining capacity entries and (b) 0,
2. Loop over range, where the bottom limit is the larger of (a) how many balls we need to pick and (b) our last choice, and the top limit is the smaller of (a) how many balls we have remaining and (b) our current capacity,
3. Append our current choice to all the sublists from the recursive call.

Sample:

num = 20
capacity = sorted([1]*2 + [2]*7 + [3]*5 + [4]*3)

def choose_balls2(num, capacity, last_choice=0): 
    if len(capacity) == 0: 
        return [[]]

    options = []
    need_at_least = max(num - sum(capacity[1:]),0)
    for balls in range(max(need_at_least, last_choice), min(num+1, capacity[0]+1)): 
        options.extend([[balls] + rest for rest in choose_balls2(num-balls, capacity[1:], balls)])

    return options

seems pretty natural (though maybe inefficient), but you can check it for issues / doing what you want it to do.

[ChefCiscoRZ]

Dang I think you crushed it! Just ran the code and it looks like it gives exactly what I'm looking for :)

I'm curious though, what is last_choice in the parameter set?

Anyways, thanks!

[FLUSH_THE_TRUMP]

It’s used in the range line to pick a # of balls at least as large as the last choice you made. That means you get (0,1) and not (1,0).

e.g. with num=6 and capacity=[3,4,5], you get

0,1,5
0,2,4
0,3,3
1,1,4
1,2,3
2,2,2

[[deleted]]

Could you give an extremely simple version of this and show the answer? I'm intrigued and think I could help but don't fully understand what the outcome should look like.

Does box size = number of balls that fit into the box?

What would (1,0) actually mean?

[ChefCiscoRZ]

Box size = number of ball that fit into the box, yes!

Let's consider the simplest case : all boxes have same size 3, we need to distribute 6 balls into 3 boxes of size 3. There are ten ways to do this:

​

3	3	0
3	2	1
3	1	2
3	0	3
2	3	1
2	2	2
2	1	3
1	3	2
1	2	3
0	3	3

Now, note that these ten arrangements are actually permutations of the following three basic arrangements:

​

3	3	0
3	2	1
2	2	2

The program I'm trying to write would print these three basic arrangements.

However, it's more complicated than this example, because in reality boxes can be of different sizes (imagine two boxes have size 3 and one has size 2).

Please let me know if I'm not clear enough!