MathGroup Archive 2009

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

Search the Archive

generating submultisets with repeated elements

  • To: mathgroup at smc.vnet.net
  • Subject: [mg103678] generating submultisets with repeated elements
  • From: David Bevan <david.bevan at pb.com>
  • Date: Fri, 2 Oct 2009 08:23:25 -0400 (EDT)

I'm new to Mathematica, so if I've missed something obvious, my apologies.

I want a function to generate a list of "submultisets" with up to k elements of a set s, allowing elements from s to be repeated.

The following works, but is very inefficient since each multiset is generated multiple times and then sorted and then repeats deleted:


coinSets[s_,k_]:=DeleteDuplicates[Sort/@Flatten[Tuples[s,#]&/@Range[k],1]]



coinSets[{1,3,4},3]



{{1},{3},{4},{1,1},{1,3},{1,4},{3,3},{3,4},{4,4},{1,1,1},{1,1,3},{1,1,4},{1,3,3},{1,3,4},{1,4,4},{3,3,3},{3,3,4},{3,4,4},{4,4,4}}



I assumed there would be a suitable function in the Combinatorica package, but I can't see anything -- which would be a bit odd for a combinatorial package. What have I missed?



Do I need to write my own (perhaps by looking at how KSubsets is implemented) or is there some easy way of generating these multisets?



Thanks.



David %^>




  • Prev by Date: Re: DateListPlot & Locator
  • Next by Date: Re: DateListPlot & Locator
  • Previous by thread: Re: How to =B1?
  • Next by thread: Re: generating submultisets with repeated elements