Yes, there are a few faster ways to make Langford sequences.
Firstly, here's a fairly simple way. Rather than testing all of the permutations containing the pairs of numbers from 1 to n, we generate the permutations of numbers from 1 to n and then try to build Langford sequences from those permutations by placing each pair of numbers into the next available pair of slots. If no pair of slots is available we abandon that permutation and go onto the next one.
Building a sequence is a little slower than simply testing if a full permutation of 2n items is valid, but it means we need to test a lot fewer permutations when n is large. Eg, if n=7 there are 7! = 5040 permutations, but if we test the permutations of 7 pairs, that's 14! = 87178291200 permutations!
We can reduce that number though, because it contains a lot of duplicates. For 7 pairs, the number of unique permutations is 14! / (2**7) = 681080400 since swapping the 2 items in any of the 7 pairs produces a duplicate permutation. Unfortunately, itertools.permutations doesn't care about duplicates, but my answer here has code for a permutation generator that doesn't produce duplicate permutations. But still, 681 million permutations is a large number, and it takes a long time to test them. So it's better if we can avoid doing that.
import sys
from itertools import permutations
def place(t):
slen = 2 * len(t)
seq = [0] * slen
for u in t:
# Find next vacant slot
for i, v in enumerate(seq):
if v == 0:
break
else:
# No vacant slots
return
j = i + u + 1
if j >= slen or seq[j]:
return
seq[i] = seq[j] = u
return tuple(seq)
def langford(n):
count = 0
for t in permutations(range(1, n+1)):
seq = place(t)
#if seq and seq < seq[::-1]:
if seq:
count += 1
print(seq, count)
return count // 2
def main():
n = int(sys.argv[1]) if len(sys.argv) > 1 else 4
count = langford(n)
print(count)
if __name__ == '__main__':
main()
output for n=7
(1, 4, 1, 5, 6, 7, 4, 2, 3, 5, 2, 6, 3, 7) 1
(1, 4, 1, 6, 7, 3, 4, 5, 2, 3, 6, 2, 7, 5) 2
(1, 5, 1, 4, 6, 7, 3, 5, 4, 2, 3, 6, 2, 7) 3
(1, 5, 1, 6, 3, 7, 4, 5, 3, 2, 6, 4, 2, 7) 4
(1, 5, 1, 6, 7, 2, 4, 5, 2, 3, 6, 4, 7, 3) 5
(1, 5, 1, 7, 3, 4, 6, 5, 3, 2, 4, 7, 2, 6) 6
(1, 6, 1, 3, 5, 7, 4, 3, 6, 2, 5, 4, 2, 7) 7
(1, 6, 1, 7, 2, 4, 5, 2, 6, 3, 4, 7, 5, 3) 8
(1, 7, 1, 2, 5, 6, 2, 3, 4, 7, 5, 3, 6, 4) 9
(1, 7, 1, 2, 6, 4, 2, 5, 3, 7, 4, 6, 3, 5) 10
(2, 3, 6, 2, 7, 3, 4, 5, 1, 6, 1, 4, 7, 5) 11
(2, 3, 7, 2, 6, 3, 5, 1, 4, 1, 7, 6, 5, 4) 12
(2, 4, 7, 2, 3, 6, 4, 5, 3, 1, 7, 1, 6, 5) 13
(2, 5, 6, 2, 3, 7, 4, 5, 3, 6, 1, 4, 1, 7) 14
(2, 6, 3, 2, 5, 7, 3, 4, 6, 1, 5, 1, 4, 7) 15
(2, 6, 3, 2, 7, 4, 3, 5, 6, 1, 4, 1, 7, 5) 16
(2, 6, 7, 2, 1, 5, 1, 4, 6, 3, 7, 5, 4, 3) 17
(2, 7, 4, 2, 3, 5, 6, 4, 3, 7, 1, 5, 1, 6) 18
(3, 4, 5, 7, 3, 6, 4, 1, 5, 1, 2, 7, 6, 2) 19
(3, 4, 6, 7, 3, 2, 4, 5, 2, 6, 1, 7, 1, 5) 20
(3, 5, 7, 2, 3, 6, 2, 5, 4, 1, 7, 1, 6, 4) 21
(3, 5, 7, 4, 3, 6, 2, 5, 4, 2, 7, 1, 6, 1) 22
(3, 6, 7, 1, 3, 1, 4, 5, 6, 2, 7, 4, 2, 5) 23
(3, 7, 4, 6, 3, 2, 5, 4, 2, 7, 6, 1, 5, 1) 24
(4, 1, 6, 1, 7, 4, 3, 5, 2, 6, 3, 2, 7, 5) 25
(4, 1, 7, 1, 6, 4, 2, 5, 3, 2, 7, 6, 3, 5) 26
(4, 5, 6, 7, 1, 4, 1, 5, 3, 6, 2, 7, 3, 2) 27
(4, 6, 1, 7, 1, 4, 3, 5, 6, 2, 3, 7, 2, 5) 28
(4, 6, 1, 7, 1, 4, 5, 2, 6, 3, 2, 7, 5, 3) 29
(4, 6, 3, 5, 7, 4, 3, 2, 6, 5, 2, 1, 7, 1) 30
(5, 1, 7, 1, 6, 2, 5, 4, 2, 3, 7, 6, 4, 3) 31
(5, 2, 4, 6, 2, 7, 5, 4, 3, 1, 6, 1, 3, 7) 32
(5, 2, 4, 7, 2, 6, 5, 4, 1, 3, 1, 7, 6, 3) 33
(5, 2, 6, 4, 2, 7, 5, 3, 4, 6, 1, 3, 1, 7) 34
(5, 2, 7, 3, 2, 6, 5, 3, 4, 1, 7, 1, 6, 4) 35
(5, 3, 6, 4, 7, 3, 5, 2, 4, 6, 2, 1, 7, 1) 36
(5, 3, 6, 7, 2, 3, 5, 2, 4, 6, 1, 7, 1, 4) 37
(5, 6, 1, 7, 1, 3, 5, 4, 6, 3, 2, 7, 4, 2) 38
(5, 7, 1, 4, 1, 6, 5, 3, 4, 7, 2, 3, 6, 2) 39
(5, 7, 2, 3, 6, 2, 5, 3, 4, 7, 1, 6, 1, 4) 40
(5, 7, 2, 6, 3, 2, 5, 4, 3, 7, 6, 1, 4, 1) 41
(5, 7, 4, 1, 6, 1, 5, 4, 3, 7, 2, 6, 3, 2) 42
(6, 1, 5, 1, 7, 3, 4, 6, 5, 3, 2, 4, 7, 2) 43
(6, 2, 7, 4, 2, 3, 5, 6, 4, 3, 7, 1, 5, 1) 44
(7, 1, 3, 1, 6, 4, 3, 5, 7, 2, 4, 6, 2, 5) 45
(7, 1, 4, 1, 6, 3, 5, 4, 7, 3, 2, 6, 5, 2) 46
(7, 2, 4, 5, 2, 6, 3, 4, 7, 5, 3, 1, 6, 1) 47
(7, 2, 4, 6, 2, 3, 5, 4, 7, 3, 6, 1, 5, 1) 48
(7, 2, 6, 3, 2, 4, 5, 3, 7, 6, 4, 1, 5, 1) 49
(7, 3, 1, 6, 1, 3, 4, 5, 7, 2, 6, 4, 2, 5) 50
(7, 3, 6, 2, 5, 3, 2, 4, 7, 6, 5, 1, 4, 1) 51
(7, 4, 1, 5, 1, 6, 4, 3, 7, 5, 2, 3, 6, 2) 52
26
That takes about 0.2 seconds on my old 2GHz machine.
Conventionally, 2 Langford sequences are considered to be the same if one is a reversal of the other. One way to deal with that is to compare a sequence with its reversed version, and only print it if its less than the reversed version. You can change the above code to do that by commenting out
if seq:
in the langford function and un-commenting the following line:
#if seq and seq < seq[::-1]:
The above code is an improvement, but we can do better. My next solution uses a technique known as recursive backtracking. This technique can be elegantly implemented in Python through the use of a recursive generator function.
We start with a sequence of zeros. Starting with the highest number, we try to place a pair of numbers into each legal pair of slots, and if we're successful we recurse to place the next pair of numbers, if there are no numbers left to place we've found a solution and we can yield it.
import sys
def langford(n, seq):
''' Generate Langford sequences by recursive backtracking '''
# The next n
n1 = n - 1
# Test each valid pair of positions for this n
for i in range(0, len(seq) - n - 1):
j = i + n + 1
if not (seq[i] or seq[j]):
# Insert this n into the sequence
seq[i] = seq[j] = n
if n1:
# Recurse to add the next n
yield from langford(n1, seq)
else:
# Nothing left to insert
yield seq
# Remove this n from the sequence in preparation
# for trying the next position
seq[i] = seq[j] = 0
def main():
n = int(sys.argv[1]) if len(sys.argv) > 1 else 4
for i, t in enumerate(langford(n, [0] * 2 * n), 1):
print(t, i)
if i % 1000 == 0:
print(' ', i, end='\r', flush=True)
print('\n', i // 2)
if __name__ == '__main__':
main()
The if i % 1000 == 0: stuff lets you see the progress when n is large. This is handy if you comment-out the print(t, i) line.
This code can generate the 35584 = 2*17792 sequences for n=11 in under 25 seconds on my machine.
If you want to collect the sequences yielded by langford into a list, rather than just printing them, you can do it like this:
n = 7
results = list(langford(n, [0] * 2 * n))
However, if you want to do that you must make a slight change to the langford function. Where it says
yield seq
change it to
yield seq[:]
so that it yields a copy of seq rather than the original seq list.
If you just want to get the count of sequences (not counting reversals), you can do this:
n = 7
count = sum(1 for _ in langford(n, [0] * 2 * n)) // 2
print(count)
That will work ok with yield seq.
The above code will be slow for larger values of n. There are faster techniques for calculating the number of Langford sequences, using fairly advanced mathematics, but there's no known simple formula. The OEIS has a list of Langford sequences numbers at A014552.
