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>