Langford Pairs – a silly hill climber

Langford pairs are sequences if numbers where each number less than n occurs twice, and each occurrence of a value (i) is separated by i other numbers. For example for n=3:

3 1 2 1 3 2

So there you go. It’s a largely theoretical problem, though I think such sequences could have practical applications. For example, say you have a black box, caesar cypher encoder. You can feed it strings and look at the output in order to determine the substitution matrix being used… However the encoder embeds the message with a random amount of padding, and randomly discards parts of you message… Feeding the encoder a Langford pair may be an efficient way to determine the substitution matrix. Once encoded you can simply see which pairs are a given distance apart, the distance gives you the symbol number…

Anyway.

This is a silly hill climber for finding Langford pairs. There are surely better algorithms for doing this, and hill climbers don’t work particularly well! (solutions were at best 1 off for langford pairs beyond n=3. But I wonder what it is about the landscape that makes hill climbers perform badly here. As it’s almost a toy problem it might be interesting to play with a little.

import random

size = 7

def langfordscore(l):
  
  score = 0

  for i in range(1,size):
    idx = []
    for j in range(len(l)):
      if(l[j] == i):
        idx.append(j)

    if (abs(idx[0]-idx[1]) != (i+1)):
      score = score+1

  return score

def swap(l):
  i = random.randint(0,len(l)-1)
  j = random.randint(0,len(l)-1)

  nl = list(l)
  nl[i] = l[j]
  nl[j] = l[i]

  return nl

langford = []

for i in range(1,size):
  langford.append(i)
  langford.append(i)

print langford

score = 1000
ittr = 0
lastmove = 0
mutrate = 0
while ((score != 0) and (ittr < 200000)):

  nlangford = swap(langford)

  for i in range(mutrate):
    nlangford = swap(nlangford)

  if (lastmove > 500):
    lastmove = 0
    mutrate = mutrate + 1
  
  if (mutrate > 5):
    mutrate = 0


  nscore = langfordscore(nlangford)
  
  if(nscore < score):
    langford = nlangford
    score = nscore
    print score
    print langford
  else:
    lastmove = lastmove + 1

  ittr = ittr + 1

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>