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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
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