Problème : exercice de récursivité.

Version imprimable

28/01/2019, 13h23
SupaFlamme

Problème : exercice de récursivité.

Bonjour, je rencontre un problème concernant un exercice :

Je dois créer une fonction deepconcat(liste) qui parcourt la liste et retourne un string qui est la concaténation de tous les éléments de cette dernière, tout cela en utilisant la récursivité.

Exemple : deepconcat(["a",["b","6"],"e",["5",["g","h"]],"i"]) retourne "ab6de5ghi".

Les éléments de la liste peuvent donc être des sous-listes, ces dernières pouvant elles-même contenir des sous-listes.

Merci de votre aide.
28/01/2019, 13h45
BoorBox

Bonjour.

C'est dommage si tu n'essaie pas par toi même mais essaie de faire une fonction qui retourne
chaque élément du tableau et si un des éléments du tableau en est un alors tu relance la fonction.
28/01/2019, 17h15
Sve@r

Bonjour

Citation:

Envoyé par SupaFlamme

Bonjour, je rencontre un problème concernant un exercice :

Et quel est ce problème ? Parce que là, tu nous as donné l'énoncé de l'exercice mais rien dit sur le problème que tu rencontres...

Salut,

Si vous ne postez pas un peu de code, non seulement on ne connaît pas la difficulté que vous rencontrez (et quoi vous expliquer) mais en plus on ne sait pas trop quel style de Python, vous êtes autorisé à utiliser.

Donc on peut vous proposer une solution "récursive" cuisinée pour le plaisir du genre:
Code:

1 2 3 4 5 6 7 8 9 10 11 def deepconcat(alist): def flatten(alist): for e in alist: if isinstance(e, list): yield from flatten(e) else: assert isinstance(e, str) yield e return ''.join(e for e in flatten(alist))
mais si vous n'avez pas encore étudié les constructions que j'utilise, il y a de fortes chances que vous ne compreniez pas ce code.
Pire comme vous sortez du cadre des concepts que vous avez appris, l'exo étant là pour vous assurer que vous savez les utiliser... A la place de votre professeur, soit êtes pas capable de m'expliquer et je vous mets la moitié de la note soit c'est zéro direct.

- W

Voilà mon code pour le moment :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
def deepconcat(l) :
     new_l = []
     if l == [] :
         return None
     elif len(l) == 1 :
         return l[0]
     else :
         for i in l :
             if type(i) == str :
                 return l[0] + deepconcat(l[1:])
             if type(i) == list :
                 new_l = l[0] + deepconcat(l[1:])
                 return "".join(new_l)

29/01/2019, 11h38
lg_53

Vous semblez ne pas être loin du compte.

Indice pour vous : que se passe t il si vous appelez la fonction deepconcat en lui passant simplement une chaine de caractere ?
29/01/2019, 12h25
wiztricks
Citation:

Envoyé par SupaFlamme

Voilà mon code pour le moment :

Maintenant, il manque "je teste ce code avec la liste XYZ, çà me retourne autre chose qu'attendu" et une relecture plus attentive de votre code:
Code:

1 2 3 for i in l : if type(i) == str : return l[0] + deepconcat(l[1:])
On dirait que çà va balayer toute la liste alors que la fonction se termine en fonction du type du premier élément: il sert à quoi ce "for"?

Reprenez le problème depuis le début: à partir de:
["a",["b","6"],"e",["5",["g","h"]],"i"].
Le premier appel doit produire:
"a" + deepconcat(["b","6"]) + "e" + deepconcat(["5",["g","h"]]) + "i".
qu'on peut ré-écrire:
''.join([ "a", deepconcat(["b","6"]), "e", deepconcat(["5",["g","h"]]), "i"]).
ou encore: ''.join(new_list).
Donc la boucle "for" construit une newlist et le return est après le .join.

- W
29/01/2019, 17h08
fred1599

Si on cherche un peu en anglais, avec flatten list et python, on trouve son bonheur !

Son utilisation est simple,

Code:

print(''.join(flatten(["a",["b","6"],"e",["5",["g","h"]],"i"])))

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
def deepconcat(l) :
    new_l = []
    if l == [] :
        return None
    elif len(l) == 1 :
        return l[0]
    else :
        for i in l :
            if type(i) == str :
                return l[0] + deepconcat(l[1:])
            if type(i) == list :
                new_l = l[0] + deepconcat(l[1:])
                return "".join(new_l)

Voici mon code pour le moment.

Quand je fais deepconcat(["a","b","c"]), la fonction me retourne "abc".
Quand je fais deepconcat([["a"],["b"],["c"]]), la fonction me retourne une erreur :

TypeError: can only concatenate list (not "str") to list

30/01/2019, 20h50
Sve@r
Citation:

Envoyé par SupaFlamme

Voici mon code pour le moment.

Pas de quoi être fier

