En choisissant un ensemble de 100 nombres entiers aléatoires compris entre 1 et 9999, on souhaite estimer la probabilité d’obtenir au moins un doublon, c’est à dire deux nombres identiques dans cette liste. Utilisons un programme Python pour approcher cette probabilité.
Comment estimer la probabilité d’un doublon dans une liste aléatoire en Python ?
1ère étape : générer la liste de nombres entiers aléatoires en Python
Pour cela on va utiliser le module random et une boucle for pour générer 100 nombres entiers aléatoires.
[pastacode lang= »python » manual= »import%20random%0A%0Aliste_nombres_hasard%20%3D%20%5Brandom.randint(1%2C%209999)%20for%20x%20in%20range(100)%5D » message= » » highlight= » » provider= »manual »/]
1 et 9999 peuvent être remplacés par les bornes entre lesquelles vous souhaitez obtenir vos nombres aléatoires. 100 peut être remplacé par le nombre d’éléments voulus dans la liste.
2ème étape : extraire uniquement les doublons de la liste
On va utiliser le module iteration-utilities de Python.
[pastacode lang= »python » manual= »from%20iteration_utilities%20import%20duplicates%0Afrom%20iteration_utilities%20import%20unique_everseen%0A%0Adef%20recupListUnique(liste)%3A%0A%20%20%20%20%20%20%20%20if(len(list(unique_everseen(duplicates(liste)))))%20%3E%200%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return(1)%3B%0A%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return(0)%3B » message= » » highlight= » » provider= »manual »/]
Cette fonction permet d’abord avec list(unique_everseen(duplicates(liste))) de récupérer la liste avec les nombres apparaissant en doublons, puis de calculer sa longueur. La fonction renvoie 1 si au moins un doublon est trouvé et sinon 0, on peut ainsi compter les listes avec au moins 1 doublon.
3ème étape : placer les codes précédents dans une boucle pour approcher la probabilité
Voici donc le programme complet pour estimer la probabilité d’avoir au moins un doublon.
[pastacode lang= »python » manual= »import%20random%0A%0Afrom%20iteration_utilities%20import%20duplicates%0Afrom%20iteration_utilities%20import%20unique_everseen%0A%0Ai%20%3D%201%0Anb_listes_avec_au_moins_un_doublon%20%3D%200%20%23permet%20de%20compter%20les%20listes%20avec%20au%20moins%20un%20doublon…%0Aau_moins_un_doublon%20%3D%200%20%23variable%20renvoy%C3%A9e%20par%20la%20fonction%20%3A%201%20si%20au%20moins%20un%20doublon%20trouv%C3%A9%2C%20sinon%200%0A%0An%20%3D%2010000%20%23Nombre%20de%20simulations%20(plus%20n%20est%20grand%2C%20plus%20le%20programme%20se%20rapproche%20de%20la%20probabilit%C3%A9)%0A%0Afor%20i%20in%20range(n)%3A%0A%0A%20%20%20%20%20%20%20%20liste_nombres_hasard%20%3D%20%5Brandom.randint(1%2C%209999)%20for%20x%20in%20range(100)%5D%20%231%20et%209999%20sont%20les%20bornes%20pour%20le%20choix%20de%20l’entier%20al%C3%A9atoire.%20100%20correspond%20au%20nombre%20de%20listes%20g%C3%A9n%C3%A9r%C3%A9es%0A%0A%20%20%20%20%20%20%20%20def%20recupListUnique(liste)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if(len(list(unique_everseen(duplicates(liste)))))%20%3E%200%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return(1)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return(0)%3B%0A%0A%20%20%20%20%20%20%20%20nb_listes_avec_au_moins_un_doublon%20%3D%20nb_listes_avec_au_moins_un_doublon%20%2B%20recupListUnique(liste_nombres_hasard)%20%23Compte%20le%20nombre%20de%20liste%20avec%20au%20moins%201%20doublon%0A%0Aprint(%22Probabilit%C3%A9%20approch%C3%A9e%20d’un%20doublon%20%3A%20%22%2Bstr(round(nb_listes_avec_au_moins_un_doublon%2Fn*100%2C4))%2B’%25′)%20%23On%20affiche%20la%20fr%C3%A9quence%20du%20nombre%20de%20listes%20avec%20au%20moins%201%20doublon » message= » » highlight= » » provider= »manual »/]
Au global :
- on parcourt n fois une boucle (plus n est grand, plus on s’approche de la probabilité) ;
- dans cette boucle une liste de 100 nombres entiers entre 1 et 9999 est générée ;
- on appelle une fonction permettant de récupérer uniquement les doublons de la liste ;
- on vérifie la longueur de cette liste ;
- si elle est supérieure à 0, on ajoute 1 au nombre de listes avec au moins un doublon ;
- une fois les n boucles effectuées, on calcule la fréquence du nombre de listes avec au moins un doublon, en divisant le nombre de listes présentant un doublon par n, et en multipliant par 100 pour la présenter sous forme de pourcentage ;
- la loi des grands nombres nous permet d’approcher la probabilité d’obtenir un doublon par la fréquence obtenue.
Quelle probabilité de doublons pour notre exemple ?
En lançant le programme pour n assez grand, on constate que pour notre exemple, la probabilité d’avoir au moins 1 doublon dans une liste de 100 nombres entiers aléatoires choisis entre 1 et 9999 est d’environ 39%.
Le programme peut ensuite être modifié pour changer les bornes des entiers aléatoires choisis et le nombre d’éléments dans la liste. Commentez pour toute remarque ou question !