[Date Index]
[Thread Index]
[Author Index]
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.)
Prev by Date:
**Re: Re: NthSubset function of Combinatorica package**
Next by Date:
**Re: Range of Use of Mathematica**
Previous by thread:
**Re: Re: NthSubset function of Combinatorica package**
Next by thread:
**Re: NthSubset function of Combinatorica package**
| |