Succinct permutation representation in Python

A representation of a permutation in about n log n bits that supports both pi and its inverse quickly.

File: succinct_permutation.py, 69 lines
Level: I0 not checked yet
Toolchain: Python 3.14, pytest 9
Test framework: pytest
Run the tests: python3 -m pytest

succinct_permutation.pyRaw GitHub

# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/succinct-permutation/. The authors are listed in prov/EAVGSD.jsonl.
"""Succinct permutation with shortcuts (Munro, Raman, Raman and Rao).

pi is stored as a plain array. On every cycle longer than t, every t-th
element along the cycle is marked in a bit vector B and given a
shortcut S to the mark t steps back (or fewer, at the wrap). The
inverse is found by walking forward from i, taking one shortcut back,
and walking forward again: at most 2t + 1 evaluations of pi.
"""

from __future__ import annotations

from typing import Sequence


class SuccinctPermutation:
    """pi(i) in O(1) and pi^{-1}(i) in O(t), with about n/t extra words."""

    def __init__(self, pi: Sequence[int], t: int = 8) -> None:
        """Index the permutation ``pi`` of 0..n-1 with shortcut spacing ``t`` >= 1."""
        n = len(pi)
        if sorted(pi) != list(range(n)):
            raise ValueError("not a permutation of 0..n-1")
        self.pi = list(pi)
        self.t = t
        self.n = n
        mark = [0] * n
        back: dict[int, int] = {}
        seen = [False] * n
        for s in range(n):
            if seen[s]:
                continue
            cycle = []
            x = s
            while not seen[x]:
                seen[x] = True
                cycle.append(x)
                x = self.pi[x]
            if len(cycle) > t:
                marks = cycle[::t]
                for k, y in enumerate(marks):
                    mark[y] = 1
                    back[y] = marks[k - 1]  # k = 0 wraps to the last mark
        self.B = mark
        self.rank = [0]
        for b in mark:
            self.rank.append(self.rank[-1] + b)
        self.S = [back[y] for y in range(n) if mark[y]]  # shortcuts in rank order

    def apply(self, i: int) -> int:
        """pi(i)."""
        return self.pi[i]

    def inverse(self, i: int) -> int:
        """pi^{-1}(i), the j with pi(j) = i."""
        j, jumped = i, False  # @line L1
        nxt = self.pi[j]
        while nxt != i:  # @line L2
            if self.B[j] and not jumped:  # @line L3
                j, jumped = self.S[self.rank[j]], True
            else:  # @line L4
                j = nxt
            nxt = self.pi[j]
        return j  # @line L5

    def extra_words(self) -> int:
        """Number of shortcut entries, the main extra space."""
        return len(self.S)

test_succinct_permutation.py 77 lines

# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/succinct-permutation/. The authors are listed in prov/EAVGSD.jsonl.
"""Tests for the succinct permutation."""

from __future__ import annotations

import random
import unittest

from succinct_permutation import SuccinctPermutation

EXAMPLE = [3, 5, 7, 6, 0, 2, 1, 4, 8, 10, 9]


class CountingPerm(SuccinctPermutation):
    """Counts evaluations of pi made by inverse."""

    def inverse(self, i: int) -> int:
        pi = self.pi
        calls = [0]

        class Probe(list):
            def __getitem__(self, k):  # type: ignore[override]
                calls[0] += 1
                return list.__getitem__(self, k)

        self.pi = Probe(pi)
        try:
            r = super().inverse(i)
        finally:
            self.pi = pi
        self.last_calls = calls[0]
        return r


class TestSuccinctPermutation(unittest.TestCase):
    def test_example(self) -> None:
        p = SuccinctPermutation(EXAMPLE, t=3)
        self.assertEqual([i for i in range(11) if p.B[i]], [0, 1, 7])
        self.assertEqual(p.S, [7, 0, 1])
        self.assertEqual(p.inverse(2), 5)
        self.assertEqual(p.inverse(8), 8)
        self.assertEqual(p.inverse(9), 10)
        self.assertEqual(p.apply(2), 7)
        c = CountingPerm(EXAMPLE, t=3)
        self.assertEqual(c.inverse(2), 5)
        self.assertEqual(c.last_calls, 4)

    def test_edge(self) -> None:
        self.assertEqual(SuccinctPermutation([], t=2).n, 0)
        p = SuccinctPermutation([0], t=1)
        self.assertEqual(p.inverse(0), 0)
        with self.assertRaises(ValueError):
            SuccinctPermutation([0, 0])
        q = SuccinctPermutation([1, 2, 3, 0], t=1)
        self.assertEqual([q.inverse(i) for i in range(4)], [3, 0, 1, 2])

    def test_random(self) -> None:
        rng = random.Random(4096)
        for _ in range(600):
            n = rng.randint(1, 60)
            pi = list(range(n))
            rng.shuffle(pi)
            t = rng.randint(1, 8)
            c = CountingPerm(pi, t=t)
            inv = [0] * n
            for i, x in enumerate(pi):
                inv[x] = i
            for i in range(n):
                self.assertEqual(c.inverse(i), inv[i])
                self.assertLessEqual(c.last_calls, 2 * t + 1)
                self.assertEqual(c.apply(i), pi[i])
            self.assertLessEqual(c.extra_words(), n // t + n // (t + 1) + 1)


if __name__ == "__main__":
    unittest.main()

What the next level needs

the tests did not run in this build

Read the full page about Succinct permutation representation