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

Re: NthSubset function of Combinatorica package

• To: mathgroup at smc.vnet.net
• Subject: [mg88873] Re: NthSubset function of Combinatorica package
• From: Roman <rschmied at gmail.com>
• Date: Tue, 20 May 2008 02:25:15 -0400 (EDT)
• References: <g0o7p3$ebb$1@smc.vnet.net> <200805181134.HAA23926@smc.vnet.net>

Szabolcs, Andrzej,

Thanks for the input. RankKSubset and UnrankKSubset do exactly what I
need, and their code is explicitly given in the Combinatorica package.
All I needed was being pointed to the right functions...

Cheers!
Roman.


On May 19, 12:25 pm, "Szabolcs Horv=E1t" <szhor... at gmail.com> wrote:
> On Sun, May 18, 2008 at 2:40 PM, Andrzej Kozlowski <a... at mimuw.edu.pl> wro=
te:
>
> > 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 ther=
e
> >> 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 us=
e 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.)

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