Dérangement et Python

Bonjour

Je me suis donné un exercice sur Python, écrire un programme derange retournant la liste des dérangements de $\{1, 2, 3, ..., n\}$ pour $n\geq 2$.

Il y a la méthode bourrin qui consiste à écrire toutes les permutations et à supprimer celles possédant un point fixe.

def perm(A, k):
    r = [[]]
    for i in range(k):
        r = [[a] + b for a in A for b in r if a not in b]
    return r

def der(n):
    A=[k for k in range(1,n+1)]
    p=perm(A,n)
    return [i for i in p if not any(i[k] == A[k] for k in range(n))]

J'ai cherché quelque chose de moins calculatoire, je me suis appuyé sur la démonstration par récurrence de leur dénombrement : $D_{n+2}=(n+1)(D_{n+1}+D_n)$ en suivant ce document : http://www.klubprepa.fr/Site/Document/ChargementExtrait.aspx?IdDocument=3680

def permuter(P,L):  # permute la liste L selon la permutation P
    R=[L[l-1] for l in P]
    return(R)

def type1(M,s):  # dérangement du "type n-1"
    L=[]
    for m in M:
        for k in range(1,s+1):
            n=permuter(m,[j for j in range(1,k)]+[s+1]+[j for j in range(k+1,s+1)])+[k]
            print(n)
            L+=[n]
    return(L)
   
def type2(M,s):   # dérangement du "type n-2"
    L=[]
    for m in M:
        for k in range(1,s+2):
            n=permuter(m,[j for j in range(1,k)]+[j for j in range(k+1,s+2)])+[k]
            n.insert(k-1,s+2)
            L+=[n]
    return(L)

def derange(n):
    L,M=[],[[2,1]]
    for k in range(3,n+1):
        L,M=M,type2(L,k-2)+type1(M,k-1)
    return(M)

>>> derange(3)
[[2, 3, 1], [3, 1, 2]]

>>> derange(4)
[[4, 3, 2, 1], [3, 4, 1, 2], [2, 1, 4, 3], [2, 3, 4, 1], [4, 3, 1, 2], [2, 4, 1, 3], [3, 4, 2, 1], [3, 1, 4, 2], [4, 1, 2, 3]]

>>> derange(5)
[[5, 3, 4, 2, 1], [3, 5, 4, 1, 2], [2, 4, 5, 1, 3], [2, 3, 1, 5, 4], [5, 4, 2, 3, 1], [4, 5, 1, 3, 2], [4, 1, 5, 2, 3], [3, 1, 2, 5, 4], [4, 3, 2, 5, 1], [4, 3, 5, 1, 2], [4, 5, 2, 1, 3], [5, 3, 2, 1, 4], [3, 4, 5, 2, 1], [3, 4, 1, 5, 2], [5, 4, 1, 2, 3], [3, 5, 1, 2, 4], [2, 5, 4, 3, 1], [5, 1, 4, 3, 2], [2, 1, 4, 5, 3], [2, 1, 5, 3, 4], [2, 3, 4, 5, 1], [5, 3, 4, 1, 2], [2, 5, 4, 1, 3], [2, 3, 5, 1, 4], [4, 3, 5, 2, 1], [4, 3, 1, 5, 2], [4, 5, 1, 2, 3], [5, 3, 1, 2, 4], [2, 4, 5, 3, 1], [5, 4, 1, 3, 2], [2, 4, 1, 5, 3], [2, 5, 1, 3, 4], [3, 4, 2, 5, 1], [3, 4, 5, 1, 2], [5, 4, 2, 1, 3], [3, 5, 2, 1, 4], [3, 5, 4, 2, 1], [3, 1, 4, 5, 2], [5, 1, 4, 2, 3], [3, 1, 5, 2, 4], [4, 5, 2, 3, 1], [4, 1, 5, 3, 2], [4, 1, 2, 5, 3], [5, 1, 2, 3, 4]]

>>> len(derange(5))
44

Je suis preneur de toutes remarques pour améliorer ce code. Je me pose notamment la question suivante : est-il possible d'écrire la fonction type2 avec une liste en compréhension ? Pour type1 je sais faire, mais pour type2 la méthode .insert() me bloque.

def type1_compact(M,s):
    return [permuter(m,[j for j in range(1,k)]+[s+1]+[j for j in range(k+1,s+1)])+[k] for m in M for k in range(1,s+1)]

Je peux me passer de la fonction permuter vue comme elle est courte.

J'ai réfléchi à intégrer les fonctions type1 et type2 directement dans derange, mais je n'en vois le gain en terme de ligne (par contre il y a probablement une économie sur les appels de fonction du coup ?).

La démonstration combinatoire de $D_n=nD_{n-1}+(-1)^n$ donnée dans ce papier devrait pouvoir permettre d'élaborer un algorithme plus efficace, mais cela me semble compliqué à écrire.

Merci.