Re: Re: NthSubset function of Combinatorica package

*To*: mathgroup at smc.vnet.net*Subject*: [mg88836] Re: [mg88835] Re: NthSubset function of Combinatorica package*From*: Andrzej Kozlowski <akoz at mimuw.edu.pl>*Date*: Mon, 19 May 2008 05:14:12 -0400 (EDT)*References*: <g0o7p3$ebb$1@smc.vnet.net> <200805181134.HAA23926@smc.vnet.net>

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. Andrzej Kozlowski

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