Re: Re: NthSubset function of Combinatorica package
- To: mathgroup at smc.vnet.net
- Subject: [mg88860] Re: [mg88835] Re: NthSubset function of Combinatorica package
- From: Andrzej Kozlowski <akoz at mimuw.edu.pl>
- Date: Mon, 19 May 2008 05:18:55 -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> <C9AB9EB4-F750-40EB-9106-A0AB94D3CFD1@mimuw.edu.pl>
On 19 May 2008, at 17:10, Andrzej Kozlowski wrote:
>>>
>>>
>>
>> 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.
This last paragraph, of course, should have been erased before
posting. It provided a completely unintended illustration of what I
wrote at the beginning.
Andrzej
- References:
- Re: NthSubset function of Combinatorica package
- From: Szabolcs Horvát <szhorvat@gmail.com>
- Re: NthSubset function of Combinatorica package