É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 $\left(\genfrac{}{}{0ex}{}{n}{2}\right)=\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 ? ».