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.linear_extension_iterator(D)#
Iterate over the linear extensions of the poset.
The list
_le
keeps track of the current linear extensions. The boolean variableis_plus
keeps track of the “sign”.INPUT:
D
, the Hasse diagram of a poset.
Warning
It is assumed that
D
is not modified while the linear extensions are generated.EXAMPLES:
sage: from sage.combinat.combinat_cython import linear_extension_iterator sage: D = Poset({ 0:[1,2], 1:[3], 2:[3,4] })._hasse_diagram sage: list(linear_extension_iterator(D)) [[0, 1, 2, 3, 4], [0, 2, 1, 3, 4], [0, 2, 1, 4, 3], [0, 2, 4, 1, 3], [0, 1, 2, 4, 3]] sage: D = posets.BooleanLattice(3)._hasse_diagram sage: len(list(linear_extension_iterator(D))) 48 sage: D = posets.AntichainPoset(9)._hasse_diagram sage: len(list(linear_extension_iterator(D))) == factorial(9) # long time True
- sage.combinat.combinat_cython.lyndon_word_iterator(n, k)#
Generate the Lyndon words of fixed length
k
withn
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
andsp2
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) True
- sage.combinat.combinat_cython.set_partition_iterator(base_set)#
A fast iterator for the set partitions of the base set, which returns lists of lists instead of set partitions types.
EXAMPLES:
sage: from sage.combinat.combinat_cython import set_partition_iterator sage: list(set_partition_iterator([1,-1,x])) [[[1, -1, x]], [[1, -1], [x]], [[1, x], [-1]], [[1], [-1, x]], [[1], [-1], [x]]]
- sage.combinat.combinat_cython.set_partition_iterator_blocks(base_set, k)#
A fast iterator for the set partitions of the base set into the specified number of blocks, which returns lists of lists instead of set partitions types.
EXAMPLES:
sage: from sage.combinat.combinat_cython import set_partition_iterator_blocks sage: list(set_partition_iterator_blocks([1,-1,x], 2)) [[[1, x], [-1]], [[1], [-1, x]], [[1, -1], [x]]]