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] ====