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)#

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]
sage.combinat.combinat_cython.lyndon_word_iterator(n, k)#

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]]
sage.combinat.combinat_cython.perfect_matchings_iterator(n)#

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))
[[]]

REFERENCES:

sage.combinat.combinat_cython.set_partition_composition(sp1, sp2)#

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)                # optional - sage.combinat
True