new iterators over the partitions of an integer

[dcoudert]

trafficstars

As discussed in #37977, we implement new iterators over the partitions of an integer to get iterators generating partitions in increasing/decreasing lexicographic orders with partitions in ascending/descending orders. We also implement methods yielding the next partition in a specific ordering.

:memo: Checklist

• [x] The title is concise and informative.
• [x] The description explains in detail what this PR is about.
• [x] I have linked a relevant issue or discussion.
• [x] I have created tests covering the changes.
• [x] I have updated the documentation and checked the documentation preview.

:hourglass: Dependencies

[dcoudert]

The fastest is AccelAsc, but the difference is small.

sage: from sage.combinat.partitions import ZS1_iterator, ZS2_iterator, AccelDesc_iterator, AccelAsc_iterator
sage: %timeit sum(1 for _ in ZS1_iterator(10))
10.8 µs ± 29.4 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
sage: %timeit sum(1 for _ in ZS2_iterator(10))
12 µs ± 108 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
sage: %timeit sum(1 for _ in AccelDesc_iterator(10))
10.9 µs ± 7.62 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
sage: %timeit sum(1 for _ in AccelAsc_iterator(10))
10.8 µs ± 73.1 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
sage:
sage: %timeit sum(1 for _ in ZS1_iterator(50))
47.8 ms ± 393 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
sage: %timeit sum(1 for _ in ZS2_iterator(50))
52.1 ms ± 61.6 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
sage: %timeit sum(1 for _ in AccelDesc_iterator(50))
47.4 ms ± 45.1 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
sage: %timeit sum(1 for _ in AccelAsc_iterator(50))
46.4 ms ± 44.8 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

[github-actions[bot]]

Documentation preview for this PR (built with commit c5c4a3e4d1fb35776884fbaab1c338bd95fd4140; changes) is ready! :tada: This preview will update shortly after each push to this PR.

[dimpase]

linting errors?

[dcoudert]

At least it seems like we should not use ZS2 over AccelAsc for increasing lex iteration by default. I am not opposed to keeping both implementations with some test for a sufficiently large n (say, between 50 and 100) showing the outputs are equal at every step.

The orderings are not the same. Both generate partitions in lexicographic order, but the partitions of ZS2 are in descending order while the partitions of AccelAsc are in ascending order. So both might be of interest for some users.

I think we should add a prev method to partitions as well.

done.

[dcoudert]

Thanks for the comments.

[tscrim]

The bot is showing some failures:

sage -t --long --random-seed=286735480429121101562228604801325644303 src/sage/groups/misc_gps/argument_groups.py  # 6 doctests failed
sage -t --long --random-seed=286735480429121101562228604801325644303 src/sage/interfaces/gp.py  # 1 doctest failed
sage -t --long --random-seed=286735480429121101562228604801325644303 src/sage/libs/pari/tests.py  # 2 doctests failed
sage -t --long --random-seed=286735480429121101562228604801325644303 src/sage/rings/lazy_series_ring.py  # 2 doctests failed
sage -t --long --random-seed=286735480429121101562228604801325644303 src/sage/rings/lazy_series.py  # 2 doctests failed
sage -t --long --random-seed=286735480429121101562228604801325644303 src/sage/rings/padics/padic_generic_element.pyx  # 2 doctests failed
sage -t --long --random-seed=286735480429121101562228604801325644303 src/sage/rings/qqbar.py  # 1 doctest failed
sage -t --long --random-seed=286735480429121101562228604801325644303 src/sage/stats/basic_stats.py  # 2 doctests failed

I am not sure how many of them are real failures due to the changes here. Some seem unrelated from the log.

[dcoudert]

This seems unrelated. On my side, I don't observe these errors. I only see 1 warning

sage -t --long --warn-long 25.3 --random-seed=286735480429121101562228604801325644303 src/sage/interfaces/gp.py
**********************************************************************
File "src/sage/interfaces/gp.py", line 799, in sage.interfaces.gp.Gp.new_with_bits_prec
Warning: Variable 'pi_def' referenced here was set only in doctest marked '# needs sage.libs.pari sage.symbolic'
    pi_def.precision()
    [157 tests, 2.40 s]

[dcoudert]

Thank you for the review.