Integer partition

[tytus]

Not_yet_rated Poor (Spam) Poor (Spam) Below average Below average Average Average Good Good Very good Very good Excellent

To rate posts you must be logged in

#1

Integer partition

[fedja]

Not_yet_rated Poor (Spam) Poor (Spam) Below average Below average Average Average Good Good Very good Very good Excellent

To rate posts you must be logged in

#2

This can be done fairly easily if you know the numbers P(m,n) of all partitions
of m into n components. If you know all such numbers, then to determine the
first component of the N-th partition, compare N to P(m-1,n-1). If N does not exceed P(m-1,n-1), then the first component is 1. If N is greater than P(m-1,n-1), then you are looking at partitions of m into n components starting with 2 or higher. The number of partitions of m into n components starting with 2 is the same as the number of partitions of m-n into n components starting with 1 (subtract 1 from each component), that is P(m-n-1,n-1). Thus, the first component is 2 if P(m-1,n-1)<N<=P(m-1,n-1)+P(m-n-1,n-1). Similarly, it is 3 if
P(m-1,n-1)+P(m-n-1,n-1)<N<=P(m-1,n-1)+P(m-n-1,n-1)+P(m-2n-1,n-1) and so on.
Once you have determined that the first component is k, you reduced the problem to finding the N'=N-P(m-1,n-1)-...-P(m-(k-2)n-1,n-1)-th partition of m-k into n-1 components with the smallest component of size at least k. Subtracting k-1 from
each component, you see that it is equivalent to the problem of finding the N'-th
partition of m-k-(n-1)(k-1) into n-1 components.

This is still quite a work but it is easily doable on any decent computer. This leaves unanswered just one question: how to find P(m,n) fast? For n=1 and n=2 the answer is obvious: P(m,1)=1 (m>=1); P(m,2)=[m/2] ([x] stands for the integer part of x). Also P(m,n)=0 if m<n and P(n,n)=1.

The other values can be found from the relation P(m,n)=P(m-1,n-1)+P(m-n,n). This will force you to fill out a 220 by 10 table first to do your particular example but, again, any decent computer will manage 2200 numbers without a big problem. Hope this helps.

fedja

[tytus]

Not_yet_rated Poor (Spam) Poor (Spam) Below average Below average Average Average Good Good Very good Very good Excellent

To rate posts you must be logged in

#3

Everything seems to be OK, but I can't understand how can I count N'... When m=9, n=4 and k=3 (in your algorithm it's N), P(8,3)=5 and k (the first element) is equal to 1, so N'=N-P(m-1,n-1)=3-5=-2... What should I do then?? Maybe I'm just doing something wrong...

Can You explain me how to count N', please....

[fedja]

Not_yet_rated Poor (Spam) Poor (Spam) Below average Below average Average Average Good Good Very good Very good Excellent

To rate posts you must be logged in

#4

The sum one should subtract from to
find is a bit confusing thing for small : for it is empty: if you write it in the sigma notation, you will have
and for the range of summation will be
, i.e., empty.

So, for , we have , for (not for !), we have , for and higher the sum makes perfect sense as written.
Sorry for not writing it clearly the first time.

[tytus]

Not_yet_rated Poor (Spam) Poor (Spam) Below average Below average Average Average Good Good Very good Very good Excellent

To rate posts you must be logged in

#5

Ok - I understand that. But now I have another question:

When I find first element k of n-elements partition of integer m, then I'm looking for second one, but before doing it I have do decrement m by k (m=m-k) and decrement n by 1 (n=n-1). You wrote that next element has to be larger or equal than previous one, so what I should check?? I mean in first iteration I have to check if N<=P(m-1,n-1), if not then P(m-1,n-1)<N<=P(m-1,n-1)P(m-n-1,n-1) and so on... But in each next when k has to be larger or equal then previous one what condition I should start with?? When I'm starting always with the same condition (N<=P(m-1,n-1)) I don't know what k to take as "solution" in iteration, and usualy I get wrong answer.

[fedja]

Not_yet_rated Poor (Spam) Poor (Spam) Below average Below average Average Average Good Good Very good Very good Excellent

To rate posts you must be logged in

#6

I'll start with repeating what I wrote originally (just to make sure you paid attention to that part)

Once you have determined that the first component is k, you reduced the problem to finding the N'=N-P(m-1,n-1)-...-P(m-(k-2)n-1,n-1)-th partition of m-k into n-1 components with the smallest component of size at least k. Subtracting k-1 from
each component, you see that it is equivalent to the problem of finding the N'-th
partition of m-k-(n-1)(k-1) into n-1 components.

In the algorithm it means that you do things recursively: once you determined the first component k, you call your algorithm with parameters m-k-(n-1)(k-1),n-1, N' in place of m,n,N and then add k-1 to every element of the resulting partition to get the correct tail.

Let's run an example with m=12, n=3, N=8.
Since P(11,2)=5, P(8,2)=4, we see that k=2, N'=3
Now we would like to search the 3-d partition among the partitions
of 12-2=10 into 2 components starting with 2 or a higher number.
So, actually, we are interested in partitions 2+8 ; 3+7; 4+6; 5+5, the third one being the one we need. The trick is to think of them as of arbitrary partitions of 8 into 2 parts to which 1 is added in each component.
So, instead of 2+8=10, you think of 1+7=8, instead of 3+7=10, you think of 2+6=8 and so on. Finding the third partition of 8 among all partitions into 2 components gives you 3+5. You add 1 back and get the tail 4+6 and the final answer 2+4+6.

[tytus]

Not_yet_rated Poor (Spam) Poor (Spam) Below average Below average Average Average Good Good Very good Very good Excellent

To rate posts you must be logged in

#7

Thank You very much - I've made it - now everything is OK...