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.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_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]]]