Écrire sans doublons(t) , qui renvoie les éléments de t sans…

def sans_doublons(t):
    """Elements de t sans repetition, dans l'ordre de premiere apparition.

    Postcondition : chaque element de t figure exactement une fois dans le
                    resultat, et le resultat ne contient rien d'autre.
    """
    r = []
    for x in t:
        if x not in r:
            r.append(x)
    return r

Les deux assertions qui caractérisent. Une seule ne suffit jamais :

r = sans_doublons(t)
assert all(x in t for x in r)          # rien d'invente
assert all(x in r for x in t)          # rien d'oublie
assert len(r) == len(sans_doublons(r)) # aucun doublon ne subsiste

La première seule serait vérifiée par la fonction qui rend toujours [] ; la deuxième seule, par la fonction identité. Ensemble, elles disent l'égalité des ensembles ; la troisième ajoute l'absence de répétition.

Vérification.

assert sans_doublons([3, 1, 3, 2, 1]) == [3, 1, 2]
assert sans_doublons([]) == [] and sans_doublons([5, 5, 5]) == [5]

for _ in range(1000):
    t = [random.randint(0, 5) for _ in range(random.randint(0, 12))]
    r = sans_doublons(t)
    assert len(r) == len(set(t))
    assert all(x in t for x in r) and len(r) == len(sans_doublons(r))

Les $1000$ cas passent.

Le coût. La ligne if x not in r n'est pas gratuite : elle parcourt r jusqu'à trouver ou épuiser. Si le tableau contient $n$ valeurs toutes distinctes, le $k$-ième tour compare contre $k-1$ éléments, et le total vaut $0+1+\cdots +(n-1)=\frac{n(n-1)}{2}$ comparaisons : le coût croît comme le carré de $n$.

L'ordre de première apparition est ce qui coûte cher. Si l'on y renonce, set(t) donne le même contenu à coût presque proportionnel à $n$ — grâce au mécanisme d'accès direct du chapitre 5. Une contrainte qui paraît anodine dans l'énoncé peut décider du coût de l'algorithme.