Bonsoir

Je n'arrive pas à résoudre cet exercice après plusieurs tentatives ... :

Donner la spécification et une définition en Python de la fonction intersection_2_listes qui, étant données deux listes d'entiers L1 et L2 triées en ordre croissant, renvoie la liste des éléments appartenant à la fois à L1 et à L2. On exploitera bien sûr le fait que L1 et L2 sont toutes deux triées. Par exemple :

intersection_2_listes([0, 1, 2], [3, 4, 5])==[]

intersection_2_listes([1, 2, 3], [1, 2, 3])==[1, 2, 3]

intersection_2_listes([1, 1], [1, 1])==[1, 1]

intersection_2_listes([1, 1], [1, 2])==[1]

intersection_2_liste([], [1, 2, 3]) ==[]

intersection_2_listes([1, 2, 2, 3, 4], [2, 3, 4, 4, 5, 6])==[2, 3, 4]

Voici ce que j'ai fais (c'est faux, ça ne fonctionne pas) :

def intersection_2_listes(L1, L2) :

    """List[Int] * List[Int] -> List[Int]

    Retourne l'intersection des deux listes L1 et L2."""

    # Result : List[Int]

    Result = []

    # i1 : Int

    for i1 in L1 :

        # i2 : Int

        for i2 in L2 :

            if i1==i2 :

                Result.append(i1)

    return Result

Non seulement je n'utilise pas comme précisé dans l'énoncé le fait que L1 et L2 sont triées et en plus ça ne me renvoie pas les bons résultats dès qu'un élément apparait plusieurs fois dans les deux listes ...

Je ne sais pas comment résoudre mes erreurs

Salut

A priori c'est bon maintenant :

def intersection_2_listes(L1, L2):
    """List[Int] * List[Int] -> List[Int]
    Retourne l'intersection des deux listes L1 et L2."""

    result = []

    for n in L1:
        for x in L2:
            if n == x and n not in result:
                result.append(n)
    result.sort()

    return result


print intersection_2_listes([1, 2, 3, 4], [1, 2, 2, 5, 6])

-
Edité par InhumanRampage 12 janvier 2015 à 7:28:27

Je ne pense pas que tu y arriveras avec des boucles for.

Pour moi, tu commences avec deux indices pour chaque liste initialisés à 0. Tu compares le premier élément de la première liste et de la seconde liste.

• Si le premier élément est plus petit que le second, tu passes à l'élément suivant de la première liste
• Si le premier élément est plus grand que le second, tu passes à l'élément suivant de la deuxième liste
• S'ils sont égaux, tu places le résultat dans ta liste, et tu passes à l'élément suivant dans les deux listes.

Tu fais ça tant que tu n'as pas atteint la fin pour une liste ou l'autre.

Il n'y a plus qu'à le coder.

@InhumanRampage: ta solution ne fonctionne pas dans le cas intersection_2_listes([1, 1], [1, 1])==[1, 1]

-
Edité par Dan737 12 janvier 2015 à 10:47:04

Merci beaucoup !!!!!

Si le nombre d'éléments dans l'intersection et si l'ordre des éléments n'importe pas ou s'il est déterminé par un algorithme (=prévisible), tu peux utiliser les set:

list1 = [2, 3, 4, 5] # Les listes sont ordonnées selon un 
list2 = [1, 2, 3]      # algorithme (de tri), ici par ordre croissant
inter = sorted(list(set(list1) & set(list2)))
inter == [2, 3]

list1 = [2, 3, 4, 5]
list2 = [1, 2, 3]    # Ici l'ordre import peu
inter = [elt for elt in list1 if elt in list2] # On prend tous les éléments de list1 qui sont dans list2
inter = [2, 3]

from functools import reduce
inter = lambda l1, l2: [elt for elt in l1 if elt in l2]
intersect = lambda *lists: reduce(inter, lists)

Et ouala !

@InhumanRampage: Ca ne doit pas renvoyer [1], mais [1, 1].

LaureneBrossette a écrit:

Par exemple : >intersection_2_listes([0, 1, 2], [3, 4, 5])==[] >intersection_2_listes([1, 2, 3], [1, 2, 3])==[1, 2, 3] >intersection_2_listes([1, 1], [1, 1])==[1, 1] >intersection_2_listes([1, 1], [1, 2])==[1] >intersection_2_liste([], [1, 2, 3]) ==[] >intersection_2_listes([1, 2, 2, 3, 4], [2, 3, 4, 4, 5, 6])==[2, 3, 4]

C'est le 3ème exemple montré.

@Alphazeta

• Ta première proposition ne marche pas pour l'exemple 3 intersection_2_listes([1, 1], [1, 1])==[1, 1]
• Ta deuxième proposition ne marche pas dans l'exemple 4 intersection_2_listes([1, 1], [1, 2])==[1]
• Et bien entendu la troisième proposition se comporte comme la deuxième donc même problème.

L'énoncé peut prêter à confusion vu qu'il parle d'éléments communs aux deux listes. Ca fait de suite penser à des set. Mais en voyant les exemples, on se rend compte que c'est plus subtil que ça.