Re: generating submultisets with repeated elements

*To*: mathgroup at smc.vnet.net*Subject*: [mg103849] Re: generating submultisets with repeated elements*From*: monochrome <bayard.webb at gmail.com>*Date*: Fri, 9 Oct 2009 07:16:17 -0400 (EDT)*References*: <ha4r9k$d0h$1@smc.vnet.net> <200910071101.HAA00387@smc.vnet.net>

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

**Follow-Ups**:**Re: Re: generating submultisets with repeated elements***From:*Daniel Lichtblau <danl@wolfram.com>

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