En Python, une liste est délimitée par des crochets. Pour ajouter un élément x à la fin d'une liste L,...
16
Activité CAPYTALE : Permutations et Secret Santa
Quelques rappels pour commencer
Ajouter un élément dans une liste
En Python, une liste est délimitée par des crochets. Pour ajouter un élément x à la fin d'une liste L, on utilise alors la syntaxe L.append(a).
L = [1, 3, 7]
print(L) # affiche [1, 3, 7]
L.append(2)
print(L) # affiche [1, 3, 7, 2]
L.append(8)
print(L) # affiche [1, 3, 7, 2, 8]
L'ajout de plusieurs éléments à une liste peut par ailleurs se faire à l'aide d'une boucle for.
# On initialise une liste L vide
L = []
# On définit une fonction f
def f(x):
return x**2 + 3*x +4
# on ajoute les images par f des entiers de 1 à 7 à la liste L
# Attention aux arguments de range : la liste débute au premier nombre mais se termine un cran avant le deuxième nombre donné
# range(1,8) donne donc bien les entiers de 1 à 7
for i in range(1,8):
L.append(f(i))
print(L)
Retirer un élément d'une liste
Pour retirer un élément x d'une liste L, on utilise la syntaxe L.remove(x). Attention, seule la première occurrence de cet élément est retirée !
L = [1, 3, 7, 8, 9, 5, 3, 2]
print(L) # affiche [1, 3, 7, 8, 9, 5, 3, 2]
L.remove(7)
print(L) # affiche [1, 3, 8, 9, 5, 3, 2]
# Seule la première occurrence du nombre donné en argument est retirée
L.remove(3)
print(L) # affiche [1, 8, 9, 5, 3, 2]
Choix d'un élément au hasard
Pour choisir au hasard un élément d'une liste de taille n, deux possibilités s'offrent à nous, toutes deux utilisant le modulerandomde Python :
on peut choisir un élément au hasard en utilisant la fonctionchoice;
on peut sélectionner une position au hasard entre 0 et n - 1 puis renvoyer l'élément situé à cette position.
# Première possibilité
from random import choice
L = [1, 3, 9, 4, 6, 7, 2]
x = choice(L)
print(x)
# Deuxième possibilité
from random import randint
L = [1, 3, 9, 4, 6, 7, 2]
x = randint(0, len(L) - 1)
print(L[x])
Permutation aléatoire de {0, 1, ..., n-1}
Génération d'une permutation
Pour générer une permutation aléatoire de l'ensemble {0, 1, ..., n - 1} en Python, on peut procéder comme suit.
On génère une première liste L qui contient tous les entiers de 0 à n - 1.
On initialise la permutation p comme étant une liste vide.
Tant que la liste L n'est pas vide :
- on choisit au hasard un élément de la liste L ;
- on ajoute cet élément à la liste p ;
- on retire cet élément de la liste L.
Exercice
Compléter la fonction perm_alea qui prend en argument un entier n et renvoie une permutation aléatoire de l'ensemble {0, 1 , ..., n-1} sous la forme d'une liste Python.
from random import choice
def perm_alea(n):
L = list(range(n))
p = ...
while L != [] :
# on choisit un élément au hasard dans la liste L
x = ...
# on retire x de la liste L
...
# on ajoute x à la liste p
...
return p
Remarque
Il existe en réalité une fonction du modulerandomqui permet de renvoyer un arrangement ou une permutation d'un ensemble : il s'agit de la fonction sample.
Permutation sans point fixe
Soit L une liste Python traduisant une permutation de l'ensemble {0, 1, ..., n - 1}.
On dit que L est une permutation sans point fixe si, pour tout entier i allant de 0 à n-1, on a L[i]
=
i. On dit également que L est un dérangement de l'ensemble {0, 1, ..., n-1}.
Par exemple :
L = [1, 2, 3, 0] est un dérangement de l'ensemble {0, 1, 2, 3}.
L = [3, 1, 0, 2] n'est pas un dérangement de l'ensemble {0, 1, 2, 3} : on a en effet L[1] = 1.
Exercice
Compléter la fonction est_derangement ci-dessous qui prend en argument une liste L et renvoie True si la liste L est une permutation sans point fixe et False sinon.
def est_derangement(L):
n = len(L)
for i in range(...) :
if L[i] == i :
return ...
return ...
Probabilité d'obtenir une permutation sans point fixe
On considère la fonctionmystereci-dessous.
1.Expliquer le rôle de cette fonction.
2.Exécuter cette fonction pour différentes valeurs des entiers n et N (y compris pour des grandes valeurs de N) puis interpréter le résultat dans le contexte de l'exercice.
def mystere(n, N):
C = 0
for i in range(N):
p = perm_alea(n)
if est_derangement(p):
C = C + 1
return C / N
mystere(10, 10000)
Secret Santa
Le Secret Santa est une tradition de Noël lors de laquelle les membres d'un groupe s'offrent des cadeaux.
Les noms de tous les participants sont inscrits sur des bulletins. Chaque participant se voit alors attribuer le nom d'un autre participant par le biais d'un tirage au sort. On espère qu'aucun de ces participants ne tire son propre nom : le cas échéant, on procède à un nouveau tirage.
Exercice
Compléter la fonction derangement_alea ci-dessous qui prend en argument un entier n et renvoie un dérangement aléatoire de taille n. Pour cela, on continuera de générer une permutation aléatoire jusqu'à ce que celle-ci soit sans point fixe.
def derangement_alea(n):
derangement = False
while not derangement :
p = ...
derangement = ...
return p
On peut alors utiliser la fonction secret_santa ci-dessous pour déterminer qui offrira un cadeau à qui.
def secret_santa(L):
d = derangement_alea(len(L))
for i in range(len(L)) :
print(L[i], "offre un cadeau à", L[d[i]])
L = ["Catherine", "Claire", "Evgény", "Hélène", "Jason", "Julie"]