Exo bac C4.EB1

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 lst les éléments d'indice i1 et i2.

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

def echange(lst, i1, i2):
    lst[i2] = lst[i1]
    lst[i1] = lst[i2]

2. La documentation du module random de Python fournit les informations ci-dessous concernant la fonction 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 randint(0, 10) ?

0     1     3.5     9     10     11

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(lst, ind):
    print(lst)
    if ind > 0:
        j = randint(0, ind)
        echange(lst, ind, j)
        melange(lst, ind-1)

a. Expliquer pourquoi la fonction melange se termine toujours.

b. Lors de l’appel de la fonction melange, la valeur du paramètre ind doit être égale au plus grand indice possible de la liste lst.

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 ?

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

lst = [v for v in range(5)]
melange(lst, 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(lst) de la fonction melange sont :

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

Donner les affichages suivants produits par la fonction melange.

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

Afficher la correction

1)

Le code proposé écrase le contenu de lst[i2]. Ce contenu n'est donc plus "disponible" pour être mis dans lst[i1]

Version modifiée :

def echange(lst, i1, i2):
    temp = lst[i2]
    lst[i2] = lst[i1]
    lst[i1] = temp

ou

def echange(lst, i1, i2):
    lst[i1], lst[i2] = lst[i2], lst[i1]

2)

Les valeurs qui peuvent être renvoyées par randint(0, 10) sont : 0, 1, 9 et 10.

3)

3.a)

La fonction mélange se termine toujours car :

  • - la fonction est rappelée récursivement avec une valeur du paramètre ind strictement inférieure à la valeur précédente (elle est rappelée avec ind-1),
  • - la fonction n'est rappelée que si le paramètre ind est strictement positif.

Donc, nécessairement, la fonction mélange sera rappelée de façon récursive un nombre fini de fois. En fait pour les valeurs du paramètre ind comprise entre la valeur du paramètre du premier appel et 1.

3.a)

Notons lg la longueur de la liste.

Le plus grand indice de la liste est lg-1.

Si l'on ne compte pas le premier appel, la fonction récursive est rappelée pour des valeurs du paramètre ind allant de lg-2 à 1. Elle est donc rappelée lg-2 fois.

3.c)

Les affichages successifs sont : 

[0, 1, 2, 3, 4]
[0, 1, 4, 3, 2] # car ind=4 et j=2
[0, 3, 4, 1, 2] # car ind=3 et j=1
[0, 3, 4, 1, 2] # car ind=2 et j=2
[3, 0, 4, 1, 2] # car ind=1 et j=0

3.d)

from random import randint
def melange_iteratif(lst):
    ind = len(lst) - 1
    while ind > 0:
        j = randint(0, ind)
        echange(lst, ind, j)
        ind = ind - 1