Re: generating submultisets with repeated elements
- To: mathgroup at smc.vnet.net
- Subject: [mg103799] Re: generating submultisets with repeated elements
- From: Ray Koopman <koopman at sfu.ca>
- Date: Tue, 6 Oct 2009 08:02:38 -0400 (EDT)
- References: <hadc3d$bjo$1@smc.vnet.net>
Here's some "roll your own nested loops" code. It's faster than the "accumulator" approach. subsets[n_,1] := Transpose@{Range@n}; subsets[n_,k_] := ToExpression["Flatten[Table["<> StringTake[ToString@Table[Which[ j==0, "i"<>ToString@#& /@ Range@k, j==1, {"i1",n}, True, {"i"<>ToString@j,"i"<>ToString[j-1],n}], {j,0,k}],{2,-2}]<>"],"<>ToString[k-1]<>"]"] coinsets[s_,k_] := s[[#]]& /@ Join@@(subsets[Length@s,#]&/@Range@k) coinSets[s_,k_] := Flatten[Table[subMultiSets[s,i],{i,k}],1]; subMultiSets[s_,k_] := smsLoop[{},s,k]; smsLoop[{ts___},{x_},1] := {{ts,x}}; smsLoop[t:{ts___},{x_,xs___},1] := Prepend[smsLoop[t,{xs},1],{ts,x}]; smsLoop[{ts___},s:{x_},k_] := smsLoop[{ts,x},s,k-1]; smsLoop[t:{ts___},s:{x_,xs___},k_] := Join[smsLoop[{ts,x},s,k-1], smsLoop[t,{xs},k]] coinsets[{1,3,4,9},3] % == coinSets[{1,3,4,9},3] {{1},{3},{4},{9},{1,1},{1,3},{1,4},{1,9},{3,3},{3,4},{3,9},{4,4}, {4,9},{9,9},{1,1,1},{1,1,3},{1,1,4},{1,1,9},{1,3,3},{1,3,4},{1,3,9}, {1,4,4},{1,4,9},{1,9,9},{3,3,3},{3,3,4},{3,3,9},{3,4,4},{3,4,9}, {3,9,9},{4,4,4},{4,4,9},{4,9,9},{9,9,9}} True Timing@Length@coinsets[Range@20,7] {6.69 Second,888029} Timing@Length@coinSets[Range@20,7] {11.03 Second,888029} On Oct 5, 10:58 am, David Bevan <david.be... at pb.com> wrote: > Dan, Adriano, Kurt, > > Thanks for the feedback. > > Here are some performance results: > > (* Dan *) > > Length[multiSetsUpToK[Range[20],7]]//Timing > > {18.14,888029} > > (* Adriano *) > > Length[coinSetsAdriano[Range[20],7]]//Timing > > {9.516,888029} > > (* Kurt *) > > Length[coinSetsKurt[Range[20],7]]//Timing > > Subsets::toomany: The number of subsets (189407486533) indicated by Subsets= > [{1,1,1,1,1,1,1,2,2,2,<<130>>},{1,7}] is too large; it must be a machine in= > teger. > > And with my code: > > Length[coinSets[Range[20],7]]//Timing > > {5.063,888029} > > My 'accumulator' approach seems to be quite effective! > > However, I'm sure this can be improved significantly with the technique use= > d for KSubsets without too much difficulty. > > David %^>
- Follow-Ups:
- Re: Re: Re: generating submultisets with
- From: DrMajorBob <btreat1@austin.rr.com>
- Re: generating submultisets with repeated elements
- From: Ray Koopman <koopman@sfu.ca>
- Re: Re: Re: generating submultisets with
- From: Leonid Shifrin <lshifr@gmail.com>
- Re: Re: generating submultisets with repeated elements
- From: David Bevan <david.bevan@pb.com>
- Re: Re: generating submultisets with repeated elements
- From: "Kurt TeKolste" <tekolste@fastmail.us>
- Re: Re: Re: generating submultisets with