Re: Re: generating submultisets with repeated elements
- To: mathgroup at smc.vnet.net
- Subject: [mg103885] Re: [mg103849] Re: generating submultisets with repeated elements
- From: David Bevan <david.bevan at pb.com>
- Date: Sat, 10 Oct 2009 07:10:51 -0400 (EDT)
- References: <ha4r9k$d0h$1@smc.vnet.net> <200910071101.HAA00387@smc.vnet.net>
Bayard,
To handle general sets you do something like:
multiSets[s_List, k] := s[[#]]& /@ multiSets[Length[s], k]
multiSets[n_, k_] := f /@ Subsets[Range[n + k - 1], {k}]]
David %^>
> -----Original Message-----
> From: monochrome [mailto:bayard.webb at gmail.com]
> Sent: 9 October 2009 12:16
> To: mathgroup at smc.vnet.net
> Subject: [mg103849] Re: generating submultisets with repeated elements
>
> There is one thing that I glossed over here. This solution works only
> on the indices of the sets. This will go horribly wrong if you use it
> with general sets like {"cat","dog",...,"hamster"}. Worse yet, if you
> used this with sets of numbers, the method would calculate, but return
> garbage. Here's why...
>
> There is an algorithm to generate all subsets of a set that goes as
> follows:
> 1. List the elements
> 2. Over the first k elements, draw an arrow pointing right
> 3a. Capture the elements with arrows as a subset
> 3b. Move the rightmost free arrow to the right (an arrow is free if
> points to an empty space)
> 3c. If, after moving the arrow, it isn't free, reverse its direction
> 3d. Working to the right, move all free arrows that lie to the right
> of the arrow you just moved until they are no longer free and reverse
> them. (Note that they will all be pointing left when you start this
> step, and all point right at the end.)
> Repeat 3 until there are no free arrows.
>
> The difference between sets and multisets lies in steps 3b and 3d. To
> get multisets you allow arrows to lie over the same element, either at
> the end of the list or at the element that moves in step 3b.
>
> The method I proposed uses the index positions of the k arrows and the
> function accounts for the differences noted above. So while KSubsets
> will work on general sets, my solution requires that you work with
> indices. You could modify the solution to use set elements and use the
> Position[] function to recover the index, or use the solution as is
> and do a substitution at the end.
>
> This may have been obvious to everyone, but I felt I should have
> stated it more clearly. Also, the algorithm is what I can remember
> from an excerpt from a book by Brualdi. I haven't seen it for fifteen
> years and had to recreate it from what I could remember. If there is a
> mistake in my explanation, it's mine not Brualdi's. I had actually
> stumbled on the function first, then had to recreate this algorithm to
> figure out why it worked.
>
> Bayard
>
>
> On Oct 8, 4:57 am, David Bevan <david.be... at pb.com> wrote:
> > That's an interesting bijection I wasn't aware of. Thanks.
> >
> > David %^>
> >
> >
> >
> > > -----Original Message-----
> > > From: monochrome [mailto:bayard.w... at gmail.com]
> > > Sent: 7 October 2009 12:02
> > > To: mathgr... at smc.vnet.net
> > > Subject: Re: generating submultisets with repeated elements
> >
> > > 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}}
>
>
- References:
- Re: generating submultisets with repeated elements
- From: monochrome <bayard.webb@gmail.com>
- Re: generating submultisets with repeated elements