Permutations (Cython file)#

This is a nearly-straightforward implementation of what Knuth calls “Algorithm P” in TAOCP 7.2.1.2. The intent is to be able to enumerate permutation by “plain changes”, or multiplication by adjacent transpositions, as a generator. This is useful when a class of objects is inherently enumerated by permutations, but it is faster to swap items in a permutation than construct the next object directly from the next permutation in a list. The backtracking algorithm in sage/graphs/genus.pyx is an example of this.

The lowest level is implemented as a struct with auxiliary methods. This is because Cython does not allow pointers to class instances, so a list of these objects is inherently slower than a list of structs. The author prefers ugly code to slow code.

For those willing to sacrifice a (very small) amount of speed, we provide a class that wraps our struct.

sage.combinat.permutation_cython.left_action_product(S, lp)#

Return the permutation obtained by composing a permutation S with a permutation lp in such an order that lp is applied first and S is applied afterwards.

EXAMPLES:

sage: p = [2,1,3,4]
sage: q = [3,1,2]
sage: from sage.combinat.permutation_cython import left_action_product
sage: left_action_product(p, q)
[3, 2, 1, 4]
sage: left_action_product(q, p)
[1, 3, 2, 4]
sage: q
[3, 1, 2]

sage.combinat.permutation_cython.left_action_same_n(S, lp)#

Return the permutation obtained by composing a permutation S with a permutation lp in such an order that lp is applied first and S is applied afterwards and S and lp are of the same length.

EXAMPLES:

sage: p = [2,1,3]
sage: q = [3,1,2]
sage: from sage.combinat.permutation_cython import left_action_same_n
sage: left_action_same_n(p, q)
[3, 2, 1]
sage: left_action_same_n(q, p)
[1, 3, 2]

sage.combinat.permutation_cython.map_to_list(l, values, n)#

Build a list by mapping the array l using values.

Warning

There is no check of the input data at any point. Using wrong types or values with wrong length is likely to result in a Sage crash.

INPUT:

l – array of unsigned int (i.e., type 'I')
values – tuple; the values of the permutation
n – int; the length of the array l

OUTPUT:

A list representing the permutation.

EXAMPLES:

sage: from array import array
sage: from sage.combinat.permutation_cython import map_to_list
sage: l = array('I', [0, 1, 0, 3, 3, 0, 1])
sage: map_to_list(l, ('a', 'b', 'c', 'd'), 7)
['a', 'b', 'a', 'd', 'd', 'a', 'b']

sage.combinat.permutation_cython.next_perm(l)#

Obtain the next permutation under lex order of l by mutating l.

Algorithm based on: http://marknelson.us/2002/03/01/next-permutation/

INPUT:

l – array of unsigned int (i.e., type 'I')

Warning

This method mutates the array l.

OUTPUT:

boolean; whether another permutation was obtained

EXAMPLES:

sage: from sage.combinat.permutation_cython import next_perm
sage: from array import array
sage: L = array('I', [1, 1, 2, 3])
sage: while next_perm(L):
....:     print(L)
array('I', [1, 1, 3, 2])
array('I', [1, 2, 1, 3])
array('I', [1, 2, 3, 1])
array('I', [1, 3, 1, 2])
array('I', [1, 3, 2, 1])
array('I', [2, 1, 1, 3])
array('I', [2, 1, 3, 1])
array('I', [2, 3, 1, 1])
array('I', [3, 1, 1, 2])
array('I', [3, 1, 2, 1])
array('I', [3, 2, 1, 1])

sage.combinat.permutation_cython.permutation_iterator_transposition_list(n)#

Returns a list of transposition indices to enumerate the permutations on \(n\) letters by adjacent transpositions. Assumes zero-based lists. We artificially limit the argument to \(n < 12\) to avoid overflowing 32-bit pointers. While the algorithm works for larger \(n\), the user is encouraged to avoid filling anything more than 4GB of memory with the output of this function.

EXAMPLES:

sage: import sage.combinat.permutation_cython
sage: from sage.combinat.permutation_cython import permutation_iterator_transposition_list
sage: permutation_iterator_transposition_list(4)
[2, 1, 0, 2, 0, 1, 2, 0, 2, 1, 0, 2, 0, 1, 2, 0, 2, 1, 0, 2, 0, 1, 2]
sage: permutation_iterator_transposition_list(200)
Traceback (most recent call last):
...
ValueError: Cowardly refusing to enumerate the permutations on more than 12 letters.
sage: permutation_iterator_transposition_list(1)
[]

sage: # Generate the permutations of [1,2,3,4] fixing 4.
sage: Q = [1,2,3,4]
sage: L = [copy(Q)]
sage: for t in permutation_iterator_transposition_list(3):
....:     Q[t], Q[t+1] = Q[t+1], Q[t]
....:     L.append(copy(Q))
sage: print(L)
[[1, 2, 3, 4], [1, 3, 2, 4], [3, 1, 2, 4], [3, 2, 1, 4], [2, 3, 1, 4], [2, 1, 3, 4]]

sage.combinat.permutation_cython.right_action_product(S, rp)#

Return the permutation obtained by composing a permutation S with a permutation rp in such an order that S is applied first and rp is applied afterwards.

EXAMPLES:

sage: p = [2,1,3,4]
sage: q = [3,1,2]
sage: from sage.combinat.permutation_cython import right_action_product
sage: right_action_product(p, q)
[1, 3, 2, 4]
sage: right_action_product(q, p)
[3, 2, 1, 4]
sage: q
[3, 1, 2]

sage.combinat.permutation_cython.right_action_same_n(S, rp)#

Return the permutation obtained by composing a permutation S with a permutation rp in such an order that S is applied first and rp is applied afterwards and S and rp are of the same length.

EXAMPLES:

sage: p = [2,1,3]
sage: q = [3,1,2]
sage: from sage.combinat.permutation_cython import right_action_same_n
sage: right_action_same_n(p, q)
[1, 3, 2]
sage: right_action_same_n(q, p)
[3, 2, 1]