wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> general problem-solving / chatting / whatever >> Partitioning an integer
        
(Message started by: jpk2009 on Sep 26^th, 2009, 3:27pm)

Title: Partitioning an integer
Post by jpk2009 on Sep 26^th, 2009, 3:27pm

I want to be able to find all partitions of the integer 70 into 4 parts, including zero. Any suggestions? Also, I wonder if there is a general way to partition an integer m into n parts?

Also, I don't want any permutation of a same partition.

Thanks.

Title: Re: Partitioning an integer
Post by towr on Sep 27^th, 2009, 7:56am

For (a=0; a <= 70/4; a++)
For (b=a; b <= (70-a)/3; b++)
For (c=b; c <= (70-a-b)/2; c++)
d = 70-a-b-c
if(d >= c)
print a,b,c,d;

Title: Re: Partitioning an integer
Post by rmsgrey on Sep 27^th, 2009, 8:48am

If you're prepared to count permutations as different (so {0,0,0,70} as different from {0,0,70,0}) then it's easy enough - it's equivalent to dropping 3 dividers into a row of 70 objects, giving (70+3)!/(70!*3!)=62196 ways of partitioning. Obviously, that's a significant overcount if you don't want to distinguish permutations - a given partition gets counted up to 24 times - giving a lower bound of 2591.5

As for getting an exact count, I'm not seeing a simple way - you could try working out the numbers of partitions of form {a,a,b,c}, {a,a,b,b} (36 or 18 depending on whether you count both {0,0,35,35} and {35,35,0,0} or not) and {a,a,a,b} (24 - a ranges from 0 to 23) and compensating accordingly.

For counting {a,a,b,c}, a ranges from 0 to 35, b from 0 to 35-a (and c from 35-a to 70-2a) giving 666 (36th triangular number) such partitions, 36 of which have b=c, giving 630 such partitions with b<c

So, of the original 62196 partitions, we have:

96 of form {a,a,a,b} (4 permutations of 24)
108 of form {a,a,b,b} (6 permutations of 18)
7560 of form {a,a,b,c} (12 permutations of 630)
54432 of form {a,b,c,d} (62196 - (7560+108+96))

for a grand total of 54432/24 + 630 + 18 + 24 = 2940 partitions.

As for actually listing them, at a slow 5 seconds per partition, it would take about 4 hours to write out the list by hand - or about 50 minutes at a fast 1 per second. Doing it by computer shouldn't take long. Pseudo-code:

For (a=0;a++;a<=70/4)
{ For (b=a;b++;b<=(70-a)/3)
{ For (c=b;c++;c<=(70-a-b)/2)
{ Print a,b,c,(70-a-b-c)
}
}
}

Adapting the code for general integer m and/or for a specific number of parts, n, should be obvious. Adapting for general n is more interesting, but perfectly practical.

Title: Re: Partitioning an integer
Post by jpk2009 on Sep 27^th, 2009, 10:52am

Thanks a lot. That's simple enough for 70 in 4 parts. I guess that would serve as a basis for contriving the same thing for integer m into n parts.

Title: Re: Partitioning an integer
Post by towr on Sep 27^th, 2009, 11:08am

In general, I think you can use something like

Pseudo
Code:

function foo(int m, int n, stack st)
{
if ( n < 1 )
throw HissyFit; // or whichever exception you prefer

if (n=1)
print m, st;
else
for(i = (st.empty() ? 0 : st.top()) ; i <= m/n; i++)
{
st.push(i);
fun(m-i, n-1, st);
st.pop();
}
}

Title: Re: Partitioning an integer
Post by jpk2009 on Sep 27^th, 2009, 2:52pm

Thanks. I don't quite understand what "st.empty() ? 0 : st.top()" means but I'll look it up. Maybe it means if st.empty() = 0 then put i=st.top().

Title: Re: Partitioning an integer
Post by towr on Sep 28^th, 2009, 1:35am

on 09/27/09 at 14:52:33, jpk2009 wrote:

Thanks. I don't quite understand what "st.empty() ? 0 : st.top()" means but I'll look it up. Maybe it means if st.empty() = 0 then put i=st.top().

Almost. X ? Y : Z means if X then Y else Z. So I check whether the stack is empty and if it is, then i gets the the value 0, otherwise it gets the top value from the stack.