3

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

Sam Segers
  • 1,951
  • 2
  • 22
  • 28
Alexander Grass
  • 384
  • 2
  • 11

1 Answers1

3

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.

Community
  • 1
  • 1
Sam Segers
  • 1,951
  • 2
  • 22
  • 28
  • You may not have noticed, but you can accept this answer. [Accepting](http://meta.stackexchange.com/questions/5234/how-does-accepting-an-answer-work) an answer is important as it both rewards posters for solving your problem and informs others that your issue is resolved. – Sam Segers Jan 17 '16 at 20:30
  • It works perfectly. Still, I'm struggling with getting the idea of it. I'm always getting lost in the recursion when thinking through. Would you please be so kind as to explain the steps a little more? For example what do you mean by "each step you now the possible size of the stack is at least the size of the previous" ? Despite my lazy mind, i think it's great work you did there, thanks mate ! Regarding the accepting of the post: That's what i did now, thanks for the hint ! – Alexander Grass Jan 17 '16 at 20:32
  • 1
    You know our sequence is increasing, so the current element has to be at least the same size of the previous handled stack. And let's say we have `P` stacks to fill left with `N` books. As I explained `N/P` is our max. If you would take `(N/P)+1`, with `P` stacks left. The total number of books left should be `((N/P)+1) * P` which is strictly greater than `N` - the number of books left. I suggest you try to debug this code, for example by printing `cur`, `min` and `max` out. – Sam Segers Jan 17 '16 at 20:46
  • @AlexanderGrass & SamSegers Please don't pressure the OP into accepting an answer when only one answer has been posted yet, and only 5 hours have passed since the question was asked. – m69's been on strike for years Jan 18 '16 at 02:12
  • @m69 You are probably right. But it actually was a reaction to the author just saying "thank you, that's it." Which was removed later. Considering the rep of the author I don't feel this is appropriate. – Sam Segers Jan 18 '16 at 05:19
  • Indeed, drive-by questions from new users can be frustrating; we've all been there. No harm done. – m69's been on strike for years Jan 18 '16 at 06:01
  • Sorry for that my friend. But just saying, you helped a lot Sir. Thank you very much ! :) – Alexander Grass Mar 23 '16 at 18:45