Permutations without repeating myself

Question

This may be a quite simple question, but there we go.

Imagine that I've got a sequence $s = [s_1, s_2, \dots, s_n]$. I want to generate programatically a new random permutation $s'$ of $s$ so that $\forall i \in [1,n],\; s[i] \neq s'[i]$, of, what is the same, none of the values of the new permutation coincide 1-1 with the values of the previous one.

For instance, for $s = [1,2,3,4]$, $s' = [2,3,4,1]$ is a desired permutation because $s'$ is a permutation of $s$ and $2 \neq 1$, $2\neq 3$, and so on.

I know that the Fiser-Yates produces random permutation, but you cannot force the requirement that $s[i] \neq s'[i]$ for all $i$'s.

Thank you.

Edit: apparently I'm asking for how to generate a derangement with uniform probability distribution.

Answer 1

Generate a random derangement (that's a permutation with no fixed points), then multiply it by $s$ to obtain $s'$.

Answer 2

One way to generate a random derangement $\sigma$ of a set $S$ of $n$ letters is based on the recursion $!n = (n-1)(!(n-1) + !(n-2)$. First compute the derangement numbers $!k$ for $1 \le k \le n$.
Choose $\sigma(s_1)$ uniformly from $S \backslash \{s_1\}$. With probability $!(n-2)/(!(n-1)+!(n-2))$, let $\sigma(\sigma(s_1)) = s_1$, and the rest of $\sigma$ is a derangement of the remaining $n-2$ letters $S \backslash \{s_1, \sigma(s_1)\}$. Otherwise, recursively take a derangement of $\tau$ of $S \backslash \{s_1\}$; let $\sigma(\tau^{-1}(\sigma(s_1))) = s_1$, otherwise $\sigma(i) = \tau(i)$.