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 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/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', [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 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 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]