View source for Discrete helpers/perm

{{dh-link|perm}}
This class implements {{w|permutation}}s of the non-negative integers. 


==finite permutations==

{|
| [[File:5-el perm; active; composition; S; prefix.svg|thumb|400px|<math>P \cdot Q = S</math>]]
| [[File:5-el perm; active; composition; R; prefix.svg|thumb|400px|<math>Q \cdot P = R</math>]]
| [[File:5-el perm; active; composition; R inv; prefix.svg|thumb|400px|<math>P^{-1} \cdot Q^{-1} = R^{-1}</math>]]
|}

<syntaxhighlight lang="python">
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
</syntaxhighlight>

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

<syntaxhighlight lang="python">
assert Perm([0, 2, 1]) == Perm([0, 2, 1, 3]) == Perm([0, 2, 1, 3, 4])
</syntaxhighlight>

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

<syntaxhighlight lang="python">
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
</syntaxhighlight>

===properties===

====inversions====
[[File:Inversions of (0, 1, 2) (4, 5).svg|thumb|inversion set with left and right inversion counts]]
<small>See [[Inversion (discrete mathematics)]].</small><br>
The <code>inversion_set</code> is the set of places on which the values are out of order.<br>
The <code>left_rank</code> is the reverse colexicographic rank. Its [[w:Factorial number system|factoradic]] expression is the left inversion count.<br>
The <code>right_rank</code> is the lexicographic rank. Its factoradic expression is the right inversion count.

<syntaxhighlight lang="python">
assert perm.inversion_set == {(4, 5), (0, 2), (1, 2)}
assert perm.left_rank == 124
assert perm.right_rank == 145
</syntaxhighlight>

====inverse====

The product of a permutation and its inverse is the neutral permutation. <small>(Same as exponentiation with &minus;1.)</small>

<syntaxhighlight lang="python">
assert perm.inverse == Perm([[0, 2, 1], [4, 5]])
assert perm * perm.inverse == Perm()
</syntaxhighlight>

====cycles====

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

<syntaxhighlight lang="python">
assert perm.cycles == [[0, 1, 2], [4, 5]]
</syntaxhighlight>

{{Collapsible START|cycle partition|collapsed light}}
<code>cycle_partition</code> is a [[w:Partition of a set|set partition]] <small>(see [[Discrete helpers/set part|SetPart]])</small>.

<syntaxhighlight lang="python">
from discretehelpers.set_part import SetPart


assert perm.cycle_partition == perm.inverse.cycle_partition == SetPart([[0, 1, 2], [4, 5]])
</syntaxhighlight>
{{Collapsible END}}

====order====

Smallest positive exponent that produces the identity. <small>([[w:Least common multiple|LCM]] of cycle lengths.)</small>

{{Collapsible START|powers|collapsed light}}
<syntaxhighlight lang="python">
for i in range(7):
    print(i, perm ** i)
</syntaxhighlight>

<pre>
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()
</pre>
{{Collapsible END}}

====parity====

Parity of the number of inversions. <small>({{w|parity of a permutation}})</small>

{{Collapsible START|parities of permutations of 4 elements|collapsed light}}
<syntaxhighlight lang="python">
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))
</syntaxhighlight>

<pre>
[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
</pre>
{{Collapsible END}}

====Schoute permutation====

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

{{Collapsible START|example|collapsed light}}
<syntaxhighlight lang="python">
assert Perm([2, 1, 0]).schoute_perm == Perm([[1, 4], [3, 6]], perilen=8)
</syntaxhighlight>

[[File:Cube permutation 0 5.svg|thumb|left|reflection of cube vertices derived from switch of horizontal and vertical axis]]
{{Collapsible END}}

===methods===

====sequence====

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

<syntaxhighlight lang="python">
sequence = [1, 2, 0, 3, 5, 4]
perm = Perm(sequence)
assert perm.sequence() == perm.sequence(6) == sequence
assert                    perm.sequence(7) == sequence + [6]
</syntaxhighlight>

====apply on vector====

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

[[File:5-el perm; active; vector; R; prefix.svg|thumb]]

<syntaxhighlight lang="python">
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]
</syntaxhighlight>

<syntaxhighlight lang="python">
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]
</syntaxhighlight>


==periodic permutations==

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

<syntaxhighlight lang="python">
cycles = [[3, 4]]
p5 = Perm(cycles, 5)
p10 = Perm(cycles, 10)
</syntaxhighlight>

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

<div style="font-family: monospace;">
[0, 1, 2, '''4''', '''3''', 5, 6, 7, '''9''', '''8''', 10, 11, 12, '''14''', '''13''', 15, 16, 17, '''19''', '''18''']<br>
[0, 1, 2, '''4''', '''3''', 5, 6, 7, 8, 9, 10, 11, 12, '''14''', '''13''', 15, 16, 17, 18, 19]
</div>

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

<syntaxhighlight lang="python">
assert p5.cycles_dynamic(20) == [[3, 4], [8, 9], [13, 14], [18, 19]]
assert p10.cycles_dynamic(20) == [[3, 4], [13, 14]]
</syntaxhighlight>

Schoute permutations and [[Walsh permutation]]s <small>(see [[Discrete helpers/walsh_perm|WalshPerm]])</small> are periodic.


[[Category:Discrete helpers (software documentation)]]