Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.



Re: [mg4694] Integer Partitioning
Posted:
Aug 31, 1996 2:48 AM


Use the standard package Combinatorica.
In[1]:= Needs["DiscreteMath`Combinatorica`"]
In[2]:= ?Partitions Partitions[n] constructs all partitions of integer n in reverse lexicographic order.
In[2]:= Partitions[5]
Out[2]= {{5}, {4, 1}, {3, 2}, {3, 1, 1}, {2, 2, 1}, {2, 1, 1, 1}, > {1, 1, 1, 1, 1}}
In[3]:= ?PartitionsP PartitionsP[n] gives the number p(n) of unrestricted partitions of the integer n.
In[3]:= ?PartitionsQ PartitionsQ[n] gives the number q(n) of partitions of the integer n into distinct parts.
In[3]:= PartitionsP[5]
Out[3]= 7
PartitionsP[5] is the same as Length[Partitions[5]].
You specified that you want distinct partitions.
In[4]:= PartitionsQ[5]
Out[4]= 3
Use a pure function to select the distinct partitions from the complete list.
In[5]:= Select[Partitions[5],Length[#]==Length[Union[#]]&]
Out[5]= {{5}, {4, 1}, {3, 2}}
If you also don't want the integer itself (a trivial partition), use the following command.
In[6]:= Select[Partitions[5],Length[#]==Length[Union[#]] && Length[#]>1 &]
Out[6]= {{4, 1}, {3, 2}}
If you're going to partition large integers, you may want to write your own DistinctPartitions command. PartitionsQ climbs MUCH faster than PartitionsP as n goes to infinity.
Rob Pratt Department of Mathematics The University of North Carolina at Chapel Hill CB# 3250, 331 Phillips Hall Chapel Hill, NC 275993250
rpratt@math.unc.edu
On Sun, 25 Aug 1996, Kenneth J. Mascola wrote:
> Any references relating to the following memo would be greatly > appreciated. > I am also investigating ( as mentioned in the last section of my > previous message ) into the possibility of a > mathematical model involving the partitioning of integers ( # > Partitions would range from 1 to 400,000 and > values of the integers in the sets would range from 1 to 1 > million ) into p(n) distinct summands. I am attempting > trying to store MANY distinct integers inside 1 or very few > integer values. > eg. using small numbers > > Integer Value Distinct partitions(excluding 0) > 5 1 + 4 & 2 + 3 > 6 1 + 5 & 2 + 4 > 7 1 + 6 & 2 + 5 & 3 > + 4 > .... > 25 1 + 24 & 3 + 4 + 7 + 11 > etc..... > > Please email any responses to 76504.2375@Compuserve.com > > Regards > >



