Services & ResourcesWolfram ForumsMathGroup Archive

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

Re: Re: Re: Re: generating

• To: mathgroup at smc.vnet.net
• Subject: [mg103883] Re: [mg103861] Re: [mg103827] Re: [mg103806] Re: generating
• From: Leonid Shifrin <lshifr at gmail.com>
• Date: Sat, 10 Oct 2009 07:10:29 -0400 (EDT)
• References: <ha4r9k$d0h$1@smc.vnet.net> <200910071101.HAA00387@smc.vnet.net>

I've made a few more optimizations:

Clear[subMultiSetsNew];
subMultiSetsNew[s_, k_] :=
  Partition[s[[Flatten[#]]], k] &@
   Transpose[
    Transpose[Subsets[Range[Length[s] + k - 1], {k}]] -
     Range[0, k - 1]];

Clear[coinSetsNew];
coinSetsNew[s_, k_] :=
  Flatten[Table[subMultiSetsNew[s, i], {i, k}], 1];

Now (coinSets is  David's "accumulator" version):

In[1]:= (res1=coinSets[Range[15],7])//Length//Timing

Out[1]= {2.333,170543}

In[2]:= (res2 = coinSetsNew[Range[15],7])//Length//Timing
Out[2]= {0.37,170543}

In[3]:= res1==res2

Out[3]= True

Regards,
Leonid







On Fri, Oct 9, 2009 at 4:18 AM, David Bevan <david.bevan at pb.com> wrote:

>
> ... and using Subsets[set, {k}] is much faster than KSubsets[set, k]
>
>
> > -----Original Message-----
> > From: DrMajorBob [mailto:btreat1 at austin.rr.com]
> > Sent: 8 October 2009 17:05
> > To: David Bevan; mathgroup at smc.vnet.net
> > Cc: bayard.webb at gmail.com
> > Subject: Re: [mg103827] Re: [mg103806] Re: generating submultisets with
> > repeated elements
> >
> > g is an improvement over f, I think:
> >
> > << "Combinatorica`";
> >
> > Clear[f, g, test1, test2]
> > f[set_] := Table[set[[i]] - (i - 1), {i, Length[set]}]
> > g[set_] := set - Range[0, Length@set - 1]
> > test1[n_, k_] := With[{set = Range[n + k - 1]},
> >    f /@ KSubsets[set, k]]
> > test2[n_, k_] := With[{set = Range[n + k - 1]},
> >    g /@ KSubsets[set, k]]
> >
> > n = 15; k = 10;
> > Timing@Length@test1[n, k]
> > Timing@Length@test2[n, k]
> > Binomial[n + k - 1, k]
> >
> > {32.9105, 1961256}
> >
> > {16.3832, 1961256}
> >
> > 1961256
> >
> > Bobby
> >
> > On Thu, 08 Oct 2009 06:50:51 -0500, David Bevan <david.bevan at pb.com>
> > wrote:
> >
> > > That's an interesting bijection I wasn't aware of. Thanks.
> > >
> > > David %^>
> > >
> > >> -----Original Message-----
> > >> From: monochrome [mailto:bayard.webb at gmail.com]
> > >> Sent: 7 October 2009 12:02
> > >> To: mathgroup at smc.vnet.net
> > >> Subject: [mg103806] Re: generating submultisets with repeated elements
> > >>
> > >> I did a little research and found out that there are Choose(n+k-1, k)
> > >> multisets of size k from a set of size n. This made me think that
> > >> there should be a mapping from the k-subsets of n+k-1 to the k-
> > >> multisets of n. A few quick examples led me to the following function:
> > >>
> > >> f[set_] := Table[set[[i]] - (i - 1), {i, Length[set]}]
> > >>
> > >> This allows the following construction using the KSubsets function
> > >> from Combinatorica:
> > >>
> > >> << "Combinatorica`";
> > >> n = 6;
> > >> k = 3;
> > >> set = Range[n + k - 1];
> > >> Map[f, KSubsets[set, k]]
> > >>
> > >> ===OUTPUT===
> > >> {{1, 1, 1}, {1, 1, 2}, {1, 1, 3}, {1, 1, 4}, {1, 1, 5}, {1, 1, 6}, {1,
> > >>    2, 2}, {1, 2, 3}, {1, 2, 4}, {1, 2, 5}, {1, 2, 6}, {1, 3, 3}, {1,
> > >>   3, 4}, {1, 3, 5}, {1, 3, 6}, {1, 4, 4}, {1, 4, 5}, {1, 4, 6}, {1, 5,
> > >>    5}, {1, 5, 6}, {1, 6, 6}, {2, 2, 2}, {2, 2, 3}, {2, 2, 4}, {2, 2,
> > >>   5}, {2, 2, 6}, {2, 3, 3}, {2, 3, 4}, {2, 3, 5}, {2, 3, 6}, {2, 4,
> > >>   4}, {2, 4, 5}, {2, 4, 6}, {2, 5, 5}, {2, 5, 6}, {2, 6, 6}, {3, 3,
> > >>   3}, {3, 3, 4}, {3, 3, 5}, {3, 3, 6}, {3, 4, 4}, {3, 4, 5}, {3, 4,
> > >>   6}, {3, 5, 5}, {3, 5, 6}, {3, 6, 6}, {4, 4, 4}, {4, 4, 5}, {4, 4,
> > >>   6}, {4, 5, 5}, {4, 5, 6}, {4, 6, 6}, {5, 5, 5}, {5, 5, 6}, {5, 6,
> > >>   6}, {6, 6, 6}}
> > >>
> > >
> >
> >
> > --
> > DrMajorBob at yahoo.com
>
>
>

• References:
  • Re: generating submultisets with repeated elements
    • From: monochrome <bayard.webb@gmail.com>