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

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.linear_extension_iterator(D)

Iterate over the linear extensions of the poset.

The list _le keeps track of the current linear extensions. The boolean variable is_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 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)
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]]]