Étude : mélanger un tableau

TBD complexité amortie ?

Nous allons étudier deux algorithmes permettant de mélanger un tableau.

Commençons par identifier le problème. Nous allons utiliser le problème suivant, qui consiste à rendre une permutation des $n$ premiers entiers :

Une permutation d'un tableau $T$ de taille $n$ est un tableau $\sigma(T)$ de taille $n$ où $\sigma(T)[i] = T[\sigma(i)]$ avec $\sigma$ une bijection de $[0 .. n-1]$.

L'algorithme que nous allons montrer ici nécessite que l'on puisse obtenir un entier aléatoire plus petit qu'un nombre donné $n$. On va donc considérer que l'on a une fonction randrange de complexité $\mathcal{O}(1)$ qui résout le problème "randrange" suivant :

On ne va pas définir plus que ça la notion d'aléatoire en informatique. On va ici prendre la définition mathématique : rend un nombre entre $a$ et $b$ de façon équiprobable, et considérer que c'est ok.

Remarques préliminaires

from random import randrange

def aléatoire(T):
    T_prim = []
    for i in range(len(T)):
        T_prim.append(T[randrange(len(T))])

    return T_prim

Borne min du problème

Existence d'un algorithme

Avant de chercher plus loin commençons par montrer qu'il existe un algorithme pour résoudre le problème. Si l'on possède une liste de toutes les permutations possibles, l'algorithme suivant fonctionne :

soit P un tableau contenant chaque permutation de T une fois

i = randrange(n!)
rendre P[i]

Il nous reste à créer toutes les permutations possibles d'un tableau. C'est ce que fait l'algorithme suivant.

Toutes les permutations

Remarquez que dans le cas général, trouver toutes les permutations d'un tableau d'entier de taille $n$ revient à trouver toutes les bijections de $[0 .. n-1]$, donc toutes les permutations de $S = [0, 1, \dots, n-1]$.

En effet, il est clair que pour tout tableau d'entiers $T$, $\sigma(T)[i] = T[\sigma(S)[i]]$ pour tout $0 \leq i < n$. Nous allons donc nous concentrer sur le problème suivant :

Toutes les permutuations de $[0, 1, \dots, n-1]$

Pour trouver toutes les permutations d'un tableau on peu utiliser une technique similaire à celle utilisée pour le compteur binaires : créer une fonction qui trouve le successeur d'un tableau.

Pour cela, il nous faut :

1. trouver un ordre pour les tableaux d'entiers
2. caractériser l'ensemble de nos tableaux

L'ordre entre les tableau d'entier classique est l'ordre lexicographique :

Dans notre cas, nous ne considérons pas pas tous les tableaux d'entiers, uniquement toutes les permutations de $[0 .. n-1]$.

Essayons de trouver le successeur d'une permutation $S_i$ , c'est à la plus petite des permutations plus grande que $S_i$. Ceci peut se faire de façon efficace en considérant l'indice $i^{\star}$ le plus petit indice tel que $S_i[i^{\star}:]$ est un tableau rangé par ordre décroissant.

Une fois le successeur caractérisé, il nous reste à implémenter la fonction.

def successeur(T):
    i = len(T) - 2
    while i >= 0 and T[i] > T[i + 1]:
        i -= 1

    i1 = i
    i_star = i + 1

    i = i_star
    j = len(T) - 1
    while i < j:
        T[i], T[j] = T[j], T[i]
        i += 1
        j -= 1

    
    for i2 in range(i_star, len(T)):
        if T[i2] > T[i1]:
            T[i2], T[i1] = T[i1], T[i2]
            return

Énumérer tous les successeurs prend alors $\mathcal{O}(n!)$ opérations en utilisant les arguments données pour l'analyse par agrégat du compteur binaire, on peut partitionner l'ensemble des permutations (il y en a $n!$ au total) selon l'ordre de ses derniers éléments.

Pour tout $1 \leq i < n$, on peut séparer l'ensemble en 2 parties selon que $S[n-i] < S[n-i+1]$ ou $S[n-i] > S[n-i+1]$. Ces deux parties sont de même cardinal. Parmi toutes les permutations telles que $S[n-i] < S[n-i+1]$, le même raisonnement que précédemment nous indique que la moitié sont telles que $S[n-i+1] > S[n-i+2]$. On peut encore recommencer en considérant l'ensemble des permutations telles que $S[n-i] < S[n-i+1]$ et $S[n-i+1] > S[n-i+2]$, la moitié d'entres elles sont telle que $S[n-i+2] > S[n-i+3]$...

