Iterators over the partitions of an integer#

AUTHOR:

  • William Stein (2007-07-28): initial version

  • Jonathan Bober (2007-07-28): wrote the program partitions_c.cc that does all the actual heavy lifting.

sage.combinat.partitions.ZS1_iterator(n)#

A fast iterator for the partitions of n (in the decreasing lexicographic order) which returns lists and not objects of type Partition.

This is an implementation of the ZS1 algorithm found in [ZS98].

REFERENCES:

[ZS98]

Antoine Zoghbi, Ivan Stojmenovic, Fast Algorithms for Generating Integer Partitions, Intern. J. Computer Math., Vol. 70., pp. 319–332. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.42.1287

EXAMPLES:

sage: from sage.combinat.partitions import ZS1_iterator
sage: it = ZS1_iterator(4)
sage: next(it)
[4]
sage: type(_)
<class 'list'>
sage.combinat.partitions.ZS1_iterator_nk(n, k)#

An iterator for the partitions of n of length at most k (in the decreasing lexicographic order) which returns lists and not objects of type Partition.

The algorithm is a mild variation on ZS1_iterator(); I would not vow for its speed.

EXAMPLES:

sage: from sage.combinat.partitions import ZS1_iterator_nk
sage: it = ZS1_iterator_nk(4, 3)
sage: next(it)
[4]
sage: type(_)
<class 'list'>