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 auxilliary 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
Swith a permutationlpin such an order thatlpis applied first andSis 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
Swith a permutationlpin such an order thatlpis applied first andSis applied afterwards andSandlpare 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.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
Swith a permutationrpin such an order thatSis applied first andrpis 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
Swith a permutationrpin such an order thatSis applied first andrpis applied afterwards andSandrpare 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]