In [159]:
""" 
__author__ = Aziz Altowayan 
__date__   = April, 09 2014 
Title:  
    Stationary Probability Distributions (SPD) of Move-To-Front and Transposition heuristics. 
Description: 
    This listing uses the transition matrices (with case n=3) of MTF rule and Transposition rule to: 
        1. Compute the SPD "Prob(π)".
        2. Compute the expected cost of both heuristics "ec(A)".
 
# Here n = 3 is demonstrated as a file of 3 records: 
    R1 = A, R2 = B, and R3 = C with respective probabilities of a, b, and c. 
    And we have n! permutations thus 6x6 matrix. 
 
# Computing the expected cost of a heuristic(A), as: 
ec(A) = sum(Prob(π)) * sum(cost(π)), where: 
    # Prob(π): πj = sum(πi * pij)   "SPD, elements of the eigenvector of the matrix". 
    # cost(π) = sum(i * Pπ(i))      "Avg. number of comparisons required to search a record". 
""" 
 
import numpy as np 
from numpy.linalg import eig 
 
# Transition probabilities values "searching a letter". 
a, b, c = 0.6, 0.3, 0.1
 
# Move-To-Front transition matrix 
mtf = np.matrix([ 
        [a, b, c, 0, 0, 0], 
        [a, b, 0, c, 0, 0], 
        [0, 0, c, 0, a, b], 
        [0, 0, 0, c, a, b], 
        [0, b, c, 0, a, 0], 
        [a, 0, 0, c, 0, b]]) 
 
# ec(Move-To-Front) 
S, U = eig(mtf.T)   # S: eigenvalues, U: the normalized (unit "length") eigenvectors (i.e. col v[:,i] is eigenvector of w[i]) 
stationary = np.array(U[:,np.where(np.abs(S-1.) < 1e-8)[0][0]].flat) 
stationary = stationary / np.sum(stationary) 

mtf_pis, mtf_stat = [], stationary

# cost(π) = sum(Pπ(i) * i): 
print 'Move-To-Front matrix:\n', mtf, '\n\ncost(π):' 
for row in range(len(mtf)): 
    print ' ',sum( [mtf[row,[i]] * (i + 1) for i in range(len(mtf))] ), 
    mtf_pis.append( sum( [mtf[row,[i]] * (i + 1) for i in range(len(mtf))] ) )
 
# Prob(π) SPD 
print '\nProb(π):' 
for prob in stationary: 
    print ' ', prob, 
 
# Transposition Rule transition matrix 
transpos = np.matrix([ 
        [a, b, c, 0, 0, 0], 
        [a, b, 0, c, 0, 0], 
        [b, 0, a, 0, c, 0], 
        [0, a, 0, b, 0, c], 
        [0, 0, a, 0, c, b], 
        [0, 0, 0, b, a, c]]) 
 
# ec(Transposition) 
S, U = eig(transpos.T) 
stationary = np.array(U[:,np.where(np.abs(S-1.) < 1e-8)[0][0]].flat) 
stationary = stationary / np.sum(stationary) 

transpos_pis, transpos_stat = [], stationary

# cost(π) = sum(Pπ(i) * i): 
print '\n\nTransposition matrix:\n', transpos, '\n\ncost(π):' 
for row in range(len(transpos)): 
    print ' ', sum( [transpos[row,[i]] * (i + 1) for i in range(len(transpos))] ),
    transpos_pis.append( sum( [transpos[row,[i]] * (i + 1) for i in range(len(transpos))] ) )
 
# Prob(π) SPD 
print '\nProb(π):' 
for prob in stationary: 
    print ' ', prob,
Move-To-Front matrix:
[[ 0.6  0.3  0.1  0.   0.   0. ]
 [ 0.6  0.3  0.   0.1  0.   0. ]
 [ 0.   0.   0.1  0.   0.6  0.3]
 [ 0.   0.   0.   0.1  0.6  0.3]
 [ 0.   0.3  0.1  0.   0.6  0. ]
 [ 0.6  0.   0.   0.1  0.   0.3]] 

cost(π):
  1.5   1.6   5.1   5.2   3.9   2.8 
Prob(π):
  0.45   0.257142857143   0.0666666666667   0.0333333333333   0.15   0.0428571428571 

Transposition matrix:
[[ 0.6  0.3  0.1  0.   0.   0. ]
 [ 0.6  0.3  0.   0.1  0.   0. ]
 [ 0.3  0.   0.6  0.   0.1  0. ]
 [ 0.   0.6  0.   0.3  0.   0.1]
 [ 0.   0.   0.6  0.   0.1  0.3]
 [ 0.   0.   0.   0.3  0.6  0.1]] 

cost(π):
  1.5   1.6   2.6   3.0   4.1   4.8 
Prob(π):
  0.5   0.25   0.166666666667   0.0416666666667   0.0277777777778   0.0138888888889

In [160]:
""" Plotting """
import matplotlib.pyplot as plt

plt.plot(mtf_pis, 'r',label='MTF')
plt.plot(transpos_pis, 'b', label='Transposition')
plt.xlabel('permutation number')
plt.ylabel('cost(perm) ')
plt.title('Avg. cost of searching the list')
plt.legend(loc='upper left')
plt.show()

plt.plot(mtf_stat, 'r', label='MTF')
plt.plot(transpos_stat, 'b', label='Transposition')
plt.xlabel('permutation number')
plt.ylabel('Prob(perm)')
plt.title('Stationary Probability Distribution')
plt.legend(loc='upper right')
plt.show()