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()