3348.sagews

# Setting the parameters

q=3
n=4
d=3
r=2

# Recursive function to ensure word has symbol weight at most r

def back(level):

    if level==n:
        sw_space.append(v[:])
    
    else:

        for v[level] in xrange(q):
            
            symb=v[level]
            if symbcheck[symb]==2: continue
          
            symbcheck[symb]+=1
            
            back(level+1)
            
            symbcheck[symb]-=1

# Defining the symbol weight space

sw_space=[]
v=[0 for i in xrange(n)]
symbcheck=[0 for i in xrange(q)]

back(0)

[0, 0, 1, 1] [0, 0, 1, 2] [0, 0, 2, 1] [0, 0, 2, 2] [0, 1, 0, 1] [0, 1, 0, 2] [0, 1, 1, 0] [0, 1, 1, 2] [0, 1, 2, 0] [0, 1, 2, 1] [0, 1, 2, 2] [0, 2, 0, 1] [0, 2, 0, 2] [0, 2, 1, 0] [0, 2, 1, 1] [0, 2, 1, 2] [0, 2, 2, 0] [0, 2, 2, 1] [1, 0, 0, 1] [1, 0, 0, 2] [1, 0, 1, 0] [1, 0, 1, 2] [1, 0, 2, 0] [1, 0, 2, 1] [1, 0, 2, 2] [1, 1, 0, 0] [1, 1, 0, 2] [1, 1, 2, 0] [1, 1, 2, 2] [1, 2, 0, 0] [1, 2, 0, 1] [1, 2, 0, 2] [1, 2, 1, 0] [1, 2, 1, 2] [1, 2, 2, 0] [1, 2, 2, 1] [2, 0, 0, 1] [2, 0, 0, 2] [2, 0, 1, 0] [2, 0, 1, 1] [2, 0, 1, 2] [2, 0, 2, 0] [2, 0, 2, 1] [2, 1, 0, 0] [2, 1, 0, 1] [2, 1, 0, 2] [2, 1, 1, 0] [2, 1, 1, 2] [2, 1, 2, 0] [2, 1, 2, 1] [2, 2, 0, 0] [2, 2, 0, 1] [2, 2, 1, 0] [2, 2, 1, 1]

# Defining Hamming distance

def Hamming_distance(u,v):

    count=0
    for i in xrange(n):
        if u[i]!=v[i]:
            count+=1
    return count

# Defining the symbol weight graph

sw_space=map(tuple,sw_space)
sw_graph=Graph([ssw_space,lambda u,v:Hamming_distance(u,v)>=d])

# Finding the maximum clique

K=sw_graph.clique_maximum()

print "Size of maximum clique: %d,"%len(K)
print "Maximum clique has vertices:"
for v in K: print v

Size of maximum clique: 6, Maximum clique has vertices: (0, 1, 2, 2) (1, 0, 2, 1) (1, 1, 0, 0) (1, 2, 1, 2) (2, 0, 1, 0) (2, 2, 0, 1)