Services & ResourcesWolfram ForumsMathGroup Archive

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

Re: NthSubset function of Combinatorica package

• To: mathgroup at smc.vnet.net
• Subject: [mg88835] Re: NthSubset function of Combinatorica package
• From: Szabolcs Horvát <szhorvat at gmail.com>
• Date: Sun, 18 May 2008 07:34:29 -0400 (EDT)
• Organization: University of Bergen
• References: <g0o7p3$ebb$1@smc.vnet.net>

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}]

• Follow-Ups:
  • Re: NthSubset function of Combinatorica package
    • From: Roman <rschmied@gmail.com>
  • Re: Re: NthSubset function of Combinatorica package
    • From: "Szabolcs HorvÃt" <szhorvat@gmail.com>
  • Re: Re: NthSubset function of Combinatorica package
    • From: Andrzej Kozlowski <akoz@mimuw.edu.pl>