Mathematica 9 is now available
Services & Resources / Wolfram Forums / MathGroup Archive
-----

MathGroup Archive 2008

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

Search the Archive

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




  • Prev by Date: Re: Filtering a list of list for certain elements that are neighbours
  • Next by Date: Re: Filtering a list of list for certain elements that are neighbours
  • Previous by thread: Re: NthSubset function of Combinatorica package
  • Next by thread: Re: Re: NthSubset function of Combinatorica package