Fast computation of combinatorial functions (Cython + mpz)

Currently implemented:

  • Stirling numbers of the second kind

  • iterators for set partitions

  • iterator for Lyndon words

  • iterator for perfect matchings

  • conjugate of partitions

AUTHORS:

  • Fredrik Johansson (2010-10): Stirling numbers of second kind

  • Martin Rubey and Travis Scrimshaw (2018): iterators for set partitions, Lyndon words, and perfect matchings

sage.combinat.combinat_cython.conjugate(p)[source]

Return the conjugate partition associated to the partition p as a list.

EXAMPLES:

sage: from sage.combinat.combinat_cython import conjugate
sage: conjugate([2,2])
[2, 2]
sage: conjugate([6,3,1])
[3, 2, 2, 1, 1, 1]

>>> from sage.all import *
>>> from sage.combinat.combinat_cython import conjugate
>>> conjugate([Integer(2),Integer(2)])
[2, 2]
>>> conjugate([Integer(6),Integer(3),Integer(1)])
[3, 2, 2, 1, 1, 1]
sage.combinat.combinat_cython.lyndon_word_iterator(n, k)[source]

Generate the Lyndon words of fixed length k with n letters.

The resulting Lyndon words will be words represented as lists whose alphabet is range(n) (\(= \{0, 1, \ldots, n-1\}\)).

ALGORITHM:

The iterative FKM Algorithm 7.2 from [Rus2003].

EXAMPLES:

sage: from sage.combinat.combinat_cython import lyndon_word_iterator
sage: list(lyndon_word_iterator(4, 2))
[[0, 1], [0, 2], [0, 3], [1, 2], [1, 3], [2, 3]]
sage: list(lyndon_word_iterator(2, 4))
[[0, 0, 0, 1], [0, 0, 1, 1], [0, 1, 1, 1]]

>>> from sage.all import *
>>> from sage.combinat.combinat_cython import lyndon_word_iterator
>>> list(lyndon_word_iterator(Integer(4), Integer(2)))
[[0, 1], [0, 2], [0, 3], [1, 2], [1, 3], [2, 3]]
>>> list(lyndon_word_iterator(Integer(2), Integer(4)))
[[0, 0, 0, 1], [0, 0, 1, 1], [0, 1, 1, 1]]
sage.combinat.combinat_cython.perfect_matchings_iterator(n)[source]

Iterate over all perfect matchings with n parts.

This iterates over all perfect matchings of \(\{0, 1, \ldots, 2n-1\}\) using a Gray code for fixed-point-free involutions due to Walsh [Wal2001].

EXAMPLES:

sage: from sage.combinat.combinat_cython import perfect_matchings_iterator
sage: list(perfect_matchings_iterator(1))
[[(0, 1)]]
sage: list(perfect_matchings_iterator(2))
[[(0, 1), (2, 3)], [(0, 2), (1, 3)], [(0, 3), (1, 2)]]

sage: list(perfect_matchings_iterator(0))
[[]]

>>> from sage.all import *
>>> from sage.combinat.combinat_cython import perfect_matchings_iterator
>>> list(perfect_matchings_iterator(Integer(1)))
[[(0, 1)]]
>>> list(perfect_matchings_iterator(Integer(2)))
[[(0, 1), (2, 3)], [(0, 2), (1, 3)], [(0, 3), (1, 2)]]

>>> list(perfect_matchings_iterator(Integer(0)))
[[]]

REFERENCES:

sage.combinat.combinat_cython.set_partition_composition(sp1, sp2)[source]

Return a tuple consisting of the composition of the set partitions sp1 and sp2 and the number of components removed from the middle rows of the graph.

EXAMPLES:

sage: from sage.combinat.combinat_cython import set_partition_composition
sage: sp1 = ((1,-2),(2,-1))
sage: sp2 = ((1,-2),(2,-1))
sage: p, c = set_partition_composition(sp1, sp2)
sage: (SetPartition(p), c) == (SetPartition([[1,-1],[2,-2]]), 0)                # needs sage.combinat
True

>>> from sage.all import *
>>> from sage.combinat.combinat_cython import set_partition_composition
>>> sp1 = ((Integer(1),-Integer(2)),(Integer(2),-Integer(1)))
>>> sp2 = ((Integer(1),-Integer(2)),(Integer(2),-Integer(1)))
>>> p, c = set_partition_composition(sp1, sp2)
>>> (SetPartition(p), c) == (SetPartition([[Integer(1),-Integer(1)],[Integer(2),-Integer(2)]]), Integer(0))                # needs sage.combinat
True