Count Number of Linear Extensions of a Poset

[sagetrac-csar]

Posets appear to have no mechanism to count the number of linear extensions other than computing all the linear extensions and finding the length of that list. Using recursion, one can count the number of linear extensions without having to generate all the linear extensions.

CC: @kevindilks @jm58660

Component: combinatorics

Keywords: days45

Author: Jori Mäntysalo

Branch/Commit: 24bc331

Reviewer: Frédéric Chapoton

Issue created by migration from https://trac.sagemath.org/ticket/14126

[sagetrac-csar]

comment:3

Patch does not apply and it's not clear why.

[nathanncohen]

comment:4

(this code should probably be stored in from sage.combinat.posets.linear_extensions. Besides, your code may be faster for small cases but can also require an exponential memory, which can be a problem too).

[nathanncohen]

Author: aschilling, nthiery, hivert

[sagetrac-csar]

Attachment: trac_14126-count_linear_extensions_of_a_poset-csar.patch.gz

[sagetrac-csar]

comment:5

Replying to @nathanncohen:

(this code should probably be stored in from sage.combinat.posets.linear_extensions. Besides, your code may be faster for small cases but can also require an exponential memory, which can be a problem too).

I've moved the code to sage.categories.finite_poset, which I realise is not what you've said, and added a note in the docstring saying one may prefer to count linear extensions of P by using P.linear_extensions().cardinality(), which uses the iterator belonging to LinearExtensionsOfPoset and avoids all the cacheing.

[nathanncohen]

comment:6

O_o

Well, shouldn't the two codes that compute the number of linear extensions be at the same place ?... A choice could be madebetween the two with an argument to cardinality().

Nathann

[kevindilks]

comment:7

We originally made this function not aware that linear extensions had an iterator which would compute P.linear_extensions().cardinality() without computing all of P.linear_extensions().

In it's current form, I believe this code iterates over all linear extensions roughly same way the iterator does. So they should be approximately the same speed, and if this code is better, then those changes should be applied directly to the iterator.

However, Stembridge's posets package is still much faster at counting linear extensions. He iterates over all linear extensions approximately the same way we do, but when you just want a count of linear extensions, he has separate code that counts maximal chains in J(P). There's a fast way to count chains that doesn't involve iterating over all of them. One might think computing J(P) is expensive, but one only needs to know the covering relations, and we could come up with a faster implementation than P.order_ideals_lattice() for this purpose (that method computes a poset whose elements are sets of elements in P, and we should be able to more quickly make an isomorphic poset on [1..n]).

I think it's worth keeping this ticket open for development of this alternate way of counting linear extensions. Once we have a satisfactory implementation, we can change P.linear_extensions().cardinality() to call this special code for enumeration, rather than using the linear_extensions iterator.

[kevindilks]

comment:8

But for what it's worth, I was successfully able to apply the latest version of the patch.

[sagetrac-csar]

comment:9

Replying to @nathanncohen:

O_o

Well, shouldn't the two codes that compute the number of linear extensions be at the same place ?... A choice could be madebetween the two with an argument to cardinality().

Nathann

Fair point. cardinality() doesn't seem to live in sage.combinat.posets.linear_extensions, though. It looks like it comes from the FiniteEnumeratedSets category. Is it legitimate to give LinearExtensionsOfPoset a cardinality function with an argument to choose between the _cardinality_from_iterator from FiniteEnumeratedSets and counting recursively? My understanding of how categories are meant to work does not extend this far.

[nathanncohen]

comment:10

Hellooooooooo !!

Fair point. cardinality() doesn't seem to live in sage.combinat.posets.linear_extensions, though. It looks like it comes from the FiniteEnumeratedSets category.

Oh. Right. So it builds all linear extensions then counts them -_-

Is it legitimate to give LinearExtensionsOfPoset a cardinality function with an argument to choose between the _cardinality_from_iterator from FiniteEnumeratedSets and counting recursively? My understanding of how categories are meant to work does not extend this far.

My understanding of categories is that when they prevent you from doing something you need then categories should be changed to allow you to do whatever you wanted to do in the first place.

Technically I do not think that categories would mind an optional argument to .cardinality. I guess that they would not notice it, so that's all good.

This being said, if you are at the Sage Days 45 right now Nicolas Thiery should be around. And he's THE guy you should bug for anything related to categories :-P

Nathann

[nthiery]

comment:11

Replying to @nathanncohen:

Fair point. cardinality() doesn't seem to live in sage.combinat.posets.linear_extensions, though. It looks like it comes from the FiniteEnumeratedSets category.

Oh. Right. So it builds all linear extensions then counts them -_-

To be precise, for an object in FiniteEnumeratedSets, cardinality is
set by default to _cardinality_from_iterator. So it indeed goes
through all linear extensions. However the counting is done along the
way, without storing them. So the memory complexity is roughly
constant (well, linear in the size of one linear extension).

Is it legitimate to give LinearExtensionsOfPoset a cardinality
function with an argument to choose between the
_cardinality_from_iterator from FiniteEnumeratedSets and
counting recursively? My understanding of how categories are meant
to work does not extend this far.

