Iterators over the partitions of an integer#

The iterators generate partitions in either increasing or decreasing lexicographic orders and a partition \(P\) is represented either in ascending (\(P_i \leq P_{i+1}\)) or descending (\(P_i \geq P_{i+1}\)) orders:

sage: from sage.combinat.partitions import ZS1_iterator
sage: for p in ZS1_iterator(4):
....:     print(p)
[4]
[3, 1]
[2, 2]
[2, 1, 1]
[1, 1, 1, 1]
sage: from sage.combinat.partitions import AccelDesc_iterator
sage: for p in AccelDesc_iterator(4):
....:     print(p)
[4]
[3, 1]
[2, 2]
[2, 1, 1]
[1, 1, 1, 1]
sage: from sage.combinat.partitions import ZS2_iterator
sage: for p in ZS2_iterator(4):
....:     print(p)
[1, 1, 1, 1]
[2, 1, 1]
[2, 2]
[3, 1]
[4]
sage: from sage.combinat.partitions import AccelAsc_iterator
sage: for p in AccelAsc_iterator(4):
....:     print(p)
[1, 1, 1, 1]
[1, 1, 2]
[1, 3]
[2, 2]
[4]

>>> from sage.all import *
>>> from sage.combinat.partitions import ZS1_iterator
>>> for p in ZS1_iterator(Integer(4)):
...     print(p)
[4]
[3, 1]
[2, 2]
[2, 1, 1]
[1, 1, 1, 1]
>>> from sage.combinat.partitions import AccelDesc_iterator
>>> for p in AccelDesc_iterator(Integer(4)):
...     print(p)
[4]
[3, 1]
[2, 2]
[2, 1, 1]
[1, 1, 1, 1]
>>> from sage.combinat.partitions import ZS2_iterator
>>> for p in ZS2_iterator(Integer(4)):
...     print(p)
[1, 1, 1, 1]
[2, 1, 1]
[2, 2]
[3, 1]
[4]
>>> from sage.combinat.partitions import AccelAsc_iterator
>>> for p in AccelAsc_iterator(Integer(4)):
...     print(p)
[1, 1, 1, 1]
[1, 1, 2]
[1, 3]
[2, 2]
[4]

For each of these iterators, this module also provides a next method that takes a partition as input and return the next partition in the corresponding ordering:

sage: from sage.combinat.partitions import ZS1_next
sage: ZS1_next([2, 2])
[2, 1, 1]
sage: from sage.combinat.partitions import AccelDesc_next
sage: AccelDesc_next([2, 2])
[2, 1, 1]
sage: from sage.combinat.partitions import ZS2_next
sage: ZS2_next([2, 2])
[3, 1]
sage: from sage.combinat.partitions import AccelAsc_next
sage: AccelAsc_next([2, 2])
[4]

>>> from sage.all import *
>>> from sage.combinat.partitions import ZS1_next
>>> ZS1_next([Integer(2), Integer(2)])
[2, 1, 1]
>>> from sage.combinat.partitions import AccelDesc_next
>>> AccelDesc_next([Integer(2), Integer(2)])
[2, 1, 1]
>>> from sage.combinat.partitions import ZS2_next
>>> ZS2_next([Integer(2), Integer(2)])
[3, 1]
>>> from sage.combinat.partitions import AccelAsc_next
>>> AccelAsc_next([Integer(2), Integer(2)])
[4]

It is also possible to iterate over the partitions of bounded length:

sage: from sage.combinat.partitions import ZS1_iterator_nk
sage: for p in ZS1_iterator_nk(6, 3):
....:     print(p)
[6]
[5, 1]
[4, 2]
[4, 1, 1]
[3, 3]
[3, 2, 1]
[2, 2, 2]

>>> from sage.all import *
>>> from sage.combinat.partitions import ZS1_iterator_nk
>>> for p in ZS1_iterator_nk(Integer(6), Integer(3)):
...     print(p)
[6]
[5, 1]
[4, 2]
[4, 1, 1]
[3, 3]
[3, 2, 1]
[2, 2, 2]

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.

  • David Coudert (2024-06-01): reshape method ZS1_iterator() to ease the implementation of ZS1_next() and add iterators and next methods based on ZS2, AccelAsc and AccelDesc from [ZS1998] and [KS2012].

sage.combinat.partitions.AccelAsc_iterator(n)[source]#

Return an iterator over the partitions of n.

The partitions are generated in the increasing lexicographic order and each partition is represented as a list in ascending order (i.e., \(p_i \leq p_{i+1}\)).

This is an implementation of the AccelAsc algorithm found in [KS2012].

See also

sage.combinat.partitions.ZS1_iterator()

EXAMPLES:

