Let $\Pi$ be the set of all permutations of the set $\left\{1 \ldots n\right\}$. Of course I know the cardinal of $\Pi$ is $n!$.
I am trying to compute the number of permutations $\pi = \left\{ \pi_1, \ldots \pi_n \right\} \in \Pi $ that verify that the maximum distance between any two consecutive permuted elements is lower than a given constant $M$.
This is, I want to compute the cardinal of the set $\Pi^M = \left\{ \pi = \left\{ \pi_1, \ldots \pi_n \right\}, \max(|\pi_i - \pi_{i+1} |) < M , \forall i,i+1 \in \left\{1\ldots n\right\}\right\}$
Also, is there an algorithm to efficiently compute such a subset $\Pi^M$ of $\Pi$?
Maybe an example explains better the $\Pi^M$ set, with $n=4$ and $M=2$:
- $ \left\{1, 2, 3, 4 \right\} \in \Pi^2$ as all elements have a distance of one. But
- $ \left\{4, 1, 2, 3 \right\} \notin \Pi^2$ because elements 4 and 1 have a distance of 3.