Generating Langford Pairs in Scala
As I've discussed on the blog before, I've been reading Donald Knuth's series The Art of Computer Programming now for a few years, trying to work through all of the exercises. I've gotten up to volume 4A, which starts out with a discussion of an interesting mathematical puzzle — the generation of Langford pairs. Given a list of n integers, how many ways can you arrange them in pairs so that each integer i is i slots away from its twin? For example, when n=3, the arrangement:
312132
Is a Langford pairing (and along with its reverse is, in fact, the only Langford pairing for n=3).
Not every n can generate a Langford pairing, though. In fact, Knuth presents a proof that the only integers which can are those where n=4k-1 or n=4k. When n is of this form, though, finding the actual configurations is tricky. It occurred to me while thinking about it that discovering pairs makes for a succinct Scala programming exercise.
Of course, you could always just brute-force your way through every combination, but there are a lot of combinations, even for small ns: more than 87 trillion for n = 7. A quicker way is to reduce the possibilities based on what you know about the Langford pairs. For example, when n = 7, we're trying to fill in 14 available slots with the 7's 7 slots away from each other, the 6's 6 slots away from each other, etc. So, given 14 slots, there are only 6 different possible locations for the pair of 7's:
7 _ _ _ _ _ _ _ 7 _ _ _ _ _
_ 7 _ _ _ _ _ _ _ 7 _ _ _ _
_ _ 7 _ _ _ _ _ _ _ 7 _ _ _
_ _ _ 7 _ _ _ _ _ _ _ 7 _ _
_ _ _ _ 7 _ _ _ _ _ _ _ 7 _
_ _ _ _ _ 7 _ _ _ _ _ _ _ 7
In any other configuration, the 7's would be too close to one another. Also, given each configuration of 7's, the 6's can only be placed in 5 ways:
7 _ _ _ _ _ _ _ 7 _ _ _ _ _
6 _ _ _ _ _ _ 6
6 _ _ _ _ _ _ 6
6 _ _ _ _ _ _ 6
6 _ _ _ _ _ _ 6
6 _ _ _ _ _ _ 6
_ 7 _ _ _ _ _ _ _ 7 _ _ _ _
6 _ _ _ _ _ _ 6
6 _ _ _ _ _ _ 6
6 _ _ _ _ _ _ 6
6 _ _ _ _ _ _ 6
6 _ _ _ _ _ _ 6
_ _ 7 _ _ _ _ _ _ _ 7 _ _ _
6 _ _ _ _ _ _ 6
6 _ _ _ _ _ _ 6
6 _ _ _ _ _ _ 6
6 _ _ _ _ _ _ 6
6 _ _ _ _ _ _ 6
_ _ _ 7 _ _ _ _ _ _ _ 7 _ _
6 _ _ _ _ _ _ 6
6 _ _ _ _ _ _ 6
6 _ _ _ _ _ _ 6
6 _ _ _ _ _ _ 6
6 _ _ _ _ _ _ 6
_ _ _ _ 7 _ _ _ _ _ _ _ 7 _
6 _ _ _ _ _ _ 6
6 _ _ _ _ _ _ 6
6 _ _ _ _ _ _ 6
6 _ _ _ _ _ _ 6
6 _ _ _ _ _ _ 6
_ _ _ _ _ 7 _ _ _ _ _ _ _ 7
6 _ _ _ _ _ _ 6
6 _ _ _ _ _ _ 6
6 _ _ _ _ _ _ 6
6 _ _ _ _ _ _ 6
6 _ _ _ _ _ _ 6
The spot right after the first 7 won't work because the matching 6 would overwrite the second 7. However, given any configuration of 7's and 6's, there are at most 5 spots to place the 5's, but fewer depending on the configuration: 5's:
7 _ 6 _ _ _ _ _ 7 6 _ _ _ _
5 _ _ _ _ _ 5
5 _ _ _ _ _ 5
5 _ _ _ _ _ 5
5 _ _ _ _ _ 5
5 _ _ _ _ _ 5
7 _ _ 6 _ _ _ _ 7 _ 6 _ _ _
5 _ _ _ _ _ 5
5 _ _ _ _ _ 5
5 _ _ _ _ _ 5
5 _ _ _ _ _ 5
5 _ _ _ _ _ 5
7 _ _ _ 6 _ _ _ 7 _ _ 6 _ _
5 _ _ _ _ _ 5
5 _ _ _ _ _ 5
5 _ _ _ _ _ 5
5 _ _ _ _ _ 5
7 _ _ _ _ 6 _ _ 7 _ _ _ 6 _
5 _ _ _ _ _ 5
5 _ _ _ _ _ 5
5 _ _ _ _ _ 5
5 _ _ _ _ _ 5
7 _ _ _ _ _ 6 _ 7 _ _ _ _ 6
5 _ _ _ _ _ 5
5 _ _ _ _ _ 5
5 _ _ _ _ _ 5
5 _ _ _ _ _ 5
6 7 _ _ _ _ _ 6 _ 7 _ _ _ _
5 _ _ _ _ _ 5
5 _ _ _ _ _ 5
5 _ _ _ _ _ 5
5 _ _ _ _ _ 5
_ 7 _ 6 _ _ _ _ _ 7 6 _ _ _
5 _ _ _ _ _ 5
5 _ _ _ _ _ 5
5 _ _ _ _ _ 5
5 _ _ _ _ _ 5
5 _ _ _ _ _ 5
_ 7 _ _ 6 _ _ _ _ 7 _ 6 _ _
5 _ _ _ _ _ 5
5 _ _ _ _ _ 5
5 _ _ _ _ _ 5
5 _ _ _ _ _ 5
5 _ _ _ _ _ 5
_ 7 _ _ _ 6 _ _ _ 7 _ _ 6 _
5 _ _ _ _ _ 5
5 _ _ _ _ _ 5
5 _ _ _ _ _ 5
5 _ _ _ _ _ 5
_ 7 _ _ _ _ 6 _ _ 7 _ _ _ 6
5 _ _ _ _ _ 5
5 _ _ _ _ _ 5
5 _ _ _ _ _ 5
...
You can always find a place for the 4's but, eventually, you get down to configurations where the 3's can't be placed at all:
5 _ _ 7 4 6 5 _ _ 4 _ 7 6 _
5 _ _ 7 _ 6 5 _ 4 _ _ 7 6 4
6 4 _ 5 7 _ 4 6 _ 5 _ _ 7 _
Or where the 3's can be placed, but the 2's can't:
_ 5 6 7 _ 4 _ 5 3 6 4 7 3 _
3 5 6 7 3 _ _ 5 4 6 _ 7 _ 4
_ 5 6 7 _ _ 3 5 4 6 3 7 _ 4
4 _ 6 7 5 4 _ _ 3 6 5 7 3 _
_ 4 6 7 5 _ 4 _ 3 6 5 7 3 _
Or, if you get lucky, you find one where you can place all 7 pairs and you get a valid Langford pairing. So, although this is still a trial-and-error process, the number of combinations to go through have gone from (2n)! down to O(n!). Not feasible for huge n, but a bit more tractable. This approach suggests a recursive algorithm to generate all Langford pairs for a given n:
def findPairing(n: Int, pairs: Array[Int]): List[Array[Int]] =
n match {
case 0 => pairs :: Nil
case _ =>
var l = List[Array[Int]]()
for (i <- 0 until pairs.size - n - 1; if (pairs(i) == 0 && pairs(i + n + 1) == 0))
l = l ::: findPairing(n - 1, pairs.updated(i, n).updated(i + n + 1, n))
l
}
Listing 1: Scala function to find Langford pairs
Add a comment:
Completely off-topic or spam comments will be removed at the discretion of the moderator.
You may preserve formatting (e.g. a code sample) by indenting with four spaces preceding the formatted line(s)
