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 permutation lp in such an order that lp is applied first and S is applied afterwards.

See also

sage.combinat.permutation.Permutation.left_action_product()

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]

p = [2,1,3,4]
q = [3,1,2]
from sage.combinat.permutation_cython import left_action_product
left_action_product(p, q)
left_action_product(q, p)
q
sage.combinat.permutation_cython.left_action_same_n(S, lp)[source]

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.

See also

sage.combinat.permutation.Permutation.left_action_product()

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]

p = [2,1,3]
q = [3,1,2]
from sage.combinat.permutation_cython import left_action_same_n
left_action_same_n(p, q)
left_action_same_n(q, p)
sage.combinat.permutation_cython.map_to_list(l, values, n)[source]

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 – integer; the length of the array l

OUTPUT: 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']

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

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])

>>> 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])

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

Return 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]]

import sage.combinat.permutation_cython
from sage.combinat.permutation_cython import permutation_iterator_transposition_list
permutation_iterator_transposition_list(4)
permutation_iterator_transposition_list(200)
permutation_iterator_transposition_list(1)
# Generate the permutations of [1,2,3,4] fixing 4.
Q = [1,2,3,4]
L = [copy(Q)]
for t in permutation_iterator_transposition_list(3):
    Q[t], Q[t+1] = Q[t+1], Q[t]
    L.append(copy(Q))
print(L)
sage.combinat.permutation_cython.right_action_product(S, rp)[source]

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.

See also

sage.combinat.permutation.Permutation.right_action_product()

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]

p = [2,1,3,4]
q = [3,1,2]
from sage.combinat.permutation_cython import right_action_product
right_action_product(p, q)
right_action_product(q, p)
q
sage.combinat.permutation_cython.right_action_same_n(S, rp)[source]

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.

See also

sage.combinat.permutation.Permutation.right_action_product()

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]

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