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: [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


  • Prev by Date: Re: Filtering a list of list for certain elements that are neighbours
  • Next by Date: Re: An Elegant way of plotting the Pole-Zero diagram
  • Previous by thread: Re: Re: NthSubset function of Combinatorica package
  • Next by thread: Re: Re: NthSubset function of Combinatorica package