Python 3 débutant: Fusionner 2 tableaux déjà triés

**Demky** · 30/04/2018, 18h05

Bonjour;

Cela fait plus++ d'une heure que j'essaye de réfléchir sur ça en vain; j'ai 2 tableaux déjà fusionné et je dois les réunir dans un troisième tableau avec en contrainte le fait que :
"On présume que les deux tableaux de départ sont préalablement triés : il est donc irrationnel de faire une simple concaténation des deux tableaux de départ, puis d'opérer un tri"

J'ai tout essayé avec des -1 / +1 et je tombe tout le temps sur le out of range, j'ai compris que c'est du au fait qu'a un moment l'une de mes liste est terminé et que donc la comparaison ne peut plus avoir lieu mais je n'ai aucune idée de comment dire a python que dans ce cas il faut arrêter et ajouter toutes les valeurs de la liste restante.

j'ai essayer de rajouter une deuxième boucle while mais en vain.

Voici le code que j'ai écrit :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
tab1 = [1, 2, 3, 6, 7]
tab2 = [4, 5, 8, 11]
tab3 = []
 
tailleTab3 = len(tab1) + len(tab2)
i, j = 0, 0
 
while len(tab3) < tailleTab3 :
    if tab1[i] < tab2[j] :
        tab3.append(tab1[i])
        i += 1
    else:
        tab3.append(tab2[j])
        j += 1
 
print(tab3)

Depuis 5 semaines que je suis en formation j'ai souvent l'impression que je reste bloqué devant des exercices pendant des heures sans pouvoir avancer; comment vous faites pour vous sortir d'une impasse ?
Je commence a me demander si ce n'est pas moi qui suis juste pas fait pour ce travail; a chaque fois qu'on m'explique une solution je la comprend aisément mais pour créer quelque chose à partir de rien je bloque pendant des heures.

merci pour l'aide.

**fred1599** · 30/04/2018, 18h38

On pourrait utiliser la méthode insert des listes.

il suffirait d'itérer sur ta liste fusionnée, et de vérifier si l'élément est supérieur ou inférieur selon l'ordre (croissant ou décroissant) à un des éléments de la 3ème liste.

EDIT: Oups, j'avais pas compris l'énoncé,

**wiztricks** · 30/04/2018, 18h51

Salut,

Envoyé par Demky

comment vous faites pour vous sortir d'une impasse ?

Personnellement, quand c'est comme çà, j'oublie le code et je repars avec papier crayon pour essayer d'imaginer un algorithme qui me semble répondre au problème.
Après, j'essaie de le coder et je teste.

Envoyé par Demky

Je commence a me demander si ce n'est pas moi qui suis juste pas fait pour ce travail; a chaque fois qu'on m'explique une solution je la comprend aisément mais pour créer quelque chose à partir de rien je bloque pendant des heures.

Il faut apprendre à chercher sans se précipiter sur le clavier.
Intuitivement, si on part de:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
tab1 = [1, 3, 7]
tab2 = [4, 5 ]
tab3 = []

on voit bien qu'il va falloir parcourir tab1 et tab2 indépendamment donc un faudra deux index i et j.
Donc sur la feuille de papier vous écrivez: i = j = 0
Et il va falloir comparer tab1[0]=1 avec tab2[0]=4.
tab1[0] étant plus petit que tab2[0], on va ajouter tab1[0] à tab3 et incrémenter i.
2ème itération:
On se retrouve à comparer tab1[1]=3 avec tab2[0]=4
Même punition: on ajouter tab1[1] à tab3 et on incrémente i.
3ème itération:
On se retrouve à comparer tab1[2]=7 avec tab2[0]=4
Cette fois c'est tab2[0] qui est plus grand donc on l'ajoute à tab3 et on incrémente j.
4ème itération:
On se retrouve à comparer tab1[2]=7 avec tab2[1]=5
C'est encore tab2[2] qui est plus grand donc on l'ajoute à tab3 et on incrémente j.

Si on continue bourrin, on va s'amuser à comparer un tab1[3] qui n'existe pas, alors qu'en fait, puisque toute la liste tab2 a été consommée, il suffit d'ajouter les éléments restants de tab1 à tab3 et on a fini.

Après on essaie de coder çà. On a bien un while mais la condition de sortie de la boucle sera i < len(tab1) and j < len(tab2). Puis après la boucle on traite les éléments restants.

- W

