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.
![[home]](http://people.csail.mit.edu/mip/images/home.gif){kind=small}
4 comments:
At least these guys don't seem to know a closed form solution: http://scholar.google.com/scholar?hl=en&lr=&cluster=2621410177201314710
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 :(
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.
@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
Post a Comment