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