7
$\begingroup$

Given $N$ and $K$, I need to count number of permutations of $1, 2, 3,\ldots, N$ in which no adjacent elements differ by more than $K$. How do I approach this problem?

$\endgroup$
  • 1
    $\begingroup$ Please share your thoughts so far :) $\endgroup$ – Shaun Jan 25 '15 at 10:16
  • $\begingroup$ I am trying to count the number of permutations by hand, but it is too cumbersome. $\endgroup$ – xennygrimmato Jan 25 '15 at 10:20
  • 1
    $\begingroup$ Here is one estimate: There are $N!$ permutations. Each has $N-1$ adjacent pairs. These must all come from $(N-1)+...+(N-K)$ of the $N(N-1)/2$ pairs, so my estimate is $N!{(N-1)+...+(N-K)\choose N-1}/{N(N-1)/2\choose N-1}$. $\endgroup$ – Empy2 Jan 25 '15 at 11:08
  • $\begingroup$ This is OEIS A249631. I note there are no formulae there, only a couple routines that generate/filter/count, so I wonder if there are in fact any other methods. $\endgroup$ – HammyTheGreek Jan 26 '15 at 21:44
2
$\begingroup$

This is a question that appeared in a contest i.e Codecraft 2015 organised by IIITH and its editorial is available here. You can also submit your code in the gym.

Basically you require DP + Bitmask.You need to keep track of last_used element and all other elements included so far.You can do it using recursion and it will require memoization to optimize it.

$\endgroup$

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.