# Posets(10) freezing

For some reason in SageMath 8.1 the following code leads to a freeze:

p10 = Posets(10)
p10[18]


I have tried different indices, and everything works fine for i<=17, but starting from 18 I can not access to p10[i] without an immediate freeze. The bug does not depend on system: I tried macOS and Windows 10, both lead to the same result.

edit retag close merge delete

I can observe that in Sage 8.2.rc1 too.

( 2018-04-09 01:36:14 +0200 )edit

Sort by » oldest newest most voted

This is due to the generic algorithm generating the posets. If you do:

sage: for i in p10:
....:     print i


You will get the 18 "first" posets as:

Finite poset containing 10 elements


But then the generator probably has to backtrack a lot before finding another poset. If you want to make clear why 19 is a backtracking point, just do:

sage: for i in p10:
....:     i.show()


You will immediately get why there is some complexity gap at this point.

Note that if you are patient enough (a few minutes, about three), then you will get a ton of new posets. This is just that during the exploration the algorithm falls into a zone with plent of posets:

sage: %time p10[18]
CPU times: user 2min 43s, sys: 20 ms, total: 2min 43s
Wall time: 2min 44s
Finite poset containing 10 elements


Note that counting the number of posets on a given set is very hard (and related to counting finite topologies), the human kind is not even able to count the posets on 17 elements (yet). If we could iterate on them in a fast way, we would also be able to count them easily. See https://oeis.org/A000112 for the first values (they are hardcoded in Sage with Posets(i).cardinality()).

more