Wednesday, April 8, 2009

Puzzle: Short-hop permutations

Count the number of permutations of size n, such that |π(i) - π(i+1)| ≤ k, for all i. That is, the hop between any two consecutive values must be short.

I am asking for an algorithm, not a closed formula. (Combinatorialists: is one known?)

Your algorithm should work fast for values like n=106 and k=8. I have not thought hard about supporting larger k (say, k = 20), but I would certainly be interested to hear such a solution if you have one.

Credits. This problem was used in a selection contest for the Romanian olympic team. The original author was Marius Andrei. My subjective judgment of its difficulty is "average+" (it was tricky, but I solved it within 10 minutes). YMMV.

at

4 comments:

  1. rgrigFri Apr 10, 09:58:00 AM EDT

    At least these guys don't seem to know a closed form solution: http://scholar.google.com/scholar?hl=en&lr=&cluster=2621410177201314710

    ReplyDelete
  2. rgrigFri Apr 10, 11:32:00 AM EDT

    Actually, they seem to just do bruteforce :o Not even the simple (but slow) solution where you keep track of the count C(n,S) of permutations of 1..n that have the n-k+1..n numbers in a certain configuration S. A configuration being something like 012036504: here k=6; 1 stands for n-k+1; 6 stands for n; 0 means "a string of stuff <=n-k that I don't really remember". There are O(n(2k)^k) such numbers and you do about O(k) operations for each. Hence, too slow :(

    ReplyDelete
  3. UnknownMon Apr 13, 03:26:00 PM EDT

    Shouldn't there be O(k!*2^k) such configurations? You can get all of them by starting from a permutation of 1..K and adding a zero between some consecutive values.

    ReplyDelete
  4. rgrigMon Apr 13, 05:34:00 PM EDT

    @Andrei: Yes. I used k!=O(k^k). For some strange reason I thought at the time that the formula will be easier to read :P

    ReplyDelete