Re: Re: generating submultisets with repeated elements

*To*: mathgroup at smc.vnet.net*Subject*: [mg103872] Re: [mg103849] Re: generating submultisets with repeated elements*From*: Daniel Lichtblau <danl at wolfram.com>*Date*: Sat, 10 Oct 2009 07:08:22 -0400 (EDT)*References*: <ha4r9k$d0h$1@smc.vnet.net> <200910071101.HAA00387@smc.vnet.net> <200910091116.HAA25909@smc.vnet.net>

monochrome wrote: > 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}} > A very small modification of your method will work for general sets. multiSetsK[set_,k_] := With[{diffset=Range[k]-1}, Map[set[[#-diffset]]&, Subsets[Range[Length[set]+k-1], {k}]]] multiSetsToK[set_,k_] := Join @@ Table[multiSetsK[set,j],{j,k}] In[27]:= set = {1,0,-7,"dog",913,"cat"}; InputForm[multiSetsToK[set,3]] In[28]:= Out[28]//InputForm= {{1}, {0}, {-7}, {"dog"}, {913}, {"cat"}, {1, 1}, {1, 0}, {1, -7}, {1, "dog"}, {1, 913}, {1, "cat"}, {0, 0}, {0, -7}, {0, "dog"}, {0, 913}, {0, "cat"}, {-7, -7}, {-7, "dog"}, {-7, 913}, {-7, "cat"}, {"dog", "dog"}, {"dog", 913}, {"dog", "cat"}, {913, 913}, {913, "cat"}, {"cat", "cat"}, {1, 1, 1}, {1, 1, 0}, {1, 1, -7}, {1, 1, "dog"}, {1, 1, 913}, {1, 1, "cat"}, {1, 0, 0}, {1, 0, -7}, {1, 0, "dog"}, {1, 0, 913}, {1, 0, "cat"}, {1, -7, -7}, {1, -7, "dog"}, {1, -7, 913}, {1, -7, "cat"}, {1, "dog", "dog"}, {1, "dog", 913}, {1, "dog", "cat"}, {1, 913, 913}, {1, 913, "cat"}, {1, "cat", "cat"}, {0, 0, 0}, {0, 0, -7}, {0, 0, "dog"}, {0, 0, 913}, {0, 0, "cat"}, {0, -7, -7}, {0, -7, "dog"}, {0, -7, 913}, {0, -7, "cat"}, {0, "dog", "dog"}, {0, "dog", 913}, {0, "dog", "cat"}, {0, 913, 913}, {0, 913, "cat"}, {0, "cat", "cat"}, {-7, -7, -7}, {-7, -7, "dog"}, {-7, -7, 913}, {-7, -7, "cat"}, {-7, "dog", "dog"}, {-7, "dog", 913}, {-7, "dog", "cat"}, {-7, 913, 913}, {-7, 913, "cat"}, {-7, "cat", "cat"}, {"dog", "dog", "dog"}, {"dog", "dog", 913}, {"dog", "dog", "cat"}, {"dog", 913, 913}, {"dog", 913, "cat"}, {"dog", "cat", "cat"}, {913, 913, 913}, {913, 913, "cat"}, {913, "cat", "cat"}, {"cat", "cat", "cat"}} To my surprise, it seems quite efficient (after seeing some of the other entrants, I had pretty much given up in the speed category). In[5]:= Timing[Length[s7 = multiSetsToK[Range[20],7]]] Out[5]= {1.49377, 888029} In[6]:= Timing[Length[s8 = multiSetsToK[Range[20],8]]] Out[6]= {5.42518, 3108104} In[7]:= Timing[Length[s10 = multiSetsToK[Range[15],10]]] Out[7]= {5.97709, 3268759} Caveat: It seems to be memory hungry. I ran the largest examples on a 64 bit machine. Even packing the subsets via Developer`ToPackedArray does not salvage it; something (maybe Part?) is later unpacking. Daniel Lichtblau Wolfram Research

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

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

**Re: Re: How to find which variable caused the trigger in Manipulate[]**

**Re: Plot with axis with the same scaling factor**

**Re: generating submultisets with repeated elements**

**Re: Re: Re: Re: generating**