sage: from sage.combinat.partitions import AccelAsc_iterator
sage: for p in AccelAsc_iterator(4):
....:     print(p)
[1, 1, 1, 1]
[1, 1, 2]
[1, 3]
[2, 2]
[4]
sage: next(AccelAsc_iterator(4))
[1, 1, 1, 1]
sage: type(_)
<class 'list'>

>>> from sage.all import *
>>> from sage.combinat.partitions import AccelAsc_iterator
>>> for p in AccelAsc_iterator(Integer(4)):
...     print(p)
[1, 1, 1, 1]
[1, 1, 2]
[1, 3]
[2, 2]
[4]
>>> next(AccelAsc_iterator(Integer(4)))
[1, 1, 1, 1]
>>> type(_)
<class 'list'>
sage.combinat.partitions.AccelAsc_next(P)[source]#

Return the partition after P in the ordering of the AccelAsc algorithm.

INPUT:

  • P – a list encoding a partition of an integer \(n\) in ascending order (i.e., \(P_i \leq P_{i+1}\))

EXAMPLES:

sage: from sage.combinat.partitions import AccelAsc_next
sage: P = [1, 1, 1, 1]
sage: while P:
....:     print(P)
....:     P = AccelAsc_next(P)
[1, 1, 1, 1]
[1, 1, 2]
[1, 3]
[2, 2]
[4]

>>> from sage.all import *
>>> from sage.combinat.partitions import AccelAsc_next
>>> P = [Integer(1), Integer(1), Integer(1), Integer(1)]
>>> while P:
...     print(P)
...     P = AccelAsc_next(P)
[1, 1, 1, 1]
[1, 1, 2]
[1, 3]
[2, 2]
[4]
sage.combinat.partitions.AccelDesc_iterator(n)[source]#

Return an iterator over the partitions of n.

The partitions are generated in the increasing lexicographic order and each partition is represented as a list in descending order (i.e., \(p_i \geq p_{i+1}\)).

This is an implementation of the AccelDesc algorithm found in [KS2012].

See also

sage.combinat.partitions.ZS1_iterator()

EXAMPLES:

sage: from sage.combinat.partitions import AccelDesc_iterator
sage: for p in AccelDesc_iterator(4):
....:     print(p)
[4]
[3, 1]
[2, 2]
[2, 1, 1]
[1, 1, 1, 1]
sage: next(AccelDesc_iterator(4))
[4]
sage: type(_)
<class 'list'>

>>> from sage.all import *
>>> from sage.combinat.partitions import AccelDesc_iterator
>>> for p in AccelDesc_iterator(Integer(4)):
...     print(p)
[4]
[3, 1]
[2, 2]
[2, 1, 1]
[1, 1, 1, 1]
>>> next(AccelDesc_iterator(Integer(4)))
[4]
>>> type(_)
<class 'list'>

Check that ZS1_iterator() and AccelDesc_iterator() generate partitions in the same order:

sage: from sage.combinat.partitions import ZS1_iterator
sage: from sage.misc.prandom import randint
sage: n = randint(1, 50)
sage: all(p == q for p, q in zip(ZS1_iterator(n), AccelDesc_iterator(n)))  # long time
True

>>> from sage.all import *
>>> from sage.combinat.partitions import ZS1_iterator
>>> from sage.misc.prandom import randint
>>> n = randint(Integer(1), Integer(50))
>>> all(p == q for p, q in zip(ZS1_iterator(n), AccelDesc_iterator(n)))  # long time
True
sage.combinat.partitions.AccelDesc_next(P)[source]#

Return the partition after P in the ordering of the AccelDesc algorithm.

INPUT:

  • P – a list encoding a partition of an integer \(n\) in descending order (i.e., \(P_i \geq P_{i+1}\))

EXAMPLES:

sage: from sage.combinat.partitions import AccelDesc_iterator, AccelDesc_next
sage: P = [4]
sage: while P:
....:     print(P)
....:     P = AccelDesc_next(P)
[4]
[3, 1]
[2, 2]
[2, 1, 1]
[1, 1, 1, 1]
sage: A = [list(p) for p in Partitions(7)]
sage: all(AccelDesc_next(p) == q for p, q in zip(A, A[1:]))
True

>>> from sage.all import *
>>> from sage.combinat.partitions import AccelDesc_iterator, AccelDesc_next
>>> P = [Integer(4)]
>>> while P:
...     print(P)
...     P = AccelDesc_next(P)
[4]
[3, 1]
[2, 2]
[2, 1, 1]
[1, 1, 1, 1]
>>> A = [list(p) for p in Partitions(Integer(7))]
>>> all(AccelDesc_next(p) == q for p, q in zip(A, A[Integer(1):]))
True
sage.combinat.partitions.ZS1_iterator(n)[source]#

