Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: Re: [mg4694] Integer Partitioning
Replies: 0

 Robert Pratt Posts: 56 Registered: 12/7/04
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 27599-3250

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