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)[source]#
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]
>>> from sage.all import * >>> p = [Integer(2),Integer(1),Integer(3),Integer(4)] >>> q = [Integer(3),Integer(1),Integer(2)] >>> from sage.combinat.permutation_cython import left_action_product >>> left_action_product(p, q) [3, 2, 1, 4] >>> left_action_product(q, p) [1, 3, 2, 4] >>> q [3, 1, 2]
- sage.combinat.permutation_cython.left_action_same_n(S, lp)[source]#
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]
>>> from sage.all import * >>> p = [Integer(2),Integer(1),Integer(3)] >>> q = [Integer(3),Integer(1),Integer(2)] >>> from sage.combinat.permutation_cython import left_action_same_n >>> left_action_same_n(p, q) [3, 2, 1] >>> left_action_same_n(q, p) [1, 3, 2]
- sage.combinat.permutation_cython.map_to_list(l, values, n)[source]#
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']
>>> from sage.all import * >>> from array import array >>> from sage.combinat.permutation_cython import map_to_list >>> l = array('I', [Integer(0), Integer(1), Integer(0), Integer(3), Integer(3), Integer(0), Integer(1)]) >>> map_to_list(l, ('a', 'b', 'c', 'd'), Integer(7)) ['a', 'b', 'a', 'd', 'd', 'a', 'b']
- sage.combinat.permutation_cython.next_perm(l)[source]#
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', [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])
>>> from sage.all import * >>> from sage.combinat.permutation_cython import next_perm >>> from array import array >>> L = array('I', [Integer(1), Integer(1), Integer(2), Integer(3)]) >>> 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)[source]#
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]]
>>> from sage.all import * >>> import sage.combinat.permutation_cython >>> from sage.combinat.permutation_cython import permutation_iterator_transposition_list >>> permutation_iterator_transposition_list(Integer(4)) [2, 1, 0, 2, 0, 1, 2, 0, 2, 1, 0, 2, 0, 1, 2, 0, 2, 1, 0, 2, 0, 1, 2] >>> permutation_iterator_transposition_list(Integer(200)) Traceback (most recent call last): ... ValueError: Cowardly refusing to enumerate the permutations on more than 12 letters. >>> permutation_iterator_transposition_list(Integer(1)) [] >>> # Generate the permutations of [1,2,3,4] fixing 4. >>> Q = [Integer(1),Integer(2),Integer(3),Integer(4)] >>> L = [copy(Q)] >>> for t in permutation_iterator_transposition_list(Integer(3)): ... Q[t], Q[t+Integer(1)] = Q[t+Integer(1)], Q[t] ... L.append(copy(Q)) >>> 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)[source]#
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]
>>> from sage.all import * >>> p = [Integer(2),Integer(1),Integer(3),Integer(4)] >>> q = [Integer(3),Integer(1),Integer(2)] >>> from sage.combinat.permutation_cython import right_action_product >>> right_action_product(p, q) [1, 3, 2, 4] >>> right_action_product(q, p) [3, 2, 1, 4] >>> q [3, 1, 2]
- sage.combinat.permutation_cython.right_action_same_n(S, rp)[source]#
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]
>>> from sage.all import * >>> p = [Integer(2),Integer(1),Integer(3)] >>> q = [Integer(3),Integer(1),Integer(2)] >>> from sage.combinat.permutation_cython import right_action_same_n >>> right_action_same_n(p, q) [1, 3, 2] >>> right_action_same_n(q, p) [3, 2, 1]