ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Sun, 15 Apr 2018 20:06:05 +0200Posets(10) freezinghttps://ask.sagemath.org/question/41912/posets10-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.Sun, 08 Apr 2018 20:36:48 +0200https://ask.sagemath.org/question/41912/posets10-freezing/Comment by slelievre for <p>For some reason in SageMath 8.1 the following code leads to a freeze:</p>
<pre><code>p10 = Posets(10)
p10[18]
</code></pre>
<p>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.</p>
https://ask.sagemath.org/question/41912/posets10-freezing/?comment=41922#post-id-41922I can observe that in Sage 8.2.rc1 too.Mon, 09 Apr 2018 01:36:14 +0200https://ask.sagemath.org/question/41912/posets10-freezing/?comment=41922#post-id-41922Answer by tmonteil for <p>For some reason in SageMath 8.1 the following code leads to a freeze:</p>
<pre><code>p10 = Posets(10)
p10[18]
</code></pre>
<p>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.</p>
https://ask.sagemath.org/question/41912/posets10-freezing/?answer=42021#post-id-42021This 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()`).Sun, 15 Apr 2018 20:06:05 +0200https://ask.sagemath.org/question/41912/posets10-freezing/?answer=42021#post-id-42021