#!/usr/bin/env python
def swap(a, src, dst):
a[src], a[dst] = a[dst], a[src]
# =============================================================================
def PermuteWithAll(array, randoms_sequence=None):
# take swap target index with equal probability in the range 0..N
a = array[:]
for i in range(len(a)):
dest = randoms_sequence[i] if randoms_sequence else randrange(len(a))
swap(a, i, dest)
return a
# =============================================================================
def flatten(nested):
flat = []
for el in nested:
if type(el) is list:
flat.extend( flatten(el) )
else:
flat.append( el )
return flat
# =============================================================================
# Plots a two-dimensional matrix
def plot_nice_matrix(xy, a, denominator=1):
from matplotlib.backends.backend_gtkcairo import FigureCanvasGTKCairo as FigureCanvas
from matplotlib import mpl
from matplotlib.figure import Figure, SubplotParams
from matplotlib.ticker import FormatStrFormatter, FixedLocator
normalized = [[x/float(denominator) for x in row] for row in a]
z = flatten(normalized)
x = xy*len(xy)
y = flatten([[i]*len(xy) for i in xy])
sizes = [400*q for q in z] # The matplotlib documentation says that the "size" values are in units of points^2
f = Figure(figsize=(4, 3), dpi=100, subplotpars=SubplotParams(bottom=0.2, left=0.15, top=0.85, right=0.8))
main_axis = f.add_subplot(111)
scatter2 = main_axis.scatter(x, y, s=sizes, c=z, cmap=mpl.cm.RdBu)
main_axis.set_xlim(-1, len(xy))
main_axis.set_ylim(-1, len(xy))
main_axis.invert_yaxis()
for i, row in enumerate(a):
for j, col in enumerate(row):
main_axis.text(j, i + 0.5,
"%.1f%%" % (100*row[j]/float(denominator)),
verticalalignment='center',
horizontalalignment='center',
fontsize=4.5)
cb = f.colorbar(scatter2, orientation="vertical")
cb.set_label("Probability")
main_axis.set_xlabel("Randomized Position")
main_axis.set_ylabel("Original Position")
main_axis.grid(True, color='#AAAAAA')
main_axis.xaxis.set_major_formatter( FormatStrFormatter("%d") )
main_axis.xaxis.set_major_locator( FixedLocator(xy) )
main_axis.yaxis.set_major_formatter( FormatStrFormatter("%d") )
main_axis.yaxis.set_major_locator( FixedLocator(xy) )
f.suptitle( '"Permute-With-All" Order Bias' )
chart_title = "probabilities" + str( len(xy) )
FigureCanvas( f ).print_figure(chart_title + ".svg", format="svg", transparent=True)
# =============================================================================
def position_frequency_matrix(a, permutation_bins):
# Initialize a zeroed 2D array
probabilities = [[0 for i in range(len(a))] for j in range(len(a))]
for sequence, count in permutation_bins.items():
for new_position, original_position in enumerate(sequence):
probabilities[original_position][new_position] += count
return probabilities
# =============================================================================
if __name__ == "__main__":
from collections import defaultdict
import itertools
for length in range(2, 8):
A = range(length)
print A
permutation_bins = defaultdict(int)
for random_number_sequence in itertools.product(A, repeat=len(A)):
permutation_bins[tuple(PermuteWithAll(A, random_number_sequence))] += 1
probabilities = position_frequency_matrix(A, permutation_bins)
denominator = len(A)**len(A)
plot_nice_matrix(A, probabilities, denominator)