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