Find connected components in a set of cycles, then print the corresponding cycle decomposition.

cycle-decomposition.py

from typing import Dict, Iterator, List, Set

# Type aliases...if Python 3.10+, then declare them as such. ;-)
Cycle = List[int]
CycleDecomposition = List[Cycle]
Permutation = Dict[int, int]
# Another reasonable (and more compact) structure is an array,
# but this helps keep the one-indexing and lets you sub in other graph types.


def wcc_cycle_decomposition(s: Permutation) -> CycleDecomposition:
    """Find weakly connected components of permutation to decompose into cycles."""
    visited: Set[int] = set()

    def visit_next_element(e: int) -> int:
        """e ↦ σ(e) with bookkeeping."""
        visited.add(e)  # Record that you've moved on in life.
        return s[e]

    def walk(starting_point: int) -> Iterator[int]:
        """Generate the cycle accessible from this point: e, σ(e), σ(σ(e)), …."""
        # Using loop-and-a-half to check sentinel value.
        current_element = starting_point
        while True:  # Horrible, horrible code smell...
            yield current_element
            current_element = visit_next_element(current_element)
            if current_element == starting_point:
                break

    def get_next_cycle() -> Iterator[Cycle]:
        """Yield each next cycle in turn."""
        # Refers to `s` and `visited` from outer scope.
        for element in s:
            if element not in visited:
                this_cycle = list(walk(element))

                yield this_cycle

    result = list(get_next_cycle())  # Consume the generator.

    pruned_result = [
        x for x in result if len(x) > 1
    ]  # By convention, cycles of length 1 are not written.
    return pruned_result


def format_nicely(decomp: CycleDecomposition) -> str:
    def format_one_cycle(c: Cycle) -> str:
        return f"({' '.join(str(i) for i in c)})"

    return " ".join(format_one_cycle(c) for c in decomp)


if __name__ == "__main__":
    n = 13  # Size of the set Ω.
    # fmt: off
    S_13: Permutation = {
        1: 12, 2: 13, 3: 3,  4: 1, 5: 11, 6: 9,
        7: 5,  8: 10, 9: 6, 10: 4, 11: 7, 12: 8,
        13: 2,
    }  # An example permutation of Ω defined in the book.
    # fmt: on

    # Make sure the example is valid.
    assert len(S_13) == n
    assert set(S_13.keys()) == set(S_13.values())

    # Decompose and format nicely!
    decomp = wcc_cycle_decomposition(S_13)
    print(format_nicely(decomp))