Discrete helpers/perm
perm |
This class implements permutations of the non-negative integers.
finite permutations
editfrom 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
editinversions
editSee 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
editThe 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
editThe usual cycle notation of a permutation as a list of lists.
assert perm.cycles == [[0, 1, 2], [4, 5]]
cycle partition |
---|
from discretehelpers.set_part import SetPart
assert perm.cycle_partition == perm.inverse.cycle_partition == SetPart([[0, 1, 2], [4, 5]])
|
order
editSmallest 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
editParity 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
editPeriodic permutation derived from a finite one. See Schoute permutation.
example |
---|
assert Perm([2, 1, 0]).schoute_perm == Perm([[1, 4], [3, 6]], perilen=8)
|
methods
editsequence
editThe 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
editThe 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
editA 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.