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

Re: Re: NthSubset function of Combinatorica package

• To: mathgroup at smc.vnet.net
• Subject: [mg88852] Re: [mg88835] Re: NthSubset function of Combinatorica package
• From: Andrzej Kozlowski <akoz at mimuw.edu.pl>
• Date: Mon, 19 May 2008 05:17:22 -0400 (EDT)
• References: <g0o7p3$ebb$1@smc.vnet.net> <200805181134.HAA23926@smc.vnet.net> <DB54556C-F282-4518-9394-242851898D94@mimuw.edu.pl> <f831b3d60805180626p58cb465cn74fa627e2f56ed4b@mail.gmail.com>

On 18 May 2008, at 22:26, Szabolcs Horv=E1t wrote:

> On Sun, May 18, 2008 at 2:40 PM, Andrzej Kozlowski 
> <akoz at mimuw.edu.pl> wrote:
>>
>> On 18 May 2008, at 20:34, Szabolcs Horv=E1t wrote:
>>
>>> Roman wrote:
>>>>
>>>> Hello all:
>>>>
>>>> Do you know how the function "NthSubset" of the Combinatorica 
>>>> package
>>>> works? If you can point me to a description of the algorithm, that
>>>> would be very helpful.
>>>>
>>>
>>> You can read the source code of all standard packages.  Go to
>>> $InstallationDirectory/AddOns/Packages/Combinatorica, and search for
>>> NthSubset in Combinatorica.m.  You will find that it just calls the
>>> built-in Subsets function.
>>>
>>> Subsets[] is built-in, so we cannot see its implementation.  But 
>>> there
>>> are several subset-related functions in Combinatorica, such as 
>>> KSubsets,
>>> whose code is available.  You can check those.
>>>
>>> Or just search the web.  Here's the first hit I got for "generating
>>> subsets":
>>>
>>> http://compprog.wordpress.com/2007/10/10/generating-subsets/
>>>
>>> And a Mathematica implementation of this algorithm (for generating =

>>> all
>>> subsets):
>>>
>>> subsets[l_List] :=
>>> Table[Pick[l, IntegerDigits[k, 2, Length[l]], 1],
>>>  {k, 0, 2^Length[l] - 1}]
>>>
>>
>>
>> However, note that
>>
>> Subsets[Range[1000], All, {1100}]
>>
>> ( {{1, 100}} )
>>
>> returns the answer immediately while
>>
>> Subsets[Range[1000], All]
>>
>> gives a rather different answer ... so the former certianly does 
>> make use of
>> the latter.
>>
>
> Certainly you mean that it does NOT make use of the latter (just a 
> typo). :-)

Yes, looking back at my posts I often see that some things that I 
meant to be there are missing, or that some things that I did not mean 
to be there are present. Very rarely everything is perfectly in order 
but then the post itself is missing ;-)

>
>
> I am quite confused about the subset-related functions of 
> Combinatorica.
>
> There are several functions for generating the nth subset for
> different orderings.  The doc page of NthSubset uses the expression
> "canonical order", and this is what the function produces:
>
> Table[NthSubset[i, {1, 2, 3}], {i, 0, 2^3 - 1}]
>
> {{}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}

This is the standard length-lexicographic ordering. That means: first 
subsets are ordered by length, then, among those of equal length the 
lexicographic order is used.
>
>
> The doc page of NextSubset also mentions "canonical order", but it
> generates subsets in a different order:
>
> NestList[NextSubset[{1, 2, 3}, #] &, {}, 2^3 - 1]
>
> {{}, {3}, {2}, {2, 3}, {1}, {1, 3}, {1, 2}, {1, 2, 3}}

Here it seems that subsets are ordered "lexicographically" according 
to the elements they do not contain - those that do not contain 1 come 
before those that do, if both contain (or both do not contain) 1, then 
those that do not contain 2 come earlier, and so on.
>
>
> The doc page of UnrankSubset says "some canonical order":
>
> Table[UnrankSubset[i, {1, 2, 3}], {i, 0, 2^3 - 1}]
>
> {{}, {3}, {2, 3}, {2}, {1, 2}, {1, 2, 3}, {1, 3}, {1}}

This one seems more complicated, or at least I can only see a fairly 
complicated way of describing it. First, subsets that do not contain 1 
come before those that do. Next, among those that do not contain 1, 
those that contain 2 come after those that don't and among those that 
do contain 1, those that contain 2 are come before those that do not. 
This "alternation" is then continued inductively. (there maybe a much 
easier way to describe this ordering  but I can't see it right now). I 
assume that this somewhat strange ordering is used because of better 
performance (?)


This is the standard length-lexicographic ordering. That means, first 
subsets are ordered by length. Then, among those of equal length the 
lexicographic order is used.

Andrzej Kozlowski

>
>
> So it seems that "canonical order" can mean many different things in
> Combinatorica ...
>
> There are some other functions, too, with precise definitions of the
> order, such as UnrankGrayCodeSubset, UnrankBinarySubset, and
> NextLexicographicSubset.
>
> It seems that the relevant function (with accessible source code) for
> the OP is UnrankKSubset, because it generates subsets in the same
> order as NthSubset/Subset:
>
> Join @@ Table[
>  UnrankKSubset[m - 1, k, {1, 2, 3, 4}], {k, 0, 4}, {m, Binomial[4, 
> k]}]
>
> {{}, {1}, {2}, {3}, {4}, {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4},
> {3, 4}, {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}, {1, 2, 3, 4}}


>
>
> UnrankKSubset is also a good example of why it is a very bad idea to
> use $RecursionLimit = Infinity.  On the doc page it is not explained
> that UnrankKSubset's first argument starts from 0 (and not from 1),
> and UnrankKSubset[1, 0, {1, 2, 3}] (which one might expect to return
> {}) simply crashes the kernel, causing the kernel state to be lost.
>
> I really hope that WRI will include proper stack overflow protection
> in future versions of Mathematica ... (and perhaps a Front End
> dialogue box that would alert the user that the kernel has crashed ...
> the only indication is a beep and I am sure that many users will not
> notice immediately what happened.)

• References:
  • Re: NthSubset function of Combinatorica package
    • From: Szabolcs Horvát <szhorvat@gmail.com>