Introduction

In 1958, the mathematician C.D. Langford was watching his son play with blocks. He wrote:

There were two of each color, and one day I noticed that he had placed them in a single pile so that between the red pair there was one block, two between the blue pair, and three between the yellow. I then found that by a complete rearrangement I could add a green pair with four between them.

The general problem was summarized by Hayasaka & Saito (1979) as: “Given 2n numbers, two each of the numbers 1, 2, …., n, to find whether they can be arranged in a row in such a way that the two occurrences of each number k are separated by exactly k other elements of the row.



Langford actually discovered several examples for various different number of blocks. Here are some examples of his sequences:



What one might notice is that all the solutions are for a number of blocks (n) that are divisible by 4, or one less than a number that is divisible by 4. A bit more explanation for why this is so can be found at Nick Berry’s excellent blog.



As ‘n’ increases, there are an increasing number of Langford Sequences. There is only one solution for n=3 or n=4, 26 solutions for n=7, 150 for n=8, 17,792 for n=11, 108,144 for n=12 ….. 46,845,158,056,515,936 for n=24 ! Obviously, tyring to find all solutions for any given n is computationally intensive!



At the same timea as Langford wrote his piece, a related phenomenon was being independently researched by a Swedish mathematician, Thoralf Skolem, who was trying to form sequences of 2*n blocks with intervals of 0,1,2,3 etc.

My aim here is to write a small script that can find these sequences.



The code


Langford’s Sequences


Say we have 2*8 blocks, let’s represent them with letters. We can then generate a randomly sample sequence of these letters. A simple way to find the differences between the positions of each letter is to use which

x <- rep(LETTERS[1:8],2)
set.seed(1)
y <- sample(x)
y
##  [1] "E" "F" "A" "D" "C" "B" "C" "G" "F" "A" "B" "G" "E" "H" "D" "H"
abs(diff(which(y=="A")))-1  #6
## [1] 6
abs(diff(which(y=="D")))-1  #10
## [1] 10
abs(diff(which(y=="H")))-1  #1
## [1] 1


We can get the results for all the individual letters with a loop:

res<-NULL
for(i in 1:8){  res[[i]] <- abs(diff(which(y==LETTERS[i])))-1 }
          
names(res)<-LETTERS[1:8]
res
##  A  B  C  D  E  F  G  H 
##  6  4  1 10 11  6  3  1


This is fine for one randomly sampled sequence, but when finding Langford sequences, we might want to check many sequences, so it is better to have a faster function. match seems to be very fast for this purpose (although I think using data.table it might be possible to get even faster):

langford <- function(x) {
  ux = unique(x)
  mux = match(x, ux)      
  ans = integer(length(ux))       
  for(i in seq_along(x)) ans[mux[i]] = i - ans[mux[i]]        
  return(setNames(ans - 1L, ux))
}

langford(y)
##  E  F  A  D  C  B  G  H 
## 11  6  6 10  1  4  3  1



Finding a Langford Sequence

Say we wanted to find a solution for 8 blocks. My strategy here is to keep sampling sequences until one satisfies the criteria. The way to check that I am using is to sort the intervals between each pair of letters and then ask if it is equal to 1:8. If it is, then we break and return that sequence:

set.seed(17)
while(TRUE) {
  
  samps <- sample(x)
  tmp <- sort(langford(samps))
  
  if(sum(tmp==c(1:8))==8)
    
    break
}

samps ## the sequence returned
##  [1] "G" "F" "D" "A" "E" "H" "A" "D" "F" "G" "E" "C" "B" "H" "B" "C"
sort(langford(samps))  ## the interval between pairs of letters in the sequence
## B A C D E F H G 
## 1 2 3 4 5 6 7 8



The above can be generalized for any ‘n’:

get.langford <- function(n){

  
  
while(TRUE) {

  x <- rep(LETTERS[1:n],2)
  samps <- sample(x)
  tmp <- sort(langford(samps))
  
  if(sum(tmp==c(1:n))==n)
    
    break
}

return(samps)
}


I could add some if-stop ‘s to this to prevent someone from entering a ’n’ that will not work (e.g. 5,6). Also, if someone wanted to use an ‘n’ of >26 then we’d have to use combinations of letters. I don’t recommend this though, as the function is pretty slow for anything greater than n=12.

I think the strategy could also be optimized such that rather than randomly sampling sequences, the sequences tested are done so in a more systematic fashion.

Nevertheless, here it is working for n=12.

set.seed(77)
lang12 <- get.langford(12)
lang12
##  [1] "A" "L" "I" "L" "H" "B" "J" "G" "I" "C" "A" "E" "B" "H" "E" "D" "F"
## [18] "K" "G" "J" "F" "C" "K" "D"
sort(langford(lang12))
##  L  E  F  K  I  B  D  H  A  G  C  J 
##  1  2  3  4  5  6  7  8  9 10 11 12



Finding Skolem Sequences

This is simply just a change in the if statement prior to the break.

skolem <- function(n){

while(TRUE) {

  x <- rep(LETTERS[1:n],2)
  samps <- sample(x)
  tmp <- sort(langford(samps))
  
  if(sum(tmp==c(0:(n-1)))==n)
    
    break
}

return(samps)
}

For instance, a Skolem sequence for n=8:

set.seed(88)
sk <- skolem(8)
sk
##  [1] "B" "D" "B" "G" "E" "E" "F" "C" "G" "D" "A" "H" "F" "A" "C" "H"
sort(langford(sk))
## E B A H G F C D 
## 0 1 2 3 4 5 6 7



Finding Hooked Langford Sequences

Although Langford sequences can only be found when ‘n’ is divisible by 4 or when n+1 is divisible by 4, there is an alternative type of Langford sequence called a Hooked Langford Sequence which can be found for all values of ‘n’. A Hooked Lanford Sequence is one where another block/letter is inserted in the penultimate position in the sequence.

The code for these Hooked Langford Sequence is here:

hooked.langford <- function(n){

while(TRUE) {

  x <- rep(LETTERS[1:n],2)
  samps <- sample(x)
  samps <- c(head(samps,((n*2)-1)), "X", tail(samps, 1))

  
  tmp <- sort(langford(samps))
  
  if(sum(tmp==c(1:n))==n)
    
    break
}

return(samps)
}


Some examples:

set.seed(1)
h1 <- hooked.langford(5)
h1
##  [1] "A" "D" "B" "E" "A" "E" "D" "C" "B" "X" "C"
sort(langford(h1))
## E C A D B X 
## 1 2 3 4 5 9
set.seed(11)
h2 <- hooked.langford(9)
h2
##  [1] "E" "H" "C" "H" "E" "D" "F" "G" "I" "A" "G" "C" "B" "D" "A" "I" "F"
## [18] "X" "B"
sort(langford(h2))
##  H  G  E  A  B  I  D  C  F  X 
##  1  2  3  4  5  6  7  8  9 17



A final summary chart of the different types of sequences: