Author |
Topic: Partitioning an integer (Read 820 times) |
|
jpk2009
Junior Member
Gender: 
Posts: 60
|
 |
Partitioning an integer
« on: Sep 26th, 2009, 3:27pm » |
 Quote  Modify
|
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.
|
| « Last Edit: Sep 26th, 2009, 3:29pm by jpk2009 » |
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: Partitioning an integer
« Reply #1 on: Sep 27th, 2009, 7:56am » |
Quote Modify
|
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;
|
| « Last Edit: Sep 27th, 2009, 8:00am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: Partitioning an integer
« Reply #2 on: Sep 27th, 2009, 8:48am » |
Quote Modify
|
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 1
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.
|
|
IP Logged |
|
|
|
jpk2009
Junior Member
Gender:
Posts: 60
|
|
Re: Partitioning an integer
« Reply #3 on: Sep 27th, 2009, 10:52am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Partitioning an integer
« Reply #4 on: Sep 27th, 2009, 11:08am » |
Quote Modify
|
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();
}
} |
|
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
jpk2009
Junior Member
Gender:
Posts: 60
|
|
Re: Partitioning an integer
« Reply #5 on: Sep 27th, 2009, 2:52pm » |
Quote Modify
|
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().
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Partitioning an integer
« Reply #6 on: Sep 28th, 2009, 1:35am » |
Quote Modify
|
on Sep 27th, 2009, 2:52pm, 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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print