half.py

import sys

cases = 0
average = []

def isortSteps(a):
    v = []
    for i in range(len(a)):
        v.append(a[i])
    steps = 0
    for i in range(1,len(v)):
        x = v[i]
        j = i-1
        while (j > -1) and (v[j] > x):
            v[j+1] = v[j]
            j = j -1
            steps = steps + 3
        steps = steps + 1
        v[j+1] = x
        steps = steps + 4
    steps = steps + 1
    return steps

def swap(lst, i, j):
    t = lst[i]
    lst[i] = lst[j]
    lst[j] = t
    return lst

def perm(lst,i,n):
    j = 0
    if i == n:
        global cases
        cases += 1
        #print "perm("+str(cases)+"): "
        #print lst
        steps = isortSteps(lst)
        #print "steps: " + str(steps)
        global average
        average.append(steps)
    else:
        for j in range(i,n):
            swap (lst, i, j);
            perm (lst, i+1, n);
            swap (lst, i, j);

def average_steps():
    global average
    sum = 0
    prob_n = 1.0/(2.0*(len(average)-1))
    for i in range(len(average)):
        if i == 0:
            sum += average[i]*0.5
        else:
            sum += average[i]*prob_n
    print "promedio: " + str(sum)

def half_prob(n):
    v = range(1,n+1);
    l = len(v)			
    perm(v,0,l);
    average_steps()

half_prob(int(sys.argv[1]))