2
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ What is your motivation? What have you tried? $\endgroup$ – Yuval Filmus Jun 8 '13 at 5:47
  • $\begingroup$ @YuvalFilmus I have added the limits for z,k there must be some closed form for the above conditions, since brute forcing them seems unfeasable. I am guessing at a dp solution. I tried writing down the values for small values of z,k and trying to guess a pattern, but no good till now. $\endgroup$ – Alice Jun 8 '13 at 9:03
  • $\begingroup$ @YuvalFilmus I have added my approach. $\endgroup$ – Alice Jun 8 '13 at 21:23
  • $\begingroup$ Here is the user's motivation: codechef.com/JUNE13/problems/PERMUTE. $\endgroup$ – Yuval Filmus Jun 15 '13 at 19:50
2
$\begingroup$

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]
$\endgroup$
  • $\begingroup$ Any hints for the dynamic programming structure? This recurrance looks more complex than i imagined it to be. If I calculate this value modulus a prime number. Would that help? $\endgroup$ – Alice Jun 9 '13 at 0:49
  • $\begingroup$ If you calculate the actual values for $z \approx 10^6$ then the numbers would be gigantic, so this is only really possible if you compute it modulo something. $\endgroup$ – Yuval Filmus Jun 9 '13 at 1:35
  • $\begingroup$ yes and how to proceed with dynamic programming? Can this be done using matrices for multiplication? Like a transformation matrix T^x * initial state? $\endgroup$ – Alice Jun 9 '13 at 1:38
  • $\begingroup$ As for implementation using DP, I added a few comments. If you're lazy you can always use memoization, which is dynamic programming without planning ahead. (Memoization: store all values of $D(z,k,l)$ you compute in a table, and don't recompute a value which is already in the table.) $\endgroup$ – Yuval Filmus Jun 9 '13 at 1:38
  • 1
    $\begingroup$ The DP implementation calculates $D(z,k,\cdot)$ from $D(z-1,k-2,\cdot)$ (if $k > z+1$) and $D(z,z+1,\cdot)$ from $D(z-1,z,\cdot)$, so you can implement it using matrix multiplication. I'll leave you the details. You only need linear space. $\endgroup$ – Yuval Filmus Jun 9 '13 at 1:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.