+1

My understanding of categories is that when they prevent you from
doing something you need then categories should be changed to allow
you to do whatever you wanted to do in the first place.

Certainly: in any object oriented system, abstract classes are here to
provide you with default implementations. By design they are meant to
be overridden whenever there is a better algorithm in a special case
and the application in mind makes it worth it to implement that
algorithm

Categories are nothing but a way to organize those abstract classes.

Cheers,
Nicolas

[sagetrac-csar]

comment:12

I will give LinearExtensionsOfPoset the choice of which method to count linear extensions.

[jm58660]

comment:18

Replying to @kevindilks:

There's a fast way to count chains that doesn't involve iterating over all of them.

What is it?

If there are several ways to do this, none of which is best from all sides, shouldn't we then have algorithm-keyword for the function? And in any version I guess that the poset should first be splitted to connected parts.

Is there something wrong with making a function with dumb implementation first? Then we would have a reference implementation, docstring and already thinked interface and place for the function.

[jm58660]

Branch: u/jmantysalo/count-lin-ext

[jm58660]

comment:26

?? Current version is written by me. (But of course it is trivial modification that just basically still counts all linear extensions.)

[fchapoton]

comment:27

I was just cleaning a few invalid author fields. Please change it.

[jm58660]

Changed author from Anne Schilling, Nicolas M. Thiéry, Florent Hivert to Jori Mäntysalo

[kevindilks]

comment:29

I am still intending on figuring out the 'right' way to do this. After recently realizing I can make the method be on the Hasse diagram, and can assume that I'm working with a naturally labelled poset on 0...n-1 with a dictionary of covering relations, I should be able to make it work.

[jm58660]

comment:30

I don't quite understand. AFAIK it is proved that counting linear extensions is in #P, and according to http://link.springer.com/chapter/10.1007%2F11537311_39 there is an algorithm that lists them in linear time.

We can trivially reduce time by doing series-parallel decomposition first. It won't help on average.

So do you have some good algorithm in mind? Being in #P does not mean that k could not be improved in O(k^n).

[kevindilks]

comment:31

The #P result you keep citing only applies to generating a list all linear extensions, not counting them. For example, I can tell you that the number of linear extensions of an antichain of size n is n!, independent of any complexity issues that arise when trying to generate all n! permutations.

The algorithm is used in Stembridge's Posets package. The general idea is that linear extensions are maximal chains in the lattice of order ideals.

If you want to enumerate (not generate) maximal chains, then you can use fact that if f(x) is the number of saturated chains from a minimal element to x, then f(y) = sum f(x) over all x covered by y.

If we wanted to keep the code simple, we could just create the lattice of order ideals J(P) using Sage. But then the elements of this poset would be subsets, and we'd have another (potentially expensive) computation to make the Hasse diagram and get a naturally labelled poset on 0...(|I|-1) (where |I| is the number of order ideals). I think I tried this implementation in the past, and it was still an order of magnitude or two slower than the corresponding Maple code.

However, there should be some wizardry that lets us quickly create a dictionary on 0 .. (|I|-1) corresponding to the up edges in J(P). That wizardry is what I'm trying to figure out.

