Problem Detail: We have two integers $z, k$ We form a sequence now of first z natural numbers. i.e. $1, 2, 3, 4, ldots z$. Now we have to find total number of permutations of this sequence such that the sum of any two adjacent numbers is $ le k$ ( $z leq 10^6$, $;;z < k < 2*z$ ) Here is what I have been able to think untill now. If k=2*z-1, the answer is z! Now if we reduce the value of k to 2*z-2, then we take the highest pair as a group and permute with rest of the elements, we subtract this value from the previous case of k=2*z-1 i.e. dp(z,k)= z! for k=2*z-1. and dp(z,k-1)=dp(z,k)-(z-1)!*2 for k=2*z-2. I want to know if I am going in the right direction. Any help on the closed form would be good.
Asked By : Alice
Answered By : Yuval Filmus
Let $D(z,k,l)$ be the number of permutations $p_1,ldots,p_z$ of $1,ldots,z$ in which the condition $p_i + p_{i+1} leq k$ is violated exactly $l$ times. Then $D(z,k,l)$ is given by the following recurrence relation, which is valid whenever $z geq 2$ and $z+1 leq k leq 2z-1$: $$ D(z,k,l) = begin{cases} (z-l) D(z-1,z,z-2-l) + (l+1) D(z-1,z,z-3-l), & k = z+1, (z-l) D(z-1,k-2,l) + (l+1) D(z-1,k-2,l+1), & k neq z+1. end{cases} $$ I leave the proof of correctness to you. (Here is a hint for the first case: show that $D(z,z+1,l) = D(z,z,z-1-l)$ and that $D(z,z,l) = (z-l) D(z-1, z, l-2) + (l+1) D(z-1, z, l-1)$.) The following Python program implements this recurrence:
def D(z, k, l): if z < 2 or k < z+1 or k >= 2*z: raise "Error" if z == 2: return 2 * int(l == 0) if k == z+1: return (z-l) * D(z-1, z, z-2-l) + (l+1) * D(z-1, z, z-3-l) return (z-l) * D(z-1, k-2, l) + (l+1) * D(z-1, k-2, l+1)
A more efficient implementation will use dynamic programming, I leave that also to you. One thing to notice is that case II preserves the quantity $2z-k$ while case I always has $k = z+1$, so the algorithm is quadratic rather than cubic. For concreteness, here is a Python implementation of the dynamic programming method:
def DP(z, k): if not (z >= 2 and z+1 <= k <= 2*z-1): raise "Error" z_crit = 2*z-k+1 L = [2, 0] for w in range(3, z_crit+1): L = [(w-l) * L[w-2-l] + (l+1) * L[w-3-l] for l in range(w-2)] + [2 * L[0], 0] for w in range(z_crit+1, z+1): L = [(w-l) * L[l] + (l+1) * L[l+1] for l in range(w-2)] + [2 * L[w-2], 0] return L[0]
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/12522 Ask a Question Download Related Notes/Documents
