#14094: Iterating through Partitions(n) for n>=1000.
---------------------------------+------------------------------------------
Reporter: nthiery | Owner: sage-combinat
Type: defect | Status: positive_review
Priority: major | Milestone: sage-5.9
Component: combinatorics | Resolution:
Keywords: days45 | Work issues:
Report Upstream: N/A | Reviewers: Travis Scrimshaw
Authors: Mike Hansen | Merged in:
Dependencies: #13605 | Stopgaps:
---------------------------------+------------------------------------------
Changes (by tscrim):
* status: needs_work => positive_review
Old description:
> As discovered live during the Sage Days 45 tutorial, the default fast
> iterator for Partitions(n) is recursive and breaks for n>988:
> {{{
> sage: P = Partitions(988)
> sage: for p in P: print p
> Traceback (most recent call last):
> File "<ipython console>", line 1, in <module>
> File "/opt/sage-5.6/local/lib/python2.7/site-
> packages/sage/combinat/partition.py", line 4282, in __iter__
> sage: all(test(mu,k) for k in range(1,5)
> File "/opt/sage-5.6/local/lib/python2.7/site-
> packages/sage/combinat/partition.py", line 4312, in _fast_iterator
> new_w.sort(reverse=True)
> File "/opt/sage-5.6/local/lib/python2.7/site-
> packages/sage/combinat/partition.py", line 4312, in _fast_iterator
> new_w.sort(reverse=True)
> }}}
>
> Whereas the generic iterator works:
> {{{
> sage: P = Partitions(988, max_part=1000)
> sage: for p in P: print p
> [988]
> [987, 1]
> [986, 2]
> [986, 1, 1]
> [985, 3]
> }}}
>
> Possible fix: either make the fast iterator non recursive, or default to
> the generic iterator.
New description:
As discovered live during the Sage Days 45 tutorial, the default fast
iterator for Partitions(n) is recursive and breaks for n>988:
{{{
sage: P = Partitions(988)
sage: for p in P: print p
Traceback (most recent call last):
File "<ipython console>", line 1, in <module>
File "/opt/sage-5.6/local/lib/python2.7/site-
packages/sage/combinat/partition.py", line 4282, in __iter__
sage: all(test(mu,k) for k in range(1,5)
File "/opt/sage-5.6/local/lib/python2.7/site-
packages/sage/combinat/partition.py", line 4312, in _fast_iterator
new_w.sort(reverse=True)
File "/opt/sage-5.6/local/lib/python2.7/site-
packages/sage/combinat/partition.py", line 4312, in _fast_iterator
new_w.sort(reverse=True)
}}}
Whereas the generic iterator works:
{{{
sage: P = Partitions(988, max_part=1000)
sage: for p in P: print p
[988]
[987, 1]
[986, 2]
[986, 1, 1]
[985, 3]
}}}
Possible fix: either make the fast iterator non recursive, or default to
the generic iterator.
----
Apply: [attachment: trac_14094.patch], [attachment: trac_14094
-partition_iterator-review-ts.patch]
--
Comment:
Fixed:
{{{
Doctesting 1 file.
sage -t partitions.pyx
[30 tests, 1.7 s]
----------------------------------------------------------------------
All tests passed!
----------------------------------------------------------------------
Total time for all tests: 2.1 seconds
cpu time: 1.3 seconds
cumulative wall time: 1.7 seconds
}}}
For patchbot:
Apply: [attachment: trac_14094.patch], [attachment: trac_14094
-partition_iterator-review-ts.patch]
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14094#comment:9>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.