This algorithm works whether or not P is connected. However, there would be some significant speed-up for posets with a large number of connected components if we just counted the number of linear extensions on each connected component, and combined the results appropriately (if f(P) is the number of linear extensions on P, and P=P_1 U ... U P_k , then f(P)= multinomial(|P|,{|P_1|,...,|P_k|}) * product f(P_i) .

For example, say we look at the anti-chain of 11 elements. Currently, we have to iterate over close to 40 million permutations. Using the wizardry, we would just have to create a dictionary of 2048 elements corresponding to up-edges in the Boolean lattice and iterate over it. And if we split into connected components...getting 11! is almost automatic.

[jm58660]

comment:32

?? Isn't the concept of #P about counting something? And http://link.springer.com/article/10.1007/BF00383444 seems to say that too. It is trivial to say that listing them takes more than polynomial time.

Of course there are easy answers for some posets. For the ordinal sum of P and Q the count is just product.

But I will wait for the code and see.

E: Something in lattice of ideals - but every ideal corresponds to an antichain, and counting antichains is in #P I think.

[kevindilks]

comment:33

Whatever it is, asymptotics aren't particularly relevant when in practice we're not going past |P|>100.

Even without any wizardry, P.order_ideals_lattice().chain_polynomial().leading_coefficient() (the naive implementation I mentioned) is significantly faster than P.linear_extensions().cardinality() (which defaults to using the iterator and generates all of them). Twice as fast on the antichain of 8 elements, ten times as fast on P=Posets.TamariLattice(4) (14 elements, 20243 linear extensions), ~600 times as fast on P=Posets.IntegerCompositions(5) (16 elements, 1680384 linear extensions).

[jm58660]

comment:34

Very interesting! Must think about this.

And as_ideals=False will get still more speed.

[jm58660]

comment:35

This got more speed with even very basic implementation of maximal chains counting:

def countmax(P):
    L = P.level_sets()
    c = {}
    for l in L[0]:
        c[l] = 1
    for lev in L[1:]:
        for l in lev:
            c[l] = sum(c[i] for i in P.lower_covers(l))
    return sum(c[i] for i in P.maximal_elements())

If we have better way to make a order ideals lattice, it is a place for new ticket. It would be nice feature in itself.

Hmm... Assuming we have n-element poset P and corresponding L=J(P), how we modify L when we add element n+1 as a minimal element to P? I guess the algorithm should be done by thinking this.

[jm58660]

comment:36

I guess this is worth reading about order ideals lattice: http://www.sciencedirect.com/science/article/pii/S0166218X00002584

[kevindilks]

comment:37

After much staring at Maple code, I now mostly understand the algorithm to generate a naturally labelled poset isomorphic to the order ideal lattice given a naturally labelled poset.

The idea is similar to what you mentioned. Run a loop that takes the lattice of order ideals for P restricted to {1,...,k}, and think about what happens when you add k+1. You need to know which order ideal I_{k+1} corresponds to the principal order ideal generated by k+1 (but with k+1 removed, since we haven't added it to the poset yet).

Now, you create a list K of the order ideals that lie above I_{k+1} in your partial lattice of order ideals. Each of these is going to yield a new order ideal to add to your list (the corresponding ideal I plus the new k+1). Make sure that K is ordered so that our lattice of order ideals stayed naturally labelled. The relations you need to add are I is covered by I plus k+1, and for every relation A covers B in K, you're going to have to add A plus k+1 covers B plus k+1.

The main subtlety is in creating and maintaining a helper list that will eventually tell you where I_{k+1} is by the time you reach the k+1st step. Call the list L, indexed by your poset elements, initialize it with all 1s. As you go along, after k iterations, the entry L[j] tells you which order ideal corresponds to I_j restricted to 1...k. If you add something incomparable to j, then I_j restricted to 1...k+1 doesn't change. If you add something comparable to j, then I_j restricted to 1...k+1 is one of the things in K plus k+1. So if we started with N order ideals, and I_j restricted to 1...k was the rth thing in K, then I_j restricted to 1...k+1 will be the N+rth thing, and we update L accordingly.

Since it might take me some time to actually sit down and implement this, I agree that it makes sense to just change the P.linear_extensions().cardinality() method to something simple like P.order_ideals_lattice().chain_polynomial().leading_coefficient() (maybe with an optional parameter allowing one to default back to the iterator). Then I can work on a separate ticket for generating a naturally labelled poset isomorphic to the order ideal lattice, which P.linear_extensions().cardinality() could eventually utilize.

[jm58660]

comment:38

Does that mean that order_ideals_lattice() will have an option to get a lattice with plain integers as elements? If so, we should now deprecate as_ideal keyword, as it is plain Boolean value. Or at least it sounds funny to have as_ideal with possible values True, False and 'integers'.

[sagetrac-git]

Changed commit from f908696 to 24bc331

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

24bc331

Add cardinality() to linear extensions of poset.

[jm58660]

comment:40

Shall we then accept this solution, and later think about optimizing this in two different ways?

Series-parallel decomposition could be a good thing anyways.

[kevindilks]

comment:41

Replying to @jm58660:

Does that mean that order_ideals_lattice() will have an option to get a lattice with plain integers as elements? If so, we should now deprecate as_ideal keyword, as it is plain Boolean value. Or at least it sounds funny to have as_ideal with possible values True, False and 'integers'.

Yes. It probably makes sense to deprecate as_ideals, and change it to a keyword like representative that defaults to ideal, but can also be antichains or integers.

I guess I'd want to quantify how much overhead calculating connected components and a series-parallel decomposition of the original Hasse diagram introduces (my guess is a little and lot, respectively) before making it part of every single computation. I feel like unless you explicitly construct something as an ordinal/disjoint sum of smaller posets (and thus should already know the decomposition), almost every poset you'd throw at this where you'd really need optimal performance is going to be connected and not have a series-parallel decomposition.

[jm58660]

comment:42

Replying to @kevindilks:

Yes. It probably makes sense to deprecate as_ideals, and change it to a keyword like representative that defaults to ideal, but can also be antichains or integers.

That could be done now; a little less time for new users to learn a feature to be deprecated.

I guess I'd want to quantify how much overhead calculating connected components and a series-parallel decomposition of the original Hasse diagram introduces (my guess is a little and lot, respectively) before making it part of every single computation. I feel like unless you explicitly construct something as an ordinal/disjoint sum of smaller posets (and thus should already know the decomposition), almost every poset you'd throw at this where you'd really need optimal performance is going to be connected and not have a series-parallel decomposition.

True, but then whole decomposition will be just one check to see that the poset can not be decomposed.

And in any case that should a place for it's own ticket.

[fchapoton]

comment:43

ok, looks good to me.

[fchapoton]

Reviewer: Frédéric Chapoton

[vbraun]

Changed branch from u/jmantysalo/count-lin-ext to 24bc331