Skip to content

Instantly share code, notes, and snippets.

@zahlenteufel
Created June 4, 2015 02:53
Show Gist options
  • Save zahlenteufel/96a78da8b96349dd67e1 to your computer and use it in GitHub Desktop.
Save zahlenteufel/96a78da8b96349dd67e1 to your computer and use it in GitHub Desktop.
Implementation of Fraenkel's "Error-Correcting-Code using Combinatorial Games"
# 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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment