Random permutations problem.

gistfile1.py

import random

def random_permutation(n):
    x = range(n)
    random.shuffle(x)
    return x


def cycle_decomposition(permutation):
    unused = set(permutation)
    cycles = []
    while len(unused) != 0:
        cur = orig = unused.pop()
        cycle = [cur]
        while permutation[cur] != orig:
            cur = permutation[cur]
            if cur in unused:
                unused.remove(cur)
            cycle.append(cur)
        cycles.append(cycle)
    return map(tuple, cycles)


print cycle_decomposition(random_permutation(100))
from collections import Counter
from pprint import pprint
pprint(sorted((x, y/1000.0) for (x,y) in Counter(max(map(len, cycle_decomposition(random_permutation(100)))) for _ in range(1000)).items()))

import numpy as np
def successes(n):
    perm = random_permutation(n)
    return sum((len(cycle) for cycle in cycle_decomposition(perm) if len(cycle) <= n/2), 0.0)


np.average([successes(100) for _ in range(10000)])