Aller au contenu

Tableau avec des éléments tous différents⚓︎

Un tableau peut contenir plusieurs fois le même élément. C'est le cas du tableau tableau_1 ci-dessous :

🐍 Script Python
tableau_1 = [1, 2, 3, 6, 2, 4, 5]
La valeur 2 est deux fois dans ce tableau.

Au contraire, dans le tableau tableau_2, toutes les valeurs sont uniques :

🐍 Script Python
tableau_2 = ['chien', 'chat', 'lion', 'poisson']

Écrire une fonction tous_differents qui prend un tableau tableau et renvoie un booléen indiquant si toutes les valeurs de tableau sont différentes ou non.

Taille des tableaux

Pour limiter le temps de calcul, on se limitera à des tests avec des tableaux de moins de 100 éléments.

Utilisation de range(a, b)

On pourra éventuellement utiliser range(a, b) qui itère sur toutes les valeurs entières allant de a inclus à b exclu.

Exemples

🐍 Console Python
>>> tableau_1 = [1, 2, 3, 6, 2, 4, 5]
>>> tous_differents(tableau_1)
False
🐍 Console Python
>>> tableau_2 = ['chien', 'chat', 'lion', 'poisson']
>>> tous_differents(tableau_2)
True
###
# testsbksl-nlbksl-nltableau1 = [1, 2, 3, 6, 2, 4, 5]bksl-nlassert touspy-unddifferents(tableau1) == Falsebksl-nlbksl-nltableau2 = ['chien', 'chat', 'lion', 'poisson']bksl-nlassert touspy-unddifferents(tableau2) == Truebksl-nlbksl-nl# autres testsbksl-nlassert touspy-unddifferents([]) == Truebksl-nlassert touspy-unddifferents([1, 1]) == Falsebksl-nlassert touspy-unddifferents([9, 6, 7, 3, 2, 1, 1]) == Falsebksl-nlassert touspy-unddifferents(range(100)) == Truebksl-nlassert touspy-unddifferents(['v', 'o', 'i', 't', 'u', 'r', 'e']) == Truebksl-nlassert touspy-unddifferents(['a', 'a', 'b', 'c', 'd', 'e']) == Falsebksl-nlassert touspy-unddifferents([1, 2, 3, 4, 1]) == Falsebksl-nlassert touspy-unddifferents([5, 9, 1, 2, 1, 3, 7]) == Falsebksl-nlassert touspy-unddifferents([1, 2, 3, 4, 3, 2, 1]) == Falsebksl-nlassert touspy-unddifferents(['a', 'a', 1, 1, "truc", "truc"]) == Falsebksl-nlassert touspy-unddifferents(["bob"]) == Truebksl-nlbksl-nl 5/5

def touspy-unddifferents(tableau):bksl-nl ...bksl-nlbksl-nlbksl-nl# testsbksl-nlbksl-nltableau1 = [1, 2, 3, 6, 2, 4, 5]bksl-nlassert touspy-unddifferents(tableau1) == Falsebksl-nlbksl-nltableau2 = ['chien', 'chat', 'lion', 'poisson']bksl-nlassert touspy-unddifferents(tableau2) == Truebksl-nlbksl-nlbksl-nldef touspy-unddifferents(tableau):bksl-nl n = len(tableau)bksl-nl for i in range(n - 1):bksl-nl for j in range(i + 1, n):bksl-nl if tableau[i] == tableau[j]:bksl-nl return Falsebksl-nl return Truebksl-nlbksl-nlbksl-nl# testsbksl-nlbksl-nltableau1 = [1, 2, 3, 6, 2, 4, 5]bksl-nlassert touspy-unddifferents(tableau1) == Falsebksl-nlbksl-nltableau2 = ['chien', 'chat', 'lion', 'poisson']bksl-nlassert touspy-unddifferents(tableau2) == Truebksl-nlbksl-nlbksl-nl

A

Même si on essaie d'être malin en ne parcourant que les éléments suivants pour voir si un élément apparait plusieurs fois, cette fonction a un cout quadratique. En gros, avec un tableau de taille \(n\) on va faire environ \(n^2\) comparaisons.

L'optimisation de ne regarder que les éléments suivants permet de diviser par 2 le nombre de tests, mais cela reste beaucoup.

Avec un dictionnaire⚓︎

Avec un dictionnaire, la recherche d'un élément est en cout constant, ainsi l'exercice a un cout linéaire en sa taille.

🐍 Script Python
def tous_differents(tableau):
    vus = dict()
    for element in tableau:
        if element in vus:
            return False
        else:
            vus[element] = True
    return True

Z