Find all derangements for $n=4$ and $n=5$

Question

Find all derangements for $n=4$ and $n=5$

Solution for $n=4$

I know there are 9 possibilities

$(2,1,4,3), (2,3,4,1), (2,4,1,3), (3,1,4,2),(3,4,1,2), (3,4,2,1) (4,1,2,3),(4,3,1,2), (4,3,2,1)$

Solution for $n=5$

I know there are 44 of them, I am wondering if someone had a link to a list of them, or possibly a program that would spit them out, or could help me in general, thanks!

Answer 1

These kind of things are actually really easy to find with Constraint programming.

For a permutation of length n we got the following constraints for a list:
- The list has to have length(n)
- Any number x must be in range 1..n
- All elements must different

Looking at a derangement of length n we got the following constraints:
- Be a permutation
- Have no fixed points

We can put all of this quite fast together in Prolog with:

:- use_module(library(clpfd)).

permut(L,N) :-
    length(L, N),
    L ins 1..N,
    all_different(L),
    label(L).

noFixpoint([],_Xs).
noFixpoint([X|Xs],N1) :-
    X #\= N,
    N1 #= N-1,
    noFixpoint(Xs,N).   

derangement(L,N) :-
    permut(L,N),
    noFixpoint(L,0).

findDerangements(N,Ls) :-
    findall(L,derangement(L,N),Ls).

With derangement(L,N) we can now simply generate derangements of a certain a size or all of them (of a certain size) with findDerangements(N,Ls).

 findDerangements(4,Ls), length(Ls,N).
 Ls = [[2, 1, 4, 3], [2, 3, 4, 1], [2, 4, 1, 3], [3, 1, 4, 2], [3, 4, 1, 2], [3, 4, 2|...], [4, 1|...], [4|...], [...|...]],
 N = 9.

 ?- findDerangements(5,Ls), length(Ls,N).
 Ls = [[2, 1, 4, 5, 3], [2, 1, 5, 3, 4], [2, 3, 1, 5, 4], [2, 3, 4, 5, 1], [2, 3, 5, 1|...], [2, 4, 1|...], [2, 4|...], [2|...], [...|...]|...],
 N = 44.

You can try it out here ideone link - source

Answer 2

None of the derangements can start with $1$.

They can start with $2$, so let's find some of those.

The next digit can be $1$. (We're left with $3,4,5$.)

The third digit can't be $3$, but it can be $4$. The fourth digit can be $3$.

However, the last digit can't be $5$, so go back a place and put the $5$ there. The $3$ can be put in the last place.

So we have $21453$ as the first derangement.

Replace the $4$ with a $5$. Then, $3$ works in the fourth place, and $4$ works in the fifth.

So we have $21534$ as the next derangement.

Replacing the $3$ with $4$ doesn't work.

Next, let's try $23...$ We can put $1$ in the third place. $4$ doesn't work in the fourth place, but $5$ does. $4$ works in the last place.

So we have $23154$ as the next derangement.

Next, to $234..$ Both $1$ and $5$ can work in the fourth place, but $5$ does not work in the last place.

So we have $23451$ as the next derangement.

Next, to $235..$ Now, $1$ works in the fourth place, but $4$ does not. $1$ works in the last place.

So we have $23514$ as the next derangement.

And so on. Just find them like this smallest to largest.