Re: Re: Re: generating submultisets with

*To*: mathgroup at smc.vnet.net*Subject*: [mg103874] Re: [mg103827] Re: [mg103806] Re: generating submultisets with*From*: DrMajorBob <btreat1 at austin.rr.com>*Date*: Sat, 10 Oct 2009 07:08:46 -0400 (EDT)*References*: <ha4r9k$d0h$1@smc.vnet.net> <200910071101.HAA00387@smc.vnet.net>*Reply-to*: drmajorbob at yahoo.com

> ... and using Subsets[set, {k}] is much faster than KSubsets[set, k] Faster, yes... but not by much. << "Combinatorica`"; Clear[f, g, test1, test2] f[set_] := Table[set[[i]] - (i - 1), {i, Length[set]}] g[set_] := set - Range[0, Length@set - 1] test1[n_, k_] := With[{set = Range[n + k - 1]}, f /@ KSubsets[set, k]] test2[n_, k_] := With[{set = Range[n + k - 1]}, g /@ KSubsets[set, k]] test3[n_, k_] := With[{set = Range[n + k - 1]}, g /@ Subsets[set, {k}]] n = 15; k = 10; Timing@Length@test1[n, k] Timing@Length@test2[n, k] Timing@Length@test3[n, k] Binomial[n + k - 1, k] {33.2636, 1961256} {16.7809, 1961256} {15.1007, 1961256} 1961256 Bobby On Fri, 09 Oct 2009 02:36:51 -0500, David Bevan <david.bevan at pb.com> wrote: > > ... and using Subsets[set, {k}] is much faster than KSubsets[set, k] > > >> -----Original Message----- >> From: DrMajorBob [mailto:btreat1 at austin.rr.com] >> Sent: 8 October 2009 17:05 >> To: David Bevan; mathgroup at smc.vnet.net >> Cc: bayard.webb at gmail.com >> Subject: Re: [mg103827] Re: [mg103806] Re: generating submultisets with >> repeated elements >> >> g is an improvement over f, I think: >> >> << "Combinatorica`"; >> >> Clear[f, g, test1, test2] >> f[set_] := Table[set[[i]] - (i - 1), {i, Length[set]}] >> g[set_] := set - Range[0, Length@set - 1] >> test1[n_, k_] := With[{set = Range[n + k - 1]}, >> f /@ KSubsets[set, k]] >> test2[n_, k_] := With[{set = Range[n + k - 1]}, >> g /@ KSubsets[set, k]] >> >> n = 15; k = 10; >> Timing@Length@test1[n, k] >> Timing@Length@test2[n, k] >> Binomial[n + k - 1, k] >> >> {32.9105, 1961256} >> >> {16.3832, 1961256} >> >> 1961256 >> >> Bobby >> >> On Thu, 08 Oct 2009 06:50:51 -0500, David Bevan <david.bevan at pb.com> >> wrote: >> >> > That's an interesting bijection I wasn't aware of. Thanks. >> > >> > David %^> >> > >> >> -----Original Message----- >> >> From: monochrome [mailto:bayard.webb at gmail.com] >> >> Sent: 7 October 2009 12:02 >> >> To: mathgroup at smc.vnet.net >> >> Subject: [mg103806] 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}} >> >> >> > >> >> >> -- >> DrMajorBob at yahoo.com > -- DrMajorBob at yahoo.com

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