Permutation aléatoire

I) Présentation

1) Objectif

On rappelle qu'une permutation d'un ensemble fini est un rangement avec ordre de tous les éléments de E.
Par exemple, les permutations de l'ensemble {1, 2, 3} sont: [1, 2, 3] , [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1].

Etant donné un entier n ∈ N * , on veut calculer une permutation aléatoire (au hasard) perm_alea(n) de l'ensemble {1, 2,..., n}.

On dispose de la fonction random.randint(a, b) qui calcule un entier aléatoire entre les entiers a et b (inclus).

2) Méthodes

On va étudier trois méthodes:

a) Une mauvaise idée

Calculer une liste de n nombres entiers aléatoires entre 1 et n autant de fois qu'il le faut, jusqu'à obtenir une permutation.

b) Une idée paraissant maladroite, mais qui tient finalement la route

Placer successivement les nombres 1, 2,..., n dans une liste “vide” de n éléments en cherchant de façon aléatoire et aveugle des places libres dans la liste.

c) Une idée moins naturelle, mais très efficace

Déranger aléatoirement la liste [1, 2, ..., n].

II) Algorithmes

On exploite la première idée et on propose pour commencer l'algorithme suivant:

import random

def perm_alea_0(n):
    s = [0] * n
    for i in range(n):
        s[i] = random.randint(1,n)
    return s

Q1) Expliquer pourquoi cet algorithme ne résout que “rarement” le problème. Que calcule perm_alea_0(n) ?

Q2) Prouver que la probabilité p(n) que perm_alea_0(n) soit effectivement une permutation de [1,2,...,n] est p ( n ) = n ! n n .
Calculer par exemple p(10).

Q3) Ecrire une fonction à valeurs booléennes verification(s) valant True si et seulement si la liste s de n entiers est une permutation de [1, 2,..., n].
On pourra par exemple commencer par trier la liste s.

Q4) Ecrire une fonction perm_alea_1(n) calculant effectivement une permutation aléatoire de [1, 2,..., n] en exploitant les fonctions perm_alea_0(n) et verification(s).

Q5) En faisant des tests, jusqu'à quelle valeur maximum de n peut-on aller pour avoir la réponse en moins de 3 secondes
environ ? Quel commentaire faire ?

On veut évaluer (pratiquement) la complexité C 1 ( n ) de cette fonction perm_alea_1(n). Le coût C(n) de cette fonction est le nombre de fois où l'on calcule un entier aléatoire avec randint().

Q6) Ecrire une fonction perm_alea_1_cout(n) modifiant un peu la fonction perm_alea_1() et calculant ce nombre C(n).

Q7) Ecrire une fonction perm_alea_1_cout_moyen(n, p) calculant la moyenne de C(n) sur p calculs de C(n) pour la même valeur de n.
Combien trouvez vous pour perm_alea_1_cout_moyen(10, 10) ? Ce résultat est-il conforme au calcul de probabilité de Q2) ? Pourquoi ?

Q8) Justifier que la complexité en moyenne de la fonction perm_alea_1(n) est C 1 ( n ) = O ( n n ( n - 1 ) ! )

On exploite maintenant la seconde idée.

    • On initialise une liste s = [s[0], s[1],..., s[n]] de n + 1 entiers à [0,..., 0]

    •• Pour k variant de 1 à n, on calcule de manière aléatoire à l'aide de la fonction randint() la place p ∈ {1,..., n} de k dans la liste s. Si cette place est libre (c'est à dire si s[p] = 0), on y place effectivement k, sinon on recalcule aléatoirement une autre place pour k, jusqu'à trouver une place libre où l'on place k.

    ••• Le résultat est alors s[1:] = [s[1], s[2],..., s[n]].

On peut exploiter s[0], qui semble inutile, dans l'écriture de la fonction demandée ci-dessous.

Q9) Ecrire une fonction perm_alea_2(n) calculant une permutation aléatoire de [1,2,...,n] en suivant ces consignes.

Q10) En faisant des tests, jusqu'à quelle valeur maximum de n peut-on aller pour avoir la réponse en moins de 3 secondes
environ ? Quel commentaire faire ?

On veut évaluer (pratiquement) la complexité de cette fonction perm_alea_2(n). Le coût C(n) de cette fonction est le nombre de fois où l'on calcule un entier aléatoire avec randint().

Q11) Ecrire une fonction perm_alea_2_cout(n) modifiant un peu la fonction perm_alea_2 et calculant ce nombre C(n).

Q12) Ecrire une fonction perm_alea_2_cout_moyen(n, p) calculant la moyenne de C(n) sur p calculs de C(n) pour la même valeur de n.
Combien trouvez vous pour perm_alea_2_cout_moyen(1000, 50) ? Ce résultat est-il surprenant ?

Q13) Vérifier numériquement qu'un équivalent de ce coût moyen, lorsque n tend vers l'infini, est n×ln(n). On peut (c'est difficile) démontrer ce résultat et donc la complexité moyenne de la fonction perm_alea_2(n) est C 2 ( n ) = O ( n ln ( n ) ) .

On exploite maintenant la troisième idée.

    • On initialise s à s = [1, 2,..., n]

    •• Pour i variant de n - 1 à 1, on calcule un nombre j aléatoire entre 0 et i puis on échange les termes s[i] et s[j]

Q14) Ecrire une fonction perm_alea_3(n) calculant une permutation aléatoire de [1,2,...,n] en exploitant cette idée.

Q15) Pour n = 3, expliquer en faisant par exemple un arbre que l'on obtient de manière équiprobable les 6 permutations possibles.

Q16) En faisant des tests, jusqu'à quelle valeur maximum de n peut-on aller pour avoir la réponse en moins de 3 secondes
environ ? Quel commentaire faire ?

Q17) Quelle est la complexité C 3 ( n ) de cette fonction ? (Le coût est toujours est le nombre de fois où l'on calcule un entier aléatoire avec randint()).

Q18) Chercher sur le net le nom de cette méthode (c'est un classique et c'est la bonne manière de procéder).

© 2014 - Eric Obermeyer      Powered by      Corrigé