       Re: generating submultisets with repeated elements

• To: mathgroup at smc.vnet.net
• Subject: [mg103681] Re: generating submultisets with repeated elements
• From: David Bevan <david.bevan at pb.com>
• Date: Fri, 2 Oct 2009 08:23:57 -0400 (EDT)
• References: <DE9DE45304B6FA4EBE8252CD4EBDA2418286B95F41@PBI-NAMSG-02.MGDPBI.global.pvt>

```I've now tried the following, which avoids generating the extra multisets:

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

Any suggestions for a better approach?

David %^>

________________________________
From: David Bevan
Sent: 01 October 2009 18:57
To: mathgroup at smc.vnet.net
Subject: [mg103681] generating submultisets with repeated elements

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: White Noise in Simulation
• Next by Date: Re: How to store data files in packages
• Previous by thread: generating submultisets with repeated elements
• Next by thread: Re: Re: generating submultisets with repeated elements