Services & ResourcesWolfram ForumsMathGroup Archive

[Date Index] [Thread Index] [Author Index]

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>