Possibilities to Split Book-Stack

Question

I'm struggeling with the following problem in Python. The problem is more like math specific than Python specific.

I've got a number of N books as a Stack. And a number of P stacks to split on. I'm looking for the possibilites to split this stack, avoiding repetitions and empty stacks.

So let's say my stack is 4 books tall, what are the possibilities to split on 2 stacks ?

The possibilities to split would be:

(1,3)
(2,2)

There would also be the possibility of (3,1), but since (1,3) is already in my output, I don't want (3,1) to be there too.

Another example:

5 books, 3 stacks

(3,1,1)
(2,2,1)

Solutions like (1,1,3), (2,1,2) are not in my output beacause they are redundant.

Im looking for an EFFICIENT way to compute the tuples of stacks. I'm working with a starting stack sizes up to 400, this stack could be split into another stack, which could also be split and so on.

Is there already a reference which covers this problem?

I think it would be easy to solve in combinatoric terms, but the problem here is, I am interested in the Possibilities themself and not just the number of possibilities !

Any help here?

cheers

Answer 1

Eliminating duplicates:

You can do this by taking the first permutation of each combination.

In other words having the smallest stacks in front. E.g {1,2,3},{1,3,2},{2,1,3},{2,3,1},{3,1,2},{3,2,1}

Efficiency:

You probably want to do this with recursion, so at each step you know the possible size of the stack is at least the size of the previous

You know that all following stackSizes have to be at least the current size. So the maximum size is the number of books left divided by the number of stacks left (floor).

E.g. 10 books left for 3 stacks. floor(10/3) = 3. Which is right because the max combination left at that point is {3,3,4}

Hence this will prevent you to step into a failing combination.

Code

import math

def bookStack(cur, min, booksLeft, sizes):
    if len(sizes) == (cur+1):
        sizes[cur] = booksLeft
        print(sizes)
        return;
    max = math.floor(booksLeft / (len(sizes)-cur))+1;
    for take in range(min,max):
        sizes[cur] = take
        bookStack(cur+1, take, booksLeft-take, sizes)

For 5 books over 3 stacks, call this with:

bookStack(0,1,5,[0]*3)

Run it here

Remark: Although you want all unique combinations, this still is a fast growing function and will only work for a small number of stacks. Or when the number of stacks is almost equal with the number of books. You will notice.