On arrive ainsi à démontrer par récurrence que l'ensemble $\mathcal{S}_i$ des permutations S telles que :

1. $S[n-i] < S[n-i+1]$
2. $S[n-i+j] > S[n-i+j+1]$ pour tout $0 < j < i-1$

est de cardinal $\frac{n!}{2^i}$. Comme il faut de plus de l'ordre de $i$ opérations pour traiter une permutation de $\mathcal{S}_i$, on en conclut que la complexité totale de l'énumération de toutes les permutations vaut :

$$ C = \sum_{i=1}^{n}i\cdot \frac{n!}{2^i} + n = n! \cdot \sum_{i=1}^{n}\frac{i}{2^i} + n $$

En effet, l'union des $\mathcal{S}_i$ plus l'ensemble contenant uniquement la partition triée par ordre décroissant (qui nécessite $n$ opérations pour être traitée) partitionne l'ensemble des permutations.

En poussant le calcul comme on a fait pour le compteur binaires, on trouve :

$$ C = n! \cdot (2-\frac{n+2}{2^n}) + n = \mathcal{O}(n!) $$

Comme pour le compteur binaire, on remarque que la complexité de l'énumération de toutes les permutations est de l'ordre du nombre de permutations et qu'en moyenne $n-i^\star$ vaut 2.

Toutes les permutations de $T$

Si l'énumération de toutes les permutations est de l'ordre du nombre de permutations, si l'on veut toutes les stocker il va falloir dupliquer la liste rendue par successeur car cet algorithme modifie la liste qui lui est passée en paramètre. La complexité devient alors $\mathcal{O}(n\cdot n!)$.

def permutations(données):
    P = []  # va contenir les permutations de T
    T = list(range(len(données)))

    T_fin = list(T)
    T_fin.reverse()
    P.append([données[i] for i in T])

    while T != T_fin:
        successeur(T)
        P.append([données[i] for i in T])
        print(T)

    return P

L'algorithme permutations rend un tableau contenant toutes les permutations du tableau passé en entrée. La taille de la sortie est donc très grande.

Par exemple pour permutations([1, 2, 3, 4]) va rendre la liste :

[[1, 2, 3, 4], [1, 2, 4, 3], [1, 3, 2, 4],
 [1, 3, 4, 2], [1, 4, 2, 3], [1, 4, 3, 2],
 [2, 1, 3, 4], [2, 1, 4, 3], [2, 3, 1, 4],
 [2, 3, 4, 1], [2, 4, 1, 3], [2, 4, 3, 1],
 [3, 1, 2, 4], [3, 1, 4, 2], [3, 2, 1, 4],
 [3, 2, 4, 1], [3, 4, 1, 2], [3, 4, 2, 1],
 [4, 1, 2, 3], [4, 1, 3, 2], [4, 2, 1, 3],
 [4, 2, 3, 1], [4, 3, 1, 2], [4, 3, 2, 1]]

On remarque que :

• le premier élément du tableau de sortie est le tableau initial
• le dernier élément du tableau de sortie est l'inverse du tableau initial
• que sont placés en premier les permutations ne changeant pas le 1er élément, puis celle où le 2nd élément est le premier, et ainsi de suite jusqu'à placer toutes les permutations où le dernier élément est le premier.

Un premier algorithme

Un algorithme de mélange utilisant permutations est alors de choisir 1 permutation parmi toutes les permutations d'un tableau en entrée :

from random import randrange

def mélange(T):
    P = permutations(T)
    i = randrange(len(P))
    return P[i]

Si la la fonction randrange de python rend un nombre aléatoire équiprobable mélange doit bien rendre chaque permutation de façon équiprobable.

Expérimentations

Vérifions expérimentalement que notre algorithme rend bien une permutation équiprobable.

On va compter le nombre de fois où chaque permutation apparaît :

def compte_mélange(taille_liste, nombre_lancer):
    T = list(range(taille_liste))
    P = permutations(T)
    N = [0] * len(P)

    for i in range(nombre_lancer):
        T2 = mélange(T)
        N[P.index(T2)] += 1
    
    return N

nombre = compte_mélange(5, 1000)
print(min(nombre), sum(nombre) / len(nombre), max(nombre))

