Re: Re: Help! How to calculate additive partitions?
- To: mathgroup at smc.vnet.net
- Subject: [mg34440] Re: Re: [mg34432] Help! How to calculate additive partitions?
- From: BobHanlon at aol.com
- Date: Mon, 20 May 2002 04:21:34 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
A much faster way came to mind:
Needs["DiscreteMath`Combinatorica`"];
myPartitions[n_Integer?Positive] :=
Flatten[Permutations /@ Partitions[n],1]
n=5;
myPartitions1[n]
{{5}, {1, 4}, {2, 3}, {3, 2}, {4, 1}, {1, 1, 3}, {1, 2, 2},
{1, 3, 1}, {2, 1, 2}, {2, 2, 1}, {3, 1, 1}, {1, 1, 1, 2},
{1, 1, 2, 1}, {1, 2, 1, 1}, {2, 1, 1, 1}, {1, 1, 1, 1, 1}}
Length[%]==2^(n-1)
True
In a message dated 5/19/02 12:01:55 PM, writes:
>In a message dated 5/19/02 5:08:45 AM, Tom.Brodhead at worldnet.att.net writes:
>
>>I need to find a formula or method that will allow me to calculate the
>>additive partitions of a given number.
>>
>>E.g., 3 can be expressed as
>>
>>1+1+1
>>2+1
>>1+2
>>3
>>
>>IMPORTANT: Even though 2+1 and 1+2 employ the same values, the order is
>>important and thus the procedure or formula that I need would need to
>>produce both of those results.
>>
>>Likewise, 4 would break down this way:
>>1+1+1+1
>>2+1+1
>>1+2+1
>>1+1+2
>>2+2
>>3+1
>>1+3
>>4
>>
>>I need to calculate both the number of results that I should get, and
>the
>>results themselves.
>>
>>How can this be done?
>>
>
>Needs["DiscreteMath`Combinatorica`"];
>
>
>A brute force approach which gets quite slow for large n:
>
>
>myPartitions[n_Integer?Positive] :=
>
> Union[Flatten[Table[Compositions[n,k],{k,n}],1] //.
>
> {x___,0,y___}:> {x,y}];
>
>
>myPartitions[3]
>
>
>{{3}, {1, 2}, {2, 1}, {1, 1, 1}}
>
>
>myPartitions[4]
>
>
>{{4}, {1, 3}, {2, 2}, {3, 1}, {1, 1, 2}, {1, 2, 1}, {2, 1, 1}, {1, 1, 1,
>1}}
>
>
>The number of results for myPartitions[n] is just 2^(n-1)
>
>
>Table[{n,l=Length[myPartitions[n]], l==2^(n-1)}, {n,7}]
>
>
>{{1, 1, True}, {2, 2, True}, {3, 4, True}, {4, 8, True},
> {5, 16, True}, {6, 32, True}, {7, 64, True}}
>
>
>numberOfMyPartitions[n_Integer?Positive] := 2^(n-1);
>
Bob Hanlon
Chantilly, VA USA