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.
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
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.
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.
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.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
En pièce jointe, un texte que j'ai écrit il y a quelques années pour les agrégatifs:
Merci pour ce document, je vais l'éplucher. J'en ai profité pour télécharger l'article de Jacques Désarménien qui propose une démonstration bijective de $D_n=nD_{n-1}+(-1)^n$.
Par ça ?
-- Schnoebelen, Philippe