Ask Your Question
5

Posets(10) freezing

asked 2018-04-08 13:40:04 -0500

artem.k gravatar image

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 flag offensive close merge delete

Comments

I can observe that in Sage 8.2.rc1 too.

slelievre gravatar imageslelievre ( 2018-04-08 18:36:14 -0500 )edit

1 answer

Sort by ยป oldest newest most voted
2

answered 2018-04-15 13:06:05 -0500

tmonteil gravatar image

updated 2018-04-15 13:16:25 -0500

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()).

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2018-04-08 13:36:48 -0500

Seen: 59 times

Last updated: Apr 15