conflict-free.py

#!/usr/bin/env python2.7

#conflict-free strings using python and numpy
#Marios Papachristou: [email protected]
import numpy as np
import time

def generate_conflict_free_string(n, f = lambda x: x):
	k = n / 2
	a = np.zeros(n)
	for i in range(1, n / 2):
		a[k + i] = f(i)
		a[k - i] = f(i)
	a[0] = f(k - 2)
	if n % 2 != 0:
		a[n-1] = a[0]
	return a

def generate_permutations(s):
	result = []
	k = len(s)/2
	for i in range(k):
		result.append(np.mod(s + i,k))
	return result
	
def generate_permutation_array(n, f = lambda A:A):
	S = generate_conflict_free_string(n)
	P = generate_permutations(S)
	A = np.array(map(lambda x: list(P[x].astype(int)), list(S.astype(int))))
	return f(A) 
	
if __name__ == '__main__': #an example
	N = 40
	T = []
	for x in range(N):
		t = time.time()
		A = generate_permutation_array(x+2)
		print A
		T.append(time.time() - t)
		print 'Elements: {0}, Time elapsed: {1} sec'.format(x+2, T[x])