Re: Re: Re: generating submultisets with

*To*: mathgroup at smc.vnet.net*Subject*: [mg103836] Re: [mg103814] Re: [mg103799] Re: generating submultisets with*From*: Leonid Shifrin <lshifr at gmail.com>*Date*: Thu, 8 Oct 2009 07:52:30 -0400 (EDT)*References*: <hadc3d$bjo$1@smc.vnet.net> <200910061202.IAA19756@smc.vnet.net>

Kurt, I disagree. If a solution based on efficient Mathematica built-ins turns out to be inefficient, this usually means either that some underlying data structures are used improperly (say, arrays instead of linked lists like with Append etc in loops), or that the algorithm does a lot of unnecessary moves or creates vastly more objects than needed and then utilizes only a small subset of them. My experience is that for many efficient algorithms it may take considerable effort to translate them to Mathematica in a way which takes the maximal performance advantage of idiomatic Mathematica programming. Conversely, I feel that the programming based exclusively on operations which deal with entire lists often provokes one to create succinct but inefficient solutions, whose inefficiency for smaller lists is often hidden by the efficiency of underlying built-ins used. For many such cases, Compile (and associated with it shift towards a more procedural programming style) seems to offer a good alternative - this is where I agree with you. Perhaps also, Mathematica might benefit from efficient built-in linked lists in addition to standard Mathematica lists (implemented as arrays, as we know). But at the end, large problems just test the true complexity of the algorithm, so a dramatic difference in efficiency (especially if it scales with the size of the problem) of two implementations would mean to me that the real algorithms implemented are just different algorithms with different complexities. This has nothing to do directly with the efficiency of Mathematica built-ins in terms of time, memory, or both - it is up to us to use them in a proper way. Regards, Leonid On Wed, Oct 7, 2009 at 3:03 PM, Kurt TeKolste <tekolste at fastmail.us> wrote: > It would seem that the emphasis in the Mathematica literature on using > the allegedly highly efficient functions available in Mathematica might > be a bit overstated. Limitations of memory and time seem to require > falling back to something more akin to the classical procedural > programming style when the problem gets large. > > On Tue, 06 Oct 2009 08:02 -0400, "Ray Koopman" <koopman at sfu.ca> wrote: > > 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 %^> > > > Regards, > Kurt Tekolste > > >

**References**:**Re: generating submultisets with repeated elements***From:*Ray Koopman <koopman@sfu.ca>