**Demky** · 01/05/2018, 10h55

Merci; j'ai modifier le code grâce a vos instructions et en écrivant ceci :

Tout semble fonctionner! J'imagine qu'on doit pouvoir améliorer le code car beaucoup de lignes sont écrites en double.

**wiztricks** · 01/05/2018, 12h01

Salut,

Pourquoi écrire ce "while" en sortie:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
while len(tab3) < tailleTab3 :
    if i == len(tab1):
        tab3.append(tab2[j])
        j += 1
    elif j == len(tab2):
        tab3.append(tab1[i])
        i += 1

vous savez que vous êtes sorti du while précedent parce que i == len(tab1) ou que j == len(tab2) et donc qu'il faut ajouter les éléments restants:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
if i == len(tab1):
    for x in range(j, len(tab2)):
        tab3.append(tab2[x])
elif j == len(tab2):
    for x in range(i, len(tab1)):
        tab3.append(tab1[x])

Si vous savez découper vos listes, çà peut se faire plus simplement:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
if i == len(tab1):
    tab3 += tab2[j:]
elif j == len(tab2):
    tab3 += tab1[i:]

L'idée étant que plutôt que d'avoir un block d'itérations while len(tab3) < tailleTab3 plein d'instructions qui ne servent à rien, on pousse les itérations le plus bas possible.
Pour te former, les cours et tutoriels Python : https://python.developpez.com/cours/

- W

**nicolas581** · 01/05/2018, 22h28

Bonsoir,

Le but de l'exercice est sans doute d'itérer sur les tableaux mais il y a tout ce qu'il faut dans la bibliothèque standard :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import bisect
import heapq
 
tab1 = [1, 2, 3, 6, 7]
tab2 = [4, 5, 8, 11, 12]
tab3 = tab1[:]
 
#solution1
for elem in tab2:
    bisect.insort(tab3, elem)
 
#solution2
tab4 = list(heapq.merge(tab1, tab2))
 
print(tab3)
print(tab4)

Les deux solutions respectent l'énoncé.
La solution1 serait à utiliser pour insérer des éléments d'une structure non triée dans une structure triée, la solution 2 ayant comme pré-requis que les deux structures soient triées.

**oudjira** · 03/05/2018, 15h23

dans le cas de deux tableaux triés pour fusionner tu peut faire une fonction récursif comme ceci :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
 
def fusion(tab1, tab2):
	if tab1 ==[] : return tab2
	if tab2 ==[] : return tab1
	if tab1[0]<tab2[0] :
		return [tab1[0]]+fusion(tab1[1 :],tab2)
	else :
		return [tab2[0]]+fusion(tab1,tab2[1 :])
 
