Re: Re: NthSubset function of Combinatorica package

• To: mathgroup at smc.vnet.net
• Subject: [mg88854] Re: [mg88835] Re: NthSubset function of Combinatorica package
• From: "Szabolcs HorvÃt" <szhorvat at gmail.com>
• Date: Mon, 19 May 2008 05:17:45 -0400 (EDT)
• References: <g0o7p3\$ebb\$1@smc.vnet.net> <200805181134.HAA23926@smc.vnet.net>

```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Ã¡t 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
>>>
>>
>> You can read the source code of all standard packages.  Go to
>> 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). :-)

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}}

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}}

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}}

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.)

```