# This program chooses a random permutation sigma of the
# numbers from 1 to n and counts the number of records 
# (i.e., values of i so that sigma(i) > sigma(j) for all
# j < i). The function makehist(n,count) runs count trials of
# the process and then tabulates the distribution. What does
# the distribution look like?

import random

def numrecords(n):
    x = range(n)
    random.shuffle(x)
    currentrecord = 0
    recordcount = 0
    for i in range(n):
        if x[i] > currentrecord:
            currentrecord = x[i]
            recordcount += 1
    return recordcount

def makehist(n, count):
    histcount = {}
    for _ in range(count):
        b = numrecords(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)