Permutations (Cython file)¶
This is a nearlystraightforward 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 permutationlp
in such an order thatlp
is applied first andS
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 permutationlp
in such an order thatlp
is applied first andS
is applied afterwards andS
andlp
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
usingvalues
.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 permutationn
– int; the length of the arrayl
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 mutatingl
.Algorithm based on: http://marknelson.us/2002/03/01/nextpermutation/
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', [1L, 1L, 3L, 2L]) array('I', [1L, 2L, 1L, 3L]) array('I', [1L, 2L, 3L, 1L]) array('I', [1L, 3L, 1L, 2L]) array('I', [1L, 3L, 2L, 1L]) array('I', [2L, 1L, 1L, 3L]) array('I', [2L, 1L, 3L, 1L]) array('I', [2L, 3L, 1L, 1L]) array('I', [3L, 1L, 1L, 2L]) array('I', [3L, 1L, 2L, 1L]) array('I', [3L, 2L, 1L, 1L])

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 zerobased lists. We artificially limit the argument to \(n < 12\) to avoid overflowing 32bit 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 permutationrp
in such an order thatS
is applied first andrp
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 permutationrp
in such an order thatS
is applied first andrp
is applied afterwards andS
andrp
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]