Mélange d'une liste

D'après 2021, Métropole, Candidats libres, J2, Ex. 4

On s'intéresse dans cet exercice à un algorithme de mélange des éléments d'une liste.

1. Pour la suite, il sera utile de disposer d'une fonction echange qui permet d'échanger dans une liste valeurs les éléments d'indice i et j.

Expliquer pourquoi le code Python ci-dessous ne réalise pas cet échange et en proposer une modification.

🐍 Script Python

def echange(valeurs, i, j):
    valeurs[j] = valeurs[i]
    valeurs[i] = valeurs[j]

Réponse

On perd la valeur initiale de list[j] dès la première instruction.

On peut procéder de deux façons différentes :

• Avec une variable temporaire :

🐍 Script Python

def echange(valeurs, i, j):
    temp = valeurs[j]
    valeurs[j] = valeurs[i]
    valeurs[i] = temp

• En utilisant l'affectation multiple :

🐍 Script Python

def echange(valeurs, i, j):
    valeurs[i], valeurs[j] = valeurs[j], valeurs[i]

2. La documentation du module random de Python fournit les informations ci-dessous concernant la fonction randint :

randint(a, b)

Renvoie un entier aléatoire N tel que a <= N <= b. Alias pour randrange(a, b + 1).

Parmi les valeurs ci-dessous, quelles sont celles qui peuvent être renvoyées par l'appel randint(0, 10) ?

• 0
• 1
• 3.5
• 9
• 10
• 11

Réponse

L'appel randint(0, 10) renvoie une valeur entière entre 0 et 10 inclus l'un et l'autres.

Donc 0, 1, 9 et 10 sont des valeurs possibles.

3. Le mélange de Fischer-Yates est un algorithme permettant de permuter aléatoirement les éléments d'une liste. On donne ci-dessous une mise en œuvre récursive de cet algorithme en Python.

from random import randint

def melange(valeurs, i):
    print(valeurs)
    if i > 0:
        j = randint(0, i)
        echange(valeurs, i, j)
        melange(valeurs, i - 1)

3.a. Expliquer pourquoi la fonction melange se termine toujours.

Réponse

On suppose que i est un entier positif compris entre 0 et l'indice du dernier élément de la liste (len(valeurs) - 1).

Lors des appels récursifs, on décrémente la valeur de i et ces appels n'ont lieu que si cette valeur est strictement positive. Donc la fonction s'arrêtera toujours.

3.b. Lors de l'appel de la fonction melange, la valeur du paramètre i doit être égal au plus grand indice possible de la liste valeurs.

Pour une liste de longueur \(n\), quel est le nombre d'appels récursifs de la fonction melange effectués, sans compter l'appel initial ?

Réponse

Pour une liste de longueur \(n\), on appelle tout d'abord melange(valeurs, n - 1).

Le premier appel récursif est donc melange(valeurs, i - 2). Il est suivi d'appels récursifs correspondants aux différents indices de valeurs jusqu'au dernier appel melange(valeurs, 0).

Donc il y a \(n-1\) appels récursifs.

3.c. On considère le script ci-dessous :

🐍 Script Python

valeurs = [x for x in range(5)]
melange(valeurs, 4)

On suppose que les valeurs successivement renvoyées par la fonction randint sont 2, 1, 2 et 0.

Les deux premiers affichages produits par l'instruction print(valeurs) de la fonction melange sont :

• Premier affichage : [0, 1, 2, 3, 4],
• Deuxième affichage : [0, 1, 4, 3, 2].

Donner les affichages suivants produits par la fonction melange.

Réponse

On a les étapes suivantes :

Valeur de ind	Valeur de valeurs affichée	Valeur renvoyée par randint
ind = 4	[0, 1, 2, 3, 4]	2
ind = 3	[0, 1, 4, 3, 2]	1
ind = 2	[0, 3, 4, 1, 2]	2
ind = 1	[0, 3, 4, 1, 2]	0
ind = 0	[3, 0, 4, 1, 2]

3.d. Proposer une version itérative du mélange de Fischer-Yates.

Réponse

🐍 Script Python

from random import randint

def melange(valeurs):
    indice_dernier = len(valeurs) - 1
    for i in range(indice_dernier, 0, -1):
        j = randint(0, i)
        echange(valeurs, i, j)