MathGroup Archive 1996

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: Integer Partitioning

  • To: mathgroup at smc.vnet.net
  • Subject: [mg4707] Re: [mg4694] Integer Partitioning
  • From: Robert Pratt <rpratt at math.unc.edu>
  • Date: Sat, 31 Aug 1996 03:57:28 -0400
  • Sender: owner-wri-mathgroup at wolfram.com

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  27599-3250

rpratt at 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 e-mail any responses to 76504.2375 at Compuserve.com
> 
> Regards
> 
> 

==== [MESSAGE SEPARATOR] ====


  • Prev by Date: problem with NonlinearFit
  • Next by Date: Re: How to read a Bitmap file?
  • Previous by thread: Re: Integer Partitioning
  • Next by thread: new cellular automata book