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