Re: Re: generating submultisets with repeated elements
- To: mathgroup at smc.vnet.net
- Subject: [mg103834] Re: [mg103806] Re: generating submultisets with repeated elements
- From: "Kurt TeKolste" <tekolste at fastmail.us>
- Date: Thu, 8 Oct 2009 07:52:08 -0400 (EDT)
- References: <ha4r9k$d0h$1@smc.vnet.net> <200910071101.HAA00387@smc.vnet.net>
Elegant, fast, ... and not procedural
On Wed, 07 Oct 2009 07:01 -0400, "monochrome"
<bayard.webb at gmail.com> wrote:
> 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,#]&/@Ran
ge[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 %^>
>
>
Regards,
Kurt Tekolste
- References:
- Re: generating submultisets with repeated elements
- From: monochrome <bayard.webb@gmail.com>
- Re: generating submultisets with repeated elements