  Two permutations of $[n]=\{1,2 \ldots n\}$ are \textit{$k$-neighbor
separated} if there are two elements that are neighbors in one of the
permutations and that are separated by exactly $k-2$ other elements in the
other permutation. Let the maximal number of pairwise $k$-neighbor separated
permutations of $[n]$ be denoted by $P(n,k)$. In a previous paper, the authors
have determined $P(n,3)$ for every $n$, answering a question of K\"orner,
Messuti and Simonyi affirmatively. In this paper we prove that for every fixed
positive integer $\ell $, $$P(n,2^\ell+1) = 2^{n-o(n)}. $$ We conjecture that
for every fixed even $k$, $P(n,k)=2^{n-o(n)}$. We also show that this
conjecture is asymptotically true in the following sense $$\lim_{k \rightarrow
\infty} \lim_{n \rightarrow \infty} \sqrt[n]{P(n,k)}=2.$$ Finally, we show that
for even $n$, $P(n,n)= 3n/2$.