Return an iterator over the partitions of n.

The partitions are generated in the decreasing lexicographic order and each partition is represented as a list P in descending order (i.e., \(P_i \geq P_{i+1}\)). The method yields lists and not objects of type Partition.

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

See also

EXAMPLES:

sage: from sage.combinat.partitions import ZS1_iterator
sage: for p in ZS1_iterator(4):
....:     print(p)
[4]
[3, 1]
[2, 2]
[2, 1, 1]
[1, 1, 1, 1]
sage: next(ZS1_iterator(4))
[4]
sage: type(_)
<class 'list'>

>>> from sage.all import *
>>> from sage.combinat.partitions import ZS1_iterator
>>> for p in ZS1_iterator(Integer(4)):
...     print(p)
[4]
[3, 1]
[2, 2]
[2, 1, 1]
[1, 1, 1, 1]
>>> next(ZS1_iterator(Integer(4)))
[4]
>>> type(_)
<class 'list'>
sage.combinat.partitions.ZS1_iterator_nk(n, k)[source]#

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'>

>>> from sage.all import *
>>> from sage.combinat.partitions import ZS1_iterator_nk
>>> it = ZS1_iterator_nk(Integer(4), Integer(3))
>>> next(it)
[4]
>>> type(_)
<class 'list'>
sage.combinat.partitions.ZS1_next(P)[source]#

Return the partition after P in the ordering of the ZS1 algorithm.

INPUT:

  • P – a list encoding a partition of an integer \(n\) in descending order (i.e., \(P_i \geq P_{i+1}\))

EXAMPLES:

sage: from sage.combinat.partitions import ZS1_iterator, ZS1_next
sage: P = [4]
sage: while P:
....:     print(P)
....:     P = ZS1_next(P)
[4]
[3, 1]
[2, 2]
[2, 1, 1]
[1, 1, 1, 1]
sage: A = [list(p) for p in Partitions(7)]
sage: all(ZS1_next(p) == q for p, q in zip(A, A[1:]))
True

>>> from sage.all import *
>>> from sage.combinat.partitions import ZS1_iterator, ZS1_next
>>> P = [Integer(4)]
>>> while P:
...     print(P)
...     P = ZS1_next(P)
[4]
[3, 1]
[2, 2]
[2, 1, 1]
[1, 1, 1, 1]
>>> A = [list(p) for p in Partitions(Integer(7))]
>>> all(ZS1_next(p) == q for p, q in zip(A, A[Integer(1):]))
True
sage.combinat.partitions.ZS2_iterator(n)[source]#

Return an iterator over the partitions of n.

The partitions are generated in the increasing lexicographic order and each partition is represented as a list in descending order (i.e., \(p_i \geq p_{i+1}\)).

This is an implementation of the ZS2 algorithm found in [ZS1998].

See also

sage.combinat.partitions.ZS1_iterator()

EXAMPLES:

sage: from sage.combinat.partitions import ZS2_iterator
sage: for p in ZS2_iterator(4):
....:     print(p)
[1, 1, 1, 1]
[2, 1, 1]
[2, 2]
[3, 1]
[4]
sage: next(ZS2_iterator(4))
[1, 1, 1, 1]
sage: type(_)
<class 'list'>

>>> from sage.all import *
>>> from sage.combinat.partitions import ZS2_iterator
>>> for p in ZS2_iterator(Integer(4)):
...     print(p)
[1, 1, 1, 1]
[2, 1, 1]
[2, 2]
[3, 1]
[4]
>>> next(ZS2_iterator(Integer(4)))
[1, 1, 1, 1]
>>> type(_)
<class 'list'>
sage.combinat.partitions.ZS2_next(P)[source]#

Return the partition after P in the ordering of the ZS2 algorithm.

INPUT:

  • P – a list encoding a partition of an integer \(n\) in descending order (i.e., \(P_i \geq P_{i+1}\))

EXAMPLES:

sage: from sage.combinat.partitions import ZS2_iterator, ZS2_next
sage: P = [1, 1, 1, 1]
sage: while P:
....:     print(P)
....:     P = ZS2_next(P)
[1, 1, 1, 1]
[2, 1, 1]
[2, 2]
[3, 1]
[4]

>>> from sage.all import *
>>> from sage.combinat.partitions import ZS2_iterator, ZS2_next
>>> P = [Integer(1), Integer(1), Integer(1), Integer(1)]
>>> while P:
...     print(P)
...     P = ZS2_next(P)
[1, 1, 1, 1]
[2, 1, 1]
[2, 2]
[3, 1]
[4]