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 >>> 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). :-) 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>
- Re: NthSubset function of Combinatorica package