Services & ResourcesWolfram ForumsMathGroup Archive

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

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>