Expected value of inversions.

expinv.py

#!/usr/bin/env python
# coding: utf-8

from __future__ import division
import collections
import itertools
import matplotlib.pyplot as plt

def inversions(seq):
    invs = 0
    for i, item in enumerate(seq[:-1]):
        invs += sum((1 for e in seq[i + 1:] if e < item))
    return invs

def expval(seq):
    return sum(seq) / len(seq)

def plot_inversion_count(N):
    evs = []

    for n in range(N):
        invs = []
        for p in itertools.permutations(range(n)):
            invs.append(inversions(p))
        evs.append(expval(invs))
    
    print(zip(range(N), evs))
    plt.clf()
    plt.title("expected number of inversions")
    plt.plot(range(N), evs)
    plt.grid(True)
    plt.savefig('inversions.png')

def inversion_distribution(n):
    dist = collections.defaultdict(int)
    for p in itertools.permutations(range(n)):
        dist[inversions(p)] += 1
    return dist

def plot_inv_dist(n):
    dist = inversion_distribution(n)
    X = [k for k, _ in dist.iteritems()]
    Y = [v for _, v in dist.iteritems()]

    plt.clf()
    plt.title("inversions n = %s" % n)
    plt.bar(X, Y, 1)
    plt.xticks(X)
    plt.grid(True)
    plt.tight_layout()
    plt.savefig('invdist.png')


if __name__ == '__main__':
    plot_inv_dist(8)
    plot_inversion_count(10)

invdist.png

inversions.png