Cycle-leader in-place permutation in Python
Apply a permutation in O(n) time and O(1) extra space by following its cycles.
- File
cycle_leader_permutation.py, 60 lines- Level
- I0 not checked yet
- Toolchain
- Python 3.14, pytest 9
- Test framework
- pytest
- Run the tests
python3 -m pytest
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/cycle-leader-permutation/. The authors are listed in prov/J8DYW4.jsonl.
from typing import MutableSequence, Sequence, TypeVar
T = TypeVar("T")
def apply_permutation(a: MutableSequence[T], p: MutableSequence[int]) -> MutableSequence[T]:
"""Move a[i] to position p[i] in place, for a permutation p of 0..n-1.
p is marked by bitwise complement while the cycles are moved and is
restored before returning.
"""
n = len(a)
if len(p) != n:
raise ValueError("a and p must have the same length")
for i in range(n): # @line L1
if p[i] >= 0: # @line L2
x, j = a[i], p[i] # @line L3
while j != i: # @line L4
x, a[j] = a[j], x # @line L5
k = p[j] # @line L6
p[j] = ~p[j]
j = k
a[i] = x # @line L7
p[i] = ~p[i]
for i in range(n): # @line L8
p[i] = ~p[i]
return a # @line L9
def apply_permutation_readonly(a: MutableSequence[T], p: Sequence[int]) -> MutableSequence[T]:
"""Move a[i] to position p[i] in place without writing p."""
n = len(a)
if len(p) != n:
raise ValueError("a and p must have the same length")
for i in range(n): # @line L10
j = p[i] # @line L11
while j > i:
j = p[j]
if j == i: # @line L12
x, j = a[i], p[i] # @line L13
while j != i: # @line L14
x, a[j] = a[j], x
j = p[j]
a[i] = x # @line L15
return a # @line L16
def leader_reads(p: Sequence[int]) -> int:
"""Number of reads of p made by the leader test of apply_permutation_readonly."""
total = 0
for i in range(len(p)):
j = p[i]
total += 1
while j > i:
j = p[j]
total += 1
return total
test_cycle_leader_permutation.py 80 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/cycle-leader-permutation/. The authors are listed in prov/J8DYW4.jsonl.
import itertools
import math
import random
from fractions import Fraction
from cycle_leader_permutation import apply_permutation, apply_permutation_readonly, leader_reads
def brute(a: list, p: list[int]) -> list:
b = [None] * len(a)
for i, x in enumerate(a):
b[p[i]] = x
return b
def test_example() -> None:
p = [2, 5, 3, 0, 4, 1] # 3 6 4 1 5 2 in 1-based form
a = list("ABCDEF")
assert apply_permutation(a, p) == list("DFACEB")
assert p == [2, 5, 3, 0, 4, 1]
a = list("ABCDEF")
assert apply_permutation_readonly(a, p) == list("DFACEB")
assert leader_reads(p) == 10
def test_edges() -> None:
assert apply_permutation([], []) == []
assert apply_permutation_readonly([], []) == []
assert apply_permutation([7], [0]) == [7]
assert apply_permutation([1, 2, 3], [0, 1, 2]) == [1, 2, 3]
assert apply_permutation([1, 2, 3], [2, 1, 0]) == [3, 2, 1]
assert apply_permutation(["x", "x", "y"], [1, 2, 0]) == ["y", "x", "x"]
try:
apply_permutation([1, 2], [0])
except ValueError:
pass
else:
raise AssertionError
def test_scatter_not_gather() -> None:
p = [1, 2, 0]
assert apply_permutation(list("abc"), p) == ["c", "a", "b"]
def test_exhaustive_small() -> None:
for n in range(7):
a0 = list(range(100, 100 + n))
for q in itertools.permutations(range(n)):
p = list(q)
want = brute(a0, p)
assert apply_permutation(list(a0), p) == want
assert p == list(q)
assert apply_permutation_readonly(list(a0), p) == want
def test_leader_cost() -> None:
for n in range(1, 8):
h = sum(Fraction(1, k) for k in range(1, n + 1))
reads = [leader_reads(list(q)) for q in itertools.permutations(range(n))]
assert Fraction(sum(reads), math.factorial(n)) == (n + 1) * h - n
assert max(reads) == n * (n + 1) // 2
assert leader_reads([(i + 1) % n for i in range(n)]) == n * (n + 1) // 2
def test_random() -> None:
rng = random.Random(8803)
for _ in range(600):
n = rng.randint(0, 60)
p = list(range(n))
rng.shuffle(p)
a = [rng.randint(-5, 5) for _ in range(n)]
want = brute(a, p)
q = list(p)
assert apply_permutation(list(a), q) == want
assert q == p
assert apply_permutation_readonly(list(a), p) == want
What the next level needs
- the tests did not run in this build