Représentons graphiquement les résultats !

On a mis en abscisse les différentes permutations et en ordonnée leur nombre

import matplotlib.pyplot as plt

def graphique_mélange(taille_tableau, nombre_iteration):

    nombre = compte_mélange(taille_tableau, nombre_iteration)

    fig, ax = plt.subplots(figsize=(20, 5))

    ax.set_xlim(0, len(nombre) - 1)
    ax.set_ylim(0, max(nombre) + 1)

    ax.plot(nombre, label="nombre")
    ax.axhline(y=nombre_iteration / len(nombre), color="red", label="théorique")

    ax.legend(loc='upper left', bbox_to_anchor=(1, 1))
    ax.set_title(str(nombre_iteration) + " permutations d'un tableau à " + str(taille_tableau)+ " éléments")

    plt.show()

graphique_mélange(6, 10000)

Pour une exécution de graphique_mélange(6, 10000), j'obtiens le résultat suivant :

Les permutations semblent bien équiprobables.

Complexité

Notre algorithme est bien une solution au problème, mais sa complexité est cependant prohibitive.

Comme on a considéré que la complexité de randrange est de $\mathcal{O}(1)$, la complexité de mélange est de l'ordre de la complexité de permutations donc : $\mathcal{O}((n+2)!)$ avec $n$ la taille du tableau T. L'algorithme mélange n'est pas utilisable en pratique car n! est trop gros

Algorithme de Fisher-Yates ou de Knuth

L'algorithme que l'on va montrer maintenant, dit de fisher-yates ou encore de Knuth, va également résoudre le problème "permutation", mais de façon bien plus élégante.

from random import randrange

def mélange_Knuth(T):
    T2 = list(T)
    for i in range(len(T2) - 1, -1, -1):
        j = randrange(i + 1)
        T2[i], T2[j] = T2[j], T2[i]
    return T2

Finitude

Une unique boucle for sur la longueur du tableau : l'algorithme finit toujours.

Complexité

Comme randrange est considérée en $\mathcal{O}(1)$, la complexité totale de l'algorithme est (ligne à ligne) :

1. —
2. —
3. —
4. $\mathcal{O}(n)$ puisque l'on copie un tableau
5. une boucle for de $\mathcal{O}(n)$ itérations
6. utilisation de randrange en $\mathcal{O}(1)$
7. 2 affectations et 2 recherches dans un tableau : $\mathcal{O}(1)$
8. retour de fonction : $\mathcal{O}(1)$

Ce qui donne une complexité de :

Vérification expérimentale

Si, en exécutant l'algorithme on se rend bien compte qu'il mélange le tableau en entrée, ce n'est pas très clair à première vue que toutes les permutations sont équiprobables.

On va le vérifier expérimentalement en regardant les permutations du tableau [1, 2, 3, 4, 5, 6]. On va compter combien de fois apparaît chaque permutation (il y en a $6! = 720$) pour un grand nombre de tirage.

On pourrait reprendre le code précédent et l'adapter pour notre mélange, mais il y aurait beaucoup de duplication de code. En fait seule le nom de la permutation changerait.

On préfère donc faire directement des méthodes génériques, en passant la fonction à utiliser en paramètre

def compte_mélange_générique(fonction_mélange, taille_liste, nombre_lancer):
    T = list(range(taille_liste))
    P = permutations(T)
    N = [0] * len(P)

    for i in range(nombre_lancer):
        T2 = fonction_mélange(T)
        N[P.index(T2)] += 1
    
    return N

def graphique_mélange_générique(fonction_mélange, taille_tableau, nombre_iteration):

    nombre = compte_mélange_générique(fonction_mélange, taille_tableau, nombre_iteration)

    fig, ax = plt.subplots(figsize=(20, 5))

    ax.set_xlim(0, len(nombre) - 1)
    ax.set_ylim(0, max(nombre) + 1)

    ax.plot(nombre, label="nombre")
    ax.axhline(y=nombre_iteration / len(nombre), color="red", label="théorique")

    ax.legend(loc='upper left', bbox_to_anchor=(1, 1))
    ax.set_title(str(nombre_iteration) + " permutations d'un tableau à " + str(taille_tableau)+ " éléments")

    plt.show()

De là, pour utiliser la fonction mélange :

graphique_mélange_générique(mélange, taille_tableau, nombre_iteration)

et pour utiliser la fonction mélange_Knuth :