tab1 = [1, 2, 3, 6, 7]
tab2 = [4, 5, 8, 11, 12]
print("Resultat: fusion(tab1, tab2))
Resultat : [1, 2, 3, 4, 5, 6, 7, 8, 11, 12]

et je crois que à partir de là tu peu faire le reste

**bistouille** · 03/05/2018, 21h31

Envoyé par nicolas581

Bonsoir,

Le but de l'exercice est sans doute d'itérer sur les tableaux mais il y a tout ce qu'il faut dans la bibliothèque standard :
....

Les deux solutions respectent l'énoncé.
La solution1 serait à utiliser pour insérer des éléments d'une structure non triée dans une structure triée, la solution 2 ayant comme pré-requis que les deux structures soient triées.

Et surtout inutile d'importer quoi que ce soit, puisqu'on peut nativement combiner 2 listes

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

tab3 = sorted(tab1 + tab2)

Mais j'imagine que le but de Demky était d'écrire un algorithme faisant cela non pas pour réinventer la roue, mais pour s'exercer.

**Demky** · 03/05/2018, 22h13

merci pour tout les avis;

oui le but est surtout d'essayer d'apprendre Python et surtout l’algorithmie ; j'ai l'impression que le plus compliqué c'est de réussir a penser de la bonne façon

**BufferBob** · 04/05/2018, 08h36

salut,

encore une façon de faire, sans import, sans récursion, mais les données de départ ne sont pas conservées (au pire on les copie au préalable donc) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
while True:
   if not tab1:
      tab3 += tab2
      break # si tab1 est vide, on rajoute le reste de tab2 et on sort de la boucle
   if not tab2:
      tab3 += tab1
      break # et réciproquement
   if tab1[0] < tab2[0]:
      tab3.append(tab1.pop(0))   # pop() récupère l'élément 0 et l'enlève de la liste dans la foulée
   else:
      tab3.append(tab2.pop(0))

**disedorgue** · 04/05/2018, 12h05

Bonjour,

Envoyé par Demky

merci pour tout les avis;

oui le but est surtout d'essayer d'apprendre Python et surtout l’algorithmie ; j'ai l'impression que le plus compliqué c'est de réussir a penser de la bonne façon

Alors, on te dira que cela s'acquiert avec de la pratique et du temps, ce qui est vrai et un peu faux: aucun livre, cours, etc... ne pourra t'apprendre réellement l'algorithmie, tout au plus, on te donnera des méthodes pour effectuer telle ou telle opération mais ça n'ira guerre plus loin. C'est à toi, par la pratique, d'apprendre à décomposer les problèmes en sous problèmes élémentaires et à force, tu auras ce que l'on appelle le déclic.

Et c'est à partir de ce moment là, qu'il devient intéressant d'acquérir la connaissance des différents types d'algorithmes existant pour un problème donné.

Bon courage, mais ça en vaut la peine

**Demky** · 07/05/2018, 22h51

Envoyé par disedorgue

tu auras ce que l'on appelle le déclic.

je comprend pas trop ce principe; tous le monde nous a parlé de ça: le formateur; les anciens stagiaires...

On a forcément le déclic un jour ? genre du jour au lendemain on se met a tout comprendre ?
Je n'ai jamais eu ce genre de problème dans aucun métiers mais en même temps, je n'avais jamais eu de job intellectuel avant

il y a des articles connu qui parle du "déclic" ? ce n'est pas que c'est long mais j'aimerai bien l'avoir avant de passer le diplôme car pour l'instant j'ai un peu peur de l'évolution des choses

edit : j'étais content, j'ai commencé a lire un article sur le déclic, puis à la troisième ligne il y a eu ceci en gras :

Une première définition du déclic pourrait être : la prise de conscience que l'on a intérêt à arrêter sa consommation d'alcool.

**disedorgue** · 08/05/2018, 10h23

En relisant la discussion, ton algorithme était bon, il y avait juste la sortie de boucle qui était fausse mais là c'est lié à une contrainte algorithmique du langage que tu utilises qui ici est python (là, je vais me faire flinguer par certain en disant ça

).
Ce que je veux dire c'est que tu as résolu la partie algorithme, tes erreurs semblent plus lié à ta méconnaissance et/ou du manque de pratique du langage.

D'ailleurs, si tu veux un bon entrainement, tu peux essayer de refaire l'exercice mais au lieu du while, essayes d'utiliser le for.

**cervo** · 08/05/2018, 11h55

Desole si c'est en retard mais tu peux gerer ca tout simplement avec des methodes de l'objet list

1- extend & copy:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
tab3 = tab1.copy() # On fait un copie du tableau 1
tab3.extend(tab2) # on etend le tableau 3 a l'aide du tableau 2
tab3.sort()

ensuite tu fais

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

tab3 = list(set(tab3)) # Pour eliminer les doublons (en cas de doublons)

**wiztricks** · 08/05/2018, 12h03

Salut,

Envoyé par cervo

Desole si c'est en retard mais tu peux gerer ca tout simplement avec des methodes de l'objet list

Et si vous preniez le temps de lire l'énoncé du problème avant de répondre?

Envoyé par Demky

On a forcément le déclic un jour ? genre du jour au lendemain on se met a tout comprendre ?

Le déclic, c'est quand des paquets de neurones se connectent entre eux pour matérialiser un concept. Çà peut se faire rapidement ou pas: chacun doit avoir une "stratégie d'apprentissage" adaptée. Et puisque, c'est une affaire de neurones, c'est pas en tapant sur son clavier qu'on aura le déclic mais plutôt dans son sommeil ou des phases où on se détend, i.e. on arrête d'y penser.

Envoyé par Demky

Je n'ai jamais eu ce genre de problème dans aucun métiers mais en même temps, je n'avais jamais eu de job intellectuel avant

Dans les métiers manuels, il faut aussi connecter des neurones pour apprendre des gestes, prendre des repères,... Et si on se lance dans une activité "compliquée", il va aussi falloir apprendre à la décomposer en une séquences d'opérations et s'assurer avant de se lancer de la maîtrise des différentes techniques à utiliser.

- W