       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:= Needs["DiscreteMath`Combinatorica`"]

In:= ?Partitions
Partitions[n] constructs all partitions of integer n in reverse lexicographic
order.

In:= Partitions

Out= {{5}, {4, 1}, {3, 2}, {3, 1, 1}, {2, 2, 1}, {2, 1, 1, 1},

>    {1, 1, 1, 1, 1}}

In:= ?PartitionsP
PartitionsP[n] gives the number p(n) of unrestricted partitions of the
integer n.

In:= ?PartitionsQ
PartitionsQ[n] gives the number q(n) of partitions of the integer n into
distinct parts.

In:= PartitionsP

Out= 7

PartitionsP is the same as Length[Partitions].

You specified that you want distinct partitions.

In:= PartitionsQ

Out= 3

Use a pure function to select the distinct partitions from the complete list.

In:= Select[Partitions,Length[#]==Length[Union[#]]&]

Out= {{5}, {4, 1}, {3, 2}}

If you also don't want the integer itself (a trivial partition), use the
following command.

In:= Select[Partitions,Length[#]==Length[Union[#]] && Length[#]>1 &]

Out= {{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