Re: compositions with the restricted set of integers
- To: mathgroup at smc.vnet.net
- Subject: [mg105213] Re: compositions with the restricted set of integers
- From: Bill Rowe <readnews at sbcglobal.net>
- Date: Tue, 24 Nov 2009 05:50:58 -0500 (EST)
On 11/23/09 at 6:53 AM, lshifr at gmail.com (Leonid Shifrin) wrote:
>Hi, Michael.
>Your solution is indeed very memory - hungry due to the mapping of
>Permutations, as you mentioned. The total number of permutations can
>be easily deduced from the list of multiplicities of elements in a
>given partition: n!/(n1!n2!...nk!), where n1, ..., nk are
>multiplicities of elements, and n is the length of the partition:
>n=n1+...+nk. The multiplicities can be obtained by Tally. The
>following modification can be realistically used in a much wider
>region of the problem's parameter space than your original one, and
>may possibly serve your needs.
>In[1]:=
>Clear[outsNew];
>outsNew[sum_, thr_] :=
>Total[Factorial[Length[#]]/
>Times @@ Factorial[Tally[#][[All, 2]]] & /@
>Cases[IntegerPartitions[sum, thr, {1, 2, 3, 4, 5, 6}],
>Table[_, {thr}]]];
The above can be made more efficient by using the form of
IntegerPartitions that only generates partitions of a given
length. That is
outs[sum_, thr_] :=
Total[Factorial[Length[#]]/
Times @@ Factorial[Tally[#][[All, 2]]] & /@
IntegerPartitions[sum, {thr}, {1, 2, 3, 4, 5, 6}]]
does the same thing a bit more efficiently