Langford Pairing (2011)

https://susam.net/blog/langford-pairing.html

by susam • 3 years ago

10 4 3 years ago

shubber• 3 years ago

"A few days ago, I came across this problem" - well, volume 4A of The Art of Computer Programming was published in 2011, which gives a pretty good treatment of the Langford Pairs. The author might've made their reference clear, and called out that the Python implementation was their own contribution

susam2• 3 years ago

Hello! I am the author of this post and I did not have access to volume 4A of the Art of Computer Programming. Therefore I could not have made a reference to that book. In fact, I've never read that book.

This particular problem was shared by a colleague of mine in an internal mathematics puzzle forum. This was back in the days when my friends, some of my colleagues, and I were much younger and going through a phase in our lives when we used to challenge each other with mathematical puzzles. This blog post was a response to one such challenge.

The solution is my own. How similar do you find this solution to the one in Knuth's book? If it is indeed very similar, I would be a little amused but not too surprised because I think the approach I laid out in my solution is one of the few obvious paths to a solution. In fact, some of my colleagues independently came up with very similar proofs for the necessary condition.

If you browse my blog, you would see that I do make references clear when I pick material or concepts from other sources. Some examples would be <https://susam.net/blog/from-vector-spaces-to-periodic-functi...> and <https://susam.net/blog/lisp-in-vim.html>.

quibono• 3 years ago

Thank you, I really enjoyed the post. I also found the explanation very clear (I like the notation!).

I have to say that while the necessary part of the proof is very satisfying, the sufficient part feels a bit mechanical. Any background on how one arrives at the generation steps?

susam2• 3 years ago

Thank you for the comment. Glad you enjoyed it. I feel the same about the proof of the sufficient condition. It is mechanical indeed. Also, considering the fact that there are multiple solutions possible for each n, the specific construction I use in my blog post identifies only one (actually two, because the reverse of the solution is also a valid solution) of those multiple solutions.

To arrive at the particular construction in my blog post, I picked a solution each from the solutions for n = 2 and n = 3 and tried to explain the separation between the elements algebraically. Such an analysis is helped by the fact that the cases n = 3 and n = 4 have only two solutions each (where each solution in the pair is the reverse of the other). Further the length of each solution for these cases is also quite small thus making a manual analysis possible. The algebraic formulas so obtained then becomes both the proof of the sufficient condition as well as a method to construct one of the solutions.

Langford Pairing (2011)

Related Stories