Éliminer avec une liste Python

Les quatre outils suffisants

Le sujet ne demande rien d'exotique. Pour un objet L de type list en Python :

   L[i]      accède à l'élément d'indice i (le premier a l'indice 0)
   del L[i]  supprime l'élément d'indice i, la liste se referme
   len(L)    renvoie le nombre d'éléments
   a % b     reste de la division euclidienne de a par b

Exemple : si L = [1, 2, 3], alors après del L[1] la liste vaut [1, 3].

Modéliser le cercle

Un cercle n'existe pas en Python — mais une liste plus l'opérateur % suffisent : quand l'indice dépasse la fin, le modulo le ramène au début. C'est exactement ce que fait un cercle.

   personnes = list(range(1, n + 1))   # les numéros 1, 2, …, n
   i = 0                               # position du dernier éliminé

Le décalage de k en k

À chaque tour, on avance de k places à partir de la position courante. Comme la personne éliminée disparaît de la liste, l'indice i pointe déjà sur la suivante après le del : il faut donc avancer de k − 1 places, pas de k.

   i = (i + k - 1) % len(personnes)
   del personnes[i]

Cette unique ligne contient tout le problème. On la répète tant qu'il reste plus de survivants que voulu.

La complexité

del L[i] recopie la fin de la liste : chaque suppression coûte au pire n opérations, donc la simulation complète est en O(n²). Pour n = 41 ou n = 100, c'est instantané ; pour n = 10⁶, il faudrait une autre structure de données. C'est aussi ce qui motive la recherche d'une formule exacte dans les parties suivantes.