Services & ResourcesWolfram ForumsMathGroup Archive

[Date Index] [Thread Index] [Author Index]

Re: compositions with the restricted set of integers

• To: mathgroup at smc.vnet.net
• Subject: [mg105177] Re: [mg105143] compositions with the restricted set of integers
• From: Leonid Shifrin <lshifr at gmail.com>
• Date: Mon, 23 Nov 2009 06:53:22 -0500 (EST)
• References: <200911221110.GAA10476@smc.vnet.net>

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}]]];


For example:

In[2]: =
outsNew[53, 25] // Timing

Out[2] =

{0.05, 247679998965100}


Regards,
Leonid



On Sun, Nov 22, 2009 at 3:10 AM, michael partensky <partensky at gmail.com>wrote:

>  IntegerPartitions has a useful option restricting the values of
> partitions.
> For example, IntegerPartitions[6,2,{1,2,3,4,5,6}] . Does it exist for
> Compositions?
>
> What I am looking for is a substitute for  a lengthy and inefficient
> approach described below. We through n dice.  How many outcomes
> *outs*correspond to the face total equal
> *sum*?
> I am aware about the recursive approach, but prefer to describe it in terms
> of integer partitioning (or compositions).
> *Here is my intellectually insulting solution:*
>
> outs[sum_, thr_] :=
>  Length[Flatten[
>    Permutations /@
>     Cases[IntegerPartitions[sum, thr, {1, 2, 3, 4, 5, 6}],
>      Table[_, {thr}]], 1]];
>
> Mapping with  permutations seems especially silly.
> Is there a version of Compositions with the similar restrictive option ({1,
> 2, 3, 4, 5, 6})?
> I would appreciate any other suggestions as well.
>
> Thanks
> Michael
>
>
>

• References:
  • compositions with the restricted set of integers
    • From: michael partensky <partensky@gmail.com>