Discrete helpers/perm

perm

This class implements permutations of the non-negative integers.

finite permutations

$P\cdot Q=S$

$Q\cdot P=R$

$P^{-1}\cdot Q^{-1}=R^{-1}$

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

inversions

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

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

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

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

cycle partition
cycle_partition is a set partition (see SetPart). from discretehelpers.set_part import SetPart assert perm.cycle_partition == perm.inverse.cycle_partition == SetPart([[0, 1, 2], [4, 5]])

order

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

powers
for i in range(7): print(i, perm ** i) 0 Perm() 1 Perm([[0, 1, 2], [4, 5]]) 2 Perm([[0, 2, 1]]) 3 Perm([[4, 5]]) 4 Perm([[0, 1, 2]]) 5 Perm([[0, 2, 1], [4, 5]]) 6 Perm()

parity

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

parities of permutations of 4 elements

for i in range(24): if i % 6 == 0: print('') perm = int_to_perm(i) print(perm.sequence(4), '|', perm.parity, '|', len(perm.inversion_set)) [0, 1, 2, 3] | 0 | 0 [1, 0, 2, 3] | 1 | 1 [0, 2, 1, 3] | 1 | 1 [2, 0, 1, 3] | 0 | 2 [1, 2, 0, 3] | 0 | 2 [2, 1, 0, 3] | 1 | 3 [0, 1, 3, 2] | 1 | 1 [1, 0, 3, 2] | 0 | 2 [0, 3, 1, 2] | 0 | 2 [3, 0, 1, 2] | 1 | 3 [1, 3, 0, 2] | 1 | 3 [3, 1, 0, 2] | 0 | 4 [0, 2, 3, 1] | 0 | 2 [2, 0, 3, 1] | 1 | 3 [0, 3, 2, 1] | 1 | 3 [3, 0, 2, 1] | 0 | 4 [2, 3, 0, 1] | 0 | 4 [3, 2, 0, 1] | 1 | 5 [1, 2, 3, 0] | 1 | 3 [2, 1, 3, 0] | 0 | 4 [1, 3, 2, 0] | 0 | 4 [3, 1, 2, 0] | 1 | 5 [2, 3, 1, 0] | 1 | 5 [3, 2, 1, 0] | 0 | 6

Schoute permutation

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

example
assert Perm([2, 1, 0]).schoute_perm == Perm([[1, 4], [3, 6]], perilen=8) reflection of cube vertices derived from switch of horizontal and vertical axis

methods

sequence

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

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

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.