Implementation of Fraenkel's "Error-Correcting-Code using Combinatorial Games"

LinCod.py

# 1) for m in 0..n compute g_s(z_m) = mex{g(Z_i_1) xor ... xor g(z_i_j) : 0 <= i_1 < .. < i_j < m, j <=s}
import itertools
import operator

n = 8
s = 3 # s = d - 2

def pack(idxs, n):
	return [int(i in idxs) for i in xrange(n)]

def vectors(n, maxOnes):
	for i in xrange(maxOnes + 1):
		for ones in itertools.combinations(range(n), i):
			yield pack(ones, n)

def followers(i, s):
	return vectors(i, s)

def mex(c):
	m = 0
	while m in c:
		m += 1
	return m

def decompose(e):
	return [len(e)-1-i for i in xrange(len(e)) if e[i]]

def xor(c):
	return reduce(operator.xor, c, 0)

def g(u):
	# g(a xor b xor c) = g(a) xor g(b) xor g(c)
	return xor([G[i] for i in decompose(u)])

G = [0] * (n + 1)
for i in xrange(1, n+1):
	G[i] = mex(map(g, followers(i, s)))

def isPowOf2(n):
	return n & (n-1) == 0

seeds = [i for i in xrange(len(G)) if not isPowOf2(G[i])]

# 2) Compute a basis member of P for each seed

def basisMember(seed):
	return pack([0] + [i for i in xrange(seed) if isPowOf2(G[i]) and G[i] & G[seed]], n)

base = [basisMember(seed) for seed in seeds]

print base