#!/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)