ring comparison

ringcomp.py

from random import randint

def search(ringSetA, ringB, ops_count = 0):
  """
  Determines whether two rings are homomorphic in approximately linear time.
  Essentially does a prefix search over two randomly-cut rings to shrink the search
  space (i.e., possible shifts) as quickly as possible.  
  
  match: 4 4 6 2 2 1  ("ring B")
  
  over:  2 2 1 4 4 6  ("ring set A")
         2 1 4 4 6 2
         1 4 4 6 2 2   --->  4 6 2 2 1  --->  6 2 2 1  --->  2 2 1 --> 2 1 --> 1 --> true
         4 4 6 2 2 1         6 2 2 1 4
         4 6 2 2 1 4
         6 2 2 1 4 4
  """
  # constant
  if len(ringSetA[0]) != len(ringB):
    print ops_count
    return False
  # constant
  if len(ringB) == 0:
    print ops_count
    return True
  # linear
  matches = [ringSetA[ix][1:] for ix in xrange(len(ringSetA)) if ringSetA[ix][0] == ringB[0]]
  ops_count = ops_count + len(ringSetA)
  # constant
  if len(matches) == 0:
    print ops_count
    return False
  return search(matches, ringB[1:], ops_count)

def generate_matrix(ring):
  return [(ring[y:] + ring[0:y]) for y in xrange(len(ring))]

def random_ring(n = 40):
  return [randint(0,100) for n in xrange(n)]

def main():
  ringA = random_ring(n = 300)
  splice = randint(0,len(ringA) - 1)
  ringB = ringA[splice:] + ringA[0:splice] # + [2]
  
  # this is a particularly space inefficient way to do this.
  # this could be replaced by in-place scanning, with no change
  # in the time cost.  this is just simpler to implement right now
  # and you never said anything about space bounds.
  initial_set = generate_matrix(ringA)
  print search(initial_set, ringB)

if __name__ == '__main__':
  main()