#!/usr/bin/python
#Experiment to see how much the Hamming distance tells us about a string
#This does an exhaustive search on short strings to try to get a feeling for what is going on.
import math
import string
import random
import itertools
import re
#import cProfile
l=7
sigma = 4
threshold = math.pow(sigma, l/3)
assert(sigma < 10)
print "threshold, l and sigma are", threshold,l, sigma, "*\n"
alphabet = (string.digits)[0:sigma]
print "alphabet is", alphabet,"*\n"
def hamdist(str1, str2):
"""Count the # of differences between equal length strings str1 and str2"""
diffs = 0
for i in xrange(len(str1)):
if str1[i] != str2[i]:
diffs += 1
return diffs
def l1(str1, str2):
"""Compute the L1 difference between equal length strings"""
diffs = 0
for ch1, ch2 in itertools.izip(str1, str2):
diffs += math.fabs(int(ch1) - int(ch2))
return diffs
def finddists(unknown, pattern):
hds = [hamdist(unknown, pattern[i:l+i]) for i in xrange(l)]
return hds
#We are going to generate lots of short unknown strings and then iterate over all possible patterns checking to see how well we do. That's the theory.
allunknowns = [''.join(y) for y in itertools.product(alphabet, repeat = l)]
allpatterns = [''.join(y) for y in itertools.product((string.digits)[0:sigma-1], repeat = 2*l-1) if re.match('0+1.*', ''.join(y))]
random.shuffle(allpatterns)
# We want to know what the best pattern is over all unknowns
maxsofar = 0
print "Number of possible unknowns is:", len(allunknowns)
for pattern in allpatterns:
successcount = 0
for unknown in allunknowns:
stringsleft = allunknowns
dists = finddists(unknown, pattern)
for i in xrange(0,l):
stringsleft = [y for y in stringsleft if hamdist(pattern[i:i+l], y) == dists[i]]
if len(stringsleft) >threshold:
print len(stringsleft)
break
elif len(stringsleft) <= threshold:
successcount = successcount + 1
if successcount >= maxsofar:
print "Pattern", pattern, "gets score", successcount
maxsofar = successcount