# This program counts the number of cycles of length
# 2 in a random permutation of the numbers from 1 to
# n (here n=100). (A cycle of length 2 means that f(i)=j
# and f(j)=i, but f(i) is not equal to i.) The function
# invols counts the number of cycles of length 2. The
# function makehist runs invols several times (here 1000)
# and tabulates the results.

import random

def invols(n):
    x = range(n)
    random.shuffle(x)
    invs = 0
    for i in range(n):
        if x[i] != i and x[x[i]] == i:
            invs += 1
    return invs/2

def makehist(n,count):
    histcount = {}
    for _ in range(count):
        b = invols(n)
        if b in histcount:
            histcount[b] += 1
        else:
            histcount[b] = 1
    keys = [i for i in histcount]
    keys = sorted(keys)
    hist = [(key, histcount[key]) for key in keys]
    return hist

print makehist(100,1000)