En vrac
1. si "l" est vide, tu crées "new_l" pour rien
2. si "l" est une liste sans élément, ou une liste de 1 élément, tu la traites différemment (dans les deux cas). Je n'en vois pas la raison. Pour moi, une liste vide ou même une liste de "1" se traite de la même façon qu'une liste de 1000000 => on la balaye élément par élément (et tant pis s'il n'y a pas d'élément)
3. si l'élément "i" traité est une chaine, tu traites l[0] => pourquoi alors itérer sur chaque élément si tu traites toujours le premier
4. quoi qu'il arrive, à la première itération de ta boucle, tu sors sur un return qui est présent dans tous les cas évalués (le reste de ta boucle ne sera jamais traité)
Sinon pour simplifier un peu, t'as pas besoin d'écrire de "else" si le "if" comporte un return. Exemple
Code:

1 2 3 4 if expression: return truc else: autre_traitement
Peut s'écrire plus simplement
Code:

1 2 3 4 if expression: return truc autre_traitement
Ca gagne en indentation donc en lisibilité (ou "en indentation et en lisibilité" si tu n'es pas convaincu qu'il y a relation directe entre "indentation" et "lisibilité").

Or la lisibilité permet ensuite de mieux voir ses erreurs.

Citation:

Envoyé par SupaFlamme

Quand je fais deepconcat([["a"],["b"],["c"]]), la fonction me retourne une erreur : TypeError: can only concatenate list (not "str") to list

Ca signifie que tu tentes de concaténer une chaine à une liste ce qui est interdit (probablement en ligne 11 ou 13 => bien entendu il ne te serait pas venu à l'idée de regarder la ligne incriminée !!!)

Déjà faut être lucide: si ta fonction ne retourne pas dans tous les cas la même chose, tu ne t'en sortiras pas. Or tantôt elle retourne une chaine, tantôt elle retourne une liste, tantôt elle retourne None. Donc :mur:
31/01/2019, 08h58
fred1599
Bonjour,

Pour ajouter au post de mon VDD,

Quelques incohérences,
1. Sachant qu'on cherche à retourner un résultat de type string, autant retourner une chaîne vide si l est vide. (en passant trouve un autre nom de paramètre pour ta fonction)
2. Ligne 6, tu fais un calcul de longueur impliquant un temps d'exécution supplémentaire inutile
3. Ligne 10, n'utilise pas type, mais isinstance.
Bonne journée,
31/01/2019, 16h16
lg_53
Citation:

Envoyé par lg_53

Vous semblez ne pas être loin du compte.

Indice pour vous : que se passe t il si vous appelez la fonction deepconcat en lui passant simplement une chaine de caractere ?

Vous ne suivez pas ce qu'on vous a dit ! Là vous voyez bien que si vous passez un string à votre fonction rien ne se passe comme il le faudrait !

Donc ce qu'il vous faut c'est une structure :
```
def deepconcat(liste_or_str):
     si liste :
           faire une concaténation (join) de deepconcat appelé sur tous les éléments
           ceci retourne un str
     sinon :  (on supposera que c'est alors un str)
           retourner liste_or_str (ici on a rien a faire, on a deja un str en entrée)
```

Citation:

Envoyé par lg_53

Donc ce qu'il vous faut c'est une structure :

def deepconcat(liste_or_str):
     si liste :
           faire une concaténation (join) de deepconcat appelé sur tous les éléments
           ceci retourne un str
     sinon :  (on supposera que c'est alors un str)
           retourner liste_or_str (ici on a rien a faire, on a deja un str en entrée)

Moi je me suis amué à aller plus loin

Code:

1
2
3
4
5
6
7
def deepconcat(param):
     si param possède un attribut "__iter__":
           si param possède un attribut "has_key": (dico) => convertir le param en tuple en ne gardant que ses items
           faire une concaténation (join) de deepconcat appelé sur tous les éléments de param
           ceci retourne un str
     sinon :  (on supposera alors un str ou un float ou un int)
           retourner str(param)

mais c'est juste pour le fun. Maintenant je suis en train d'essayer de comprendre le premier code de wiztricks notemment le yield from truc que je ne connaissais pas ;)

je me suis amusé à faire ça

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def deepconcat(L):
    #prend une liste L dont les éléments sont soit des chaines
    #soit des listes de chaines
    #soit des listes dont les éléments sont des chaines ou des listes de chaines etc
    #renvoie la chaine concaténée de toutes les chaines
    if len(L)==0:
        return("")
    else:
        Ch=""
        for x in L:
            if (type(x)==str):
                Ch+=x
            elif type(x)==list:
                Ch+=deepconcat(x)
        return(Ch)

ça marche

Bonsoir,
Citation:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 def deepconcat(L): #prend une liste L dont les éléments sont soit des chaines #soit des listes de chaines #soit des listes dont les éléments sont des chaines ou des listes de chaines etc #renvoie la chaine concaténée de toutes les chaines if len(L)==0: return("") else: Ch="" for x in L: if (type(x)==str): Ch+=x elif type(x)==list: Ch+=deepconcat(x) return(Ch)
Citation:
Code:

1 2 if len(L)==0: return("")
autant faire plus propre,
Code:

1 2 if not L: return ''
Ligne 8, le else est inutile, car si la liste est vide, tu termines l'exécution du code dans ta fonction.

Ligne 11 et 13, voir mes remarques plus haut, pas type, mais isinstance.

Ligne 12 et 14, respecter la PEP8, mettre des espaces entre opérateur et variables.

Ligne 15, pas de parenthèses

Remarque: On évite les variables de moins de 3 caractères.

Pourquoi pas les docstrings ?