This class implements permutations of the non-negative integers.


finite permutations

edit
 
 
 
 
 
 
from discretehelpers.perm import Perm


# sequence notation
p = Perm([1, 3, 0, 2, 4])
q = Perm([4, 3, 2, 1, 0])
r = Perm([3, 1, 4, 2, 0])
s = Perm([4, 2, 0, 3, 1])

# alternative initializations with cycles and mapping
assert p == Perm([[0, 1, 3, 2]])   == Perm({0: 1, 1: 3, 2: 0, 3: 2})
assert q == Perm([[0, 4], [1, 3]]) == Perm({0: 4, 1: 3, 3: 1, 4: 0})
assert r == Perm([[0, 3, 2, 4]])   == Perm({0: 3, 2: 4, 3: 2, 4: 0})
assert s == Perm([[0, 4, 1, 2]])   == Perm({0: 4, 1: 2, 2: 0, 4: 1})

# composition
assert q * p == r
assert p * q == s
assert p.inverse * q.inverse == r.inverse

# inverses
assert p.inverse == p ** -1 == Perm([2, 0, 3, 1, 4]) == Perm([[0, 2, 3, 1]])
assert r.inverse == r ** -1 == Perm([4, 1, 3, 0, 2]) == Perm([[0, 4, 2, 3]])
assert q.inverse == q ** -1 == q

A permutation is only determined by the moved elements. Fixed points make no difference.

assert Perm([0, 2, 1]) == Perm([0, 2, 1, 3]) == Perm([0, 2, 1, 3, 4])

The main attribute of this class is mapping. Attributes with derived information are moved and length.

perm = Perm([[0, 1, 2], [4, 5]])
assert perm.mapping == {0: 1, 1: 2, 2: 0, 4: 5, 5: 4}
assert perm.moved == {0, 1, 2, 4, 5}
assert perm.length == 6

properties

edit

inversions

edit
 
inversion set with left and right inversion counts

See Inversion (discrete mathematics).
The inversion_set is the set of places on which the values are out of order.
The left_rank is the reverse colexicographic rank. Its factoradic expression is the left inversion count.
The right_rank is the lexicographic rank. Its factoradic expression is the right inversion count.

assert perm.inversion_set == {(4, 5), (0, 2), (1, 2)}
assert perm.left_rank == 124
assert perm.right_rank == 145

inverse

edit

The product of a permutation and its inverse is the neutral permutation. (Same as exponentiation with −1.)

assert perm.inverse == Perm([[0, 2, 1], [4, 5]])
assert perm * perm.inverse == Perm()

cycles

edit

The usual cycle notation of a permutation as a list of lists.

assert perm.cycles == [[0, 1, 2], [4, 5]]

order

edit

Smallest positive exponent that produces the identity. (LCM of cycle lengths.)

parity

edit

Parity of the number of inversions. (parity of a permutation)

Schoute permutation

edit

Periodic permutation derived from a finite one. See Schoute permutation.

methods

edit

sequence

edit

The permutation can be represented by a sequence of the required length or longer.
The example perm requires length 6 or more, because the biggest moved element is 5.

sequence = [1, 2, 0, 3, 5, 4]
perm = Perm(sequence)
assert perm.sequence() == perm.sequence(6) == sequence
assert                    perm.sequence(7) == sequence + [6]

apply on vector

edit

The result of applying a permutation on a sequence in natural order looks like the inverse of the permutation.

 
assert perm.apply_on_vector(['0', '1', '2', '3', '4', '5'])      == ['2', '0', '1', '3', '5', '4']
assert perm.apply_on_vector(['0', '1', '2', '3', '4', '5', '6']) == ['2', '0', '1', '3', '5', '4', '6']

assert perm.inverse.sequence() == [2, 0, 1, 3, 5, 4]
p = Perm([3, 1, 4, 2, 0])
p.apply_on_vector(['0', '1', '2', '3', '4']) == ['4', '1', '3', '0', '2']

assert r.inverse.sequence() == [4, 1, 3, 0, 2]


periodic permutations

edit

A periodic permutation moves an infinite number of elements, but with a repeating pattern.
Most attributes are those of the smallest corresponding finite permutation. The new attribute perilen is the period length.

cycles = [[3, 4]]
p5 = Perm(cycles, 5)
p10 = Perm(cycles, 10)

For both permutations order is 2, cycles is [[3, 4]] and mapping is {3: 4, 4: 3}.
These are the results of p5.sequence(20) and p10.sequence(20):

[0, 1, 2, 4, 3, 5, 6, 7, 9, 8, 10, 11, 12, 14, 13, 15, 16, 17, 19, 18]
[0, 1, 2, 4, 3, 5, 6, 7, 8, 9, 10, 11, 12, 14, 13, 15, 16, 17, 18, 19]

cycles_dynamic is a method only for periodic permutations, and shows the cycles for a given length:

assert p5.cycles_dynamic(20) == [[3, 4], [8, 9], [13, 14], [18, 19]]
assert p10.cycles_dynamic(20) == [[3, 4], [13, 14]]

Schoute permutations and Walsh permutations (see WalshPerm) are periodic.