Écrire couples(t), qui renvoie le tableau de tous les couples avec


def couples(t):
    """Tous les couples (t[i], t[j]) avec i < j, dans l'ordre des indices.

    Postcondition : le resultat a n(n-1)/2 elements, ou n = len(t).
    """
    n = len(t)
    r = [(t[i], t[j]) for i in range(n) for j in range(i + 1, n)]
    assert len(r) == n * (n - 1) // 2
    return r

La compréhension à deux for se lit de gauche à droite comme deux boucles imbriquées : le premier est la boucle extérieure. Le range(i + 1, n) du second dépend du $i$ du premier — c'est ce qui impose $i < j$ sans le moindre if.

Le décompte. Choisir deux indices distincts parmi $n$ , sans tenir compte de l'ordre : il y en a $(2 n) = \frac{n ( n - 1 )}{2}$ . Autrement dit : $n$ choix pour $i$ , puis $n - 1$ pour $j$ , et l'on divise par $2$ car $(i, j)$ et $(j, i)$ désignent la même paire.

Vérification.


assert couples([1, 2, 3]) == [(1, 2), (1, 3), (2, 3)]
assert couples([]) == []
assert couples([5]) == []
for n in range(0, 40):
    assert len(couples(list(range(n)))) == n * (n - 1) // 2

Les cas limites sont instructifs : un tableau vide comme un tableau à un seul élément ne fournissent aucune paire, et la formule le dit — $0 \times (- 1) /2 = 0$ et $1 \times 0/2 = 0$ .

Le coût, et la place. Les deux boucles imbriquées font $\frac{n ( n - 1 )}{2}$ tours : le coût croît comme le carré de $n$ . Pour $n = 1000$ , c'est déjà $499500$ couples ; pour $n = 100000$ , ce serait cinq milliards — le programme ne finirait pas, et surtout la mémoire ne suffirait pas. Ici le résultat lui-même est quadratique, et c'est bien plus grave qu'un calcul quadratique : on ne peut pas ranger cinq milliards de couples, quel que soit le temps qu'on y consacre. Quand une fonction construit tous les couples, la question n'est pas « combien de temps ? » mais « où va-t-on les mettre ? ».

Énoncé

Corrigé