cycle_permutation.py

# this is python3
import random

# generates a cyclic permutation of length `n`
def cycle_permutation(n):
    shuffled = list(range(n))
    random.shuffle(shuffled)
    graph = {shuffled[i]: shuffled[(i+1)%n] for i in range(n)}
    return [graph[i] for i in range(n)]

# returns a set of the cycles of a permutation
def cycles(p):
    n = len(p)
    todo = set(range(n))
    cycles = set()
    while todo:
        init = todo.pop()
        # find the cycle starting at `init`
        cycle = [init]
        x = init
        while True:
            x = p[x]
            if x == init: break
            todo.remove(x)
            cycle.append(x)
        cycles.add(tuple(cycle))
    return cycles

# try running: cycles(cycle_permutation(N))
# for some positive integer N.
# it should always return a singleton set.