Re: generating submultisets with repeated elements

*To*: mathgroup at smc.vnet.net*Subject*: [mg103806] Re: generating submultisets with repeated elements*From*: monochrome <bayard.webb at gmail.com>*Date*: Wed, 7 Oct 2009 07:01:40 -0400 (EDT)*References*: <ha4r9k$d0h$1@smc.vnet.net>

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}} On Oct 2, 5:22 am, David Bevan <david.be... at pb.com> wrote: > 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 %^>

**Follow-Ups**:**Re: generating submultisets with repeated elements***From:*DrMajorBob <btreat1@austin.rr.com>

**Re: generating submultisets with repeated elements***From:*"Kurt TeKolste" <tekolste@fastmail.us>

**Re: Re: Re: Re: Re:***From:*DrMajorBob <btreat1@austin.rr.com>

**Re: Re: Re: Re: Re:***From:*Leonid Shifrin <lshifr@gmail.com>

**Re: Re: Re: Re: Re:***From:*DrMajorBob <btreat1@austin.rr.com>

**Re: Re: generating submultisets with repeated elements***From:*David Bevan <david.bevan@pb.com>

**Re: Re: Re: generating submultisets with***From:*DrMajorBob <btreat1@austin.rr.com>

**Re: Re: Re: Re: generating***From:*Leonid Shifrin <lshifr@gmail.com>

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

**Re: Re: Re: generating submultisets with***From:*David Bevan <david.bevan@pb.com>

**Re: Re: Re: generating submultisets with***From:*DrMajorBob <btreat1@austin.rr.com>

**Re: Re: generating submultisets with repeated elements***From:*"Kurt TeKolste" <tekolste@fastmail.us>

**Re: Re: generating submultisets with repeated elements***From:*David Bevan <david.bevan@pb.com>