graphique_mélange_générique(mélange_Knuth, taille_tableau, nombre_iteration)

Vous devriez obtenir le résultat suivant :

Le nombre de permutations trouvé oscille bien autour de la valeur théorique.

Preuve de programme

On suppose que le tableau d'entrée possède $n$ éléments.

On va montrer que les probabilités de sortie de chaque permutation sont bien équiprobables de trois façons différentes. Toutes les démonstrations reposent sur le fait :

• qu'une fois un élément choisi, il n'est plus jamais déplacé
• tous les éléments seront choisis une fois dans l'algorithme (il y a $n$ itérations et on choisit un élément à chaque itération)

Preuve par probabilités

On va calculer la probabilité que l'élément originellement en position $i$ se retrouve en position $n-j$ à la fin de l'algorithme. Si notre tirage est équiprobable, cette probabilité doit être égal à $\frac{1}{n}$ quelque soient $i$ et $j$.

Pour que cela arrive, il faut que :

• l'élément n'ait pas été pris pendant la première itération : il y a $\frac{n-1}{n}$ chances que ça arrive (on ne choisit pas notre élément parmi $n$ possibles : $1-\frac{1}{n} = \frac{n-1}{n}$)
• l'élément n'ait pas été pris pendant la deuxième itération : il y a $\frac{n-2}{n-1}$ chances que ça arrive (on ne choisit pas notre élément parmi $n - 1$ possibles : $1-\frac{1}{n-1} = \frac{n-2}{n-1}$)
• ...
• l'élément n'ait pas été pris pendant la $j-1$ ème itération : il y a $\frac{n-j+1}{n-j+2}$ chances que ça arrive (on ne choisit pas notre élément parmi $n-(j-1) +1$ possibles : $1-\frac{1}{n-j+2} = \frac{n-j+1}{n-j+2}$)
• l'élément ait été pris pendant la $j$ ème itération : il y a $\frac{1}{n-j+1}$ chances que ça arrive

De là, la probabilité que l'élément originellement en position $i$ se retrouve en position $n-j$ à la fin de l'algorithme est :

$$\frac{n-1}{n} \cdot \frac{n-2}{n-1} \cdot \ ...\ \cdot \frac{n-j+1}{n-j+2} \cdot \frac{1}{n-j+1} = \frac{1}{n}$$

C'est bien équiprobable !

Preuve par dénombrement

A la $i$ème itération on choisit un élément parmi $n-i+1$, et comme $i$ croit de $1$ à $n-1$, on a $n!$ parcours différents de l'algorithme.

L'algorithme choisit donc bien 1 permutation parmi $n!$, toutes différentes : il y a bien équiprobabilité des choix.

Preuve par récurrence

1. lors de la première itération, on choisit un entier $k$ entre $0$ et $n-1$ et on échange l'élément d'indice $k$ avec celui d'indice $n-1$. Cet élément ne sera plus jamais changé dans la suite de l'algorithme. On en conclut que chaque élément du tableau d'entrée à la même chance d'être en dernière place de la permutation de sortie.
2. une fois la première itération terminée, tout se passe comme si on exécutait l'algorithme avec un tableau de taille $n-1$ contenant tous les éléments du tableau de départ sauf celui placé lors de la 1ère itération.
3. donc si l'algorithme fonctionne pour des tableau de longueur $n-1$, il fonctionne aussi pour des tableau de longueur $n$.
4. on peut terminer la preuve en remarquant que si le tableau a une longueur de 1, on a bien en sortie l'unique permutation du tableau en entrée.

Méthodes de python

Python utilise la méthode shuffle du module random pour mélanger une liste.

La méthode utilisée par shuffle est l'algorithme de Knuth / Fisher-Yates.

Attention

On va montrer trois écueils du mélange :

• le premier lié à un mauvais choix d'algorithme (mais pas évident à voir) : atteindre toutes les permutations n'est pas une garanti d'équiprobabilité.
• le second montre que si votre algorithme dépend d'un autre, il faut aussi analyser ses performances.
• le troisième lié aux biais cognitifs humains qui ne voient pas l'aléatoire comme ce qu'il est réellement.

A trop mélanger on ne mélange pas bien

Si vous implémentez un algorithme de mélange mais qu'il peut obtenir plusieurs fois la même permutation avec des opérations différentes, alors vous risquez fort de ne pas être équiprobable. Illustrons ceci par un exemple.

On sait que toute permutation d'un tableau peut être atteinte en échangeant itérativement une paire d'éléments (on appelle ça une décomposition en produit de transpositions). On peut même montrer qu'il suffit d'en faire au plus la taille du tableau moins 1.

On en déduit l'algorithme de mélange suivant :

1. soit $T$ un tableau à $n$ éléments
2. répétez $n-1$ fois
   1. soit i un nombre aléatoire entre 0 et $n-1$
   2. soit j un nombre aléatoire entre 0 et $n-1$
   3. échanger $T[i]$ et $T[j]$

def mélange_transposition(T):
    T2 = list(T)
    for k in range(len(T2) - 1):
        i = randrange(len(T2))
        j = randrange(0, len(T2))

        T2[i], T2[j] = T2[j], T2[i]
    return T2

Vous devriez obtenir quelque chose du type :

On remarque que les premières permutations sont surreprésentées par rapport à ce qu'on devrait avoir. On remarque aussi qui'l y a des pics réguliers que l'on n'observe pas avec le mélange de Knuth. Ceci est du au fait que l'on peut produire une même permutation de plusieurs manière avec cet algorithme : on produit plus facilement certaines permutations que d'autres, ce qui rend l'algorithme non équiprobable.

Nous allons ici juste montrer que les permutations en sorties ne sont pas équiprobables. La probabilité que l'élément d'indice $l$ ne soit jamais choisi pendant l'algorithme est :

$$P_n = (\frac{n-1}{n} \cdot \frac{n-1}{n})^n$$

Puisque l'algorithme a choisi pour chacune des $n$ étapes de la boucle for un élément différent de $l$ pour les lignes 4 et 5.

Or :

$$ P_n = ((1 - \frac{1}{n})^n)^2 \xrightarrow[n\to\infty]{} (\frac{1}{e})^2 > 0 $$

Ceci est incompatible avec l'équiprobabilité puisque :

• $P_n$ est plus petit que la probabilité que l'élément d'indice $l$ soit en position $l$ à la fin de l'algorithme (c'est même strictement plus petit puisqu'il peut n'avoir jamais bougé ou être revenu à sa place)
• s'il y a équiprobabilité, la probabilité que l'élément d'indice $l$ soit en position $l$ à la fin de l'algorithme doit être de $\frac{1}{n}$
• il existe $N_0$ tel que pour tout $n \geq N_0$, on a $\frac{1}{n} < (\frac{1}{e})^2$

C'est bien ce qu'on remarque sur la figure avec la surreprésentation de la première permutation qui est la permutation où rien n'a bougé.

randrange doit être puissant

En informatique, il est impossible de tirer un nombre au hasard. On est obligé d'utiliser des suites périodiques qui se comportent comme des nombre aléatoires. On appelle ces suites pseudo-aléatoires.

La période de cette suite doit être très grande pour pouvoir générer toutes les permutations : la période doit être plus grande que $n!$. Sinon, certaines permutations seront sur-représentées.

Par exemple, pour pouvoir mélanger un paquet de 52 cartes de façon équiprobable en utilisant une suite pseudo-aléatoire, il faut que sa période soit plus que grande que $52! = 80658175170943878571660636856403766975289505440883277824000000000000 \sim 2^{226}$

Attention aux humains

La perception de ce qu'est l'aléatoire n'est pas aisée. Lorsque l'on joue à un jeu de cartes par exemple, le biais de confirmation tend à se rappeler les évènement très défavorables au détriment de ceux juste normaux. De plus, lorsque l'on demande à des humains de tirer des nombres aléatoires, souvent ils ne le sont pas :

• Lorsque l'on demande à des humains de choisir un nombre aléatoirement entre 1 et 10, ils répondent le plus souvent 7.
• lorsque l'on demande à des humains d'écrire une suite aléatoire de 200 nombres valant 0 ou 1, il y aura une sous-représentation des longues séquences avec le même nombre : cela ne fait pas aléatoire d'avoir plein de fois le même nombre à la suite (alors que statistiquement, il faut bien que ces séquences existent).

Autres références

Quelques autres articles sur le sujet :

• https://possiblywrong.wordpress.com/2014/12/01/card-shuffling-algorithms-good-and-bad/
• https://blog.codinghorror.com/the-danger-of-naivete/
• https://www.stashofcode.fr/tri-aleatoire-des-elements-dun-tableau/