Concaténation de listes en python

Résolu/Fermé
yamawi Messages postés 13 Date d'inscription lundi 28 février 2022 Statut Membre Dernière intervention 8 février 2024 - Modifié le 12 déc. 2022 à 16:19
mamiemando Messages postés 32945 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 20 février 2024 - 12 déc. 2022 à 17:54

Bonjour,

Je cherche à concaténer des listes tout en pouvant les modifier.

Exemple :

a = ['chat']
b = ['chien']
a += b
b.append('poisson')

print(a)

# ici, ça affiche ['chat', 'chien']
# moi j'aimerais que ça affiche ['chat', 'chien', 'poisson']

Je sais que l'on pourrait le faire si au lieux de faire a += b on fessait a += [b] mais je ne trouve pas ça très satisfaisant.

Pouvez vous m'aider s'il vous plait
Linux / Firefox 107.0

5 réponses

jee pee Messages postés 39285 Date d'inscription mercredi 2 mai 2007 Statut Modérateur Dernière intervention 20 février 2024 9 182
11 déc. 2022 à 16:57

Bonjour,

Je ne vois pas bien ce que tu cherches dans le fond. "je ne trouve pas ça très satisfaisant." ???

a = ['chat']
b = ['chien']
b += a
a = b
b.append('poisson')

print(a)

On peut utiliser une particularité des listes quand on fait a = b,  a et b en fait ne forment plus qu'une seule liste (elles pointent en mémoire au même endroit). Modifier l'une ou l'autre c'est pareil.

C'est pourquoi quand on veut 2 listes indépendantes, on utilise la méthode copy()

a = b.copy()

0
yamawi Messages postés 13 Date d'inscription lundi 28 février 2022 Statut Membre Dernière intervention 8 février 2024
Modifié le 12 déc. 2022 à 15:54

Il est vrai que dans ma question j'ai mal exprimé mon problème, je suis désolé.

Dans mon exercice, un groupe d'amis veut aller au cinéma. Mais ce jour-là, à cause d'une grève, tout les cinémas sont fermés. De plus, chaque cinéma a une affiche indiquant l'emplacement d'un autre cinéma où le groupe d'amis peut se rendre.

Le programme est censé recevoir une liste de taille n où l'emplacement d'un cinéma est son index dans la liste et le cinéma vers le quel il redirige est donné par sa valeur. Par exemple, avec la liste [2, 3, 1] :

  • le premier cinéma redirige vers le deuxième,
  • le deuxième redirige vers le troisième,
  • et le troisième redirige vers le premier.

Le programme est censé renvoyer pour chaque cinéma tout les cinémas qui ont été visités avant de retourner sur un cinéma qui a déjà été visité.

Avec un programme avec deux boucles emboitées, ce serait simple mais trop complexe algorithmiquement.

Pour que la liste ne soit parcourue qu'une seule fois, j'ai donc créé un dictionnaire.

Admettons que l'on commence avec le premier cinéma  : 

dico = {}
redirection = [# redirection des cinéma ici]
s = 1 #le premier cinéma
dico[s] = [s]
dico[redirection(s)] = [redirection(s)]
dico[s] += dico[redirection(s)]

dico[redirection(redirection(s))] = [redirection(redirection(s))]
dico[redirection(s)] += dico[redirection(redirection(s))]

... # jusqu'à que l'on arrive sur un cinéma où l'on est déjà passé


# de cette façon j'aimerais que dico[s] renvoie tout les cinémas qui ont été parcouru.
0
yg_be Messages postés 22470 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 20 février 2024 1 440
11 déc. 2022 à 19:43

bonjour,

Pourquoi ne fais-tu pas, pour commencer, un programme "simple mais trop complexe" qui te donne le résultat que tu attends?

Tiens, peux-tu nous montrer le résultat attendu avec la liste de départ que tu donnes en exemple?  Cela permettrait peut-être de comprendre "pour chaque cinéma tout les cinémas qui ont été visité avant de retourné sur un cinéma qui a déjà été visité".

N'hésite pas à faire un exemple plus complexe.

0
yg_be Messages postés 22470 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 20 février 2024 1 440
11 déc. 2022 à 20:24

Tu supposes qu'en partant du premier cinéma, tu vas tous les parcourir.  Est-ce toujours correct?

0
jee pee Messages postés 39285 Date d'inscription mercredi 2 mai 2007 Statut Modérateur Dernière intervention 20 février 2024 9 182
11 déc. 2022 à 18:29

"tout les cinémas sont fermés," donc l'exercice est résolu, je reste chez moi devant la TV ;-)

tu devrais reposer une nouvelle question avec le bon sujet dès le départ, et terminer celle ci. La question d'origine est trompeuse. D'ailleurs, liste et dictionnaire fonctionnent différemment.


0
yg_be Messages postés 22470 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 20 février 2024 1 440
11 déc. 2022 à 21:00

En fait, pourquoi ne trouves pas cela satisfaisant d'utiliser a += [b] ?

0

Vous n’avez pas trouvé la réponse que vous recherchez ?

Posez votre question
mamiemando Messages postés 32945 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 20 février 2024 7 720
Modifié le 12 déc. 2022 à 16:24

Bonjour,

Dans ta question initiale #0, il y a une confusion entre référence et copie d'objet en mémoire. En écrivant a += b, tu recopies le contenue de b dans a, et donc les modifications futures de b n'ont pas d'impact sur le contenu de a. À moins d'avoir une structure qui maintient un ensemble de listes et qui itère sur chacune d'elle (e.g. avec itertools.chain) tu ne peux pas y faire grand chose.

Dans ton exercice complètement formulé #2, on voit de toute façon que ça n'est pas vraiment la bonne approche. Dans ton exercice, tu peux voir chaque cinéma comme le sommet d'un graphe orienté et chaque redirection comme un arc qui connecte le sommet vers le cinéma de secours. Par exemple, ton exemple #2 le graphe serait constitué de trois sommets (1, 2 et 3) formant un cycle orienté 1 -> 2 -> 3 -> 1. Les algorithme de traversée dans un graphe orienté sont prévus pour fonctionner pour n'importe quelle structure de graphe.

Dès que le graphe peut comporter des boucles ou des cycles (ce qui est ton cas), il faut mémoriser au cours du parcours les sommets déjà traversés et ne pas les réexplorer, sans quoi le programme peut boucler indéfiniment.

Les algorithmes usuels, tels que le BFS ou le DFS, associent pour cela en général à chaque sommet une couleur qui indique son statut (blanc - pas exploré ; gris - en cours d'exploration ; noir complètement exploré). Le vecteur de couleur permet d'une part les boucles infinies au cours de la traversée de graphe, mais également de voir les sommets atteints lors du parcours. En terme de complexité, pour un graphe G(V, E), un tel algorithme s'exécute en O(|V|+|E|) (on visite au plus une fois chaque sommet et chaque arc) et a une empreinte mémoire en O(|V|) (à cause du vecteur de couleur).

Dans ton cas, on peut simplifier l'algorithme car on sait que la liste est finie, supposée valide (tout identifiant inclus dedans correspond à un cinéma) et donc forme nécessairement un cycle quelque soit le cinéma de départ. De plus, au lieu d'utiliser une vecteur de couleur, on peut directement mémoriser l'ensemble des sommets visités et interrompre l'exploration dès que l'on revisite un sommet déjà découvert.

Programme :

def list_visited(redirections, current) -> set:
    visited = set()
    while current not in visited:
        visited.add(current)
        current = redirections[current]
    return visited

n = 6
redirections = [1, 2, 0, 3, 5, 4]
assert set(redirections) == {i for i in range(n)}
for start in range(n):
    visited = list_visited(redirections, start)
    print(f"start = {start} visited = {visited}")

Résultat :

start = 0 visited = {0, 1, 2}
start = 1 visited = {0, 1, 2}
start = 2 visited = {0, 1, 2}
start = 3 visited = {3}
start = 4 visited = {4, 5}
start = 5 visited = {4, 5}

Bonne chance

0
yg_be Messages postés 22470 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 20 février 2024 1 440
12 déc. 2022 à 16:30

C'est un exemple de programme "simple" avec deux boucles emboitées, tandis que le demandeur est à la recherche, sans doute illusoire, d'une solution moins "complexe".

0
mamiemando Messages postés 32945 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 20 février 2024 7 720 > yg_be Messages postés 22470 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 20 février 2024
12 déc. 2022 à 17:54

Effectivement, on peut faire une petite optimisation. Le script #6 peut être accéléré en vérifiant que start n'a jamais été visité. Le programme continue à reposer sur deux boucles (une pour changer de sommet de départ, une pour dérouler ses redirections), mais chaque redirection n'est désormais évaluée qu'une seule fois.

Si on admet que vérifier si start a déjà été traité se fait en O(1) (ce qui est le cas si on utilise un set, appelons processed), alors comme chaque sommet et chaque arc n'est visité qu'une et une seule fois, l'algorithme énumère tous les cycles en O(|V|+|E|). C'est d'ailleurs exactement ce qui se passe avec une bonne implémentation du BFS si le but est d'explorer le graphe complet : voir par exemple la fonction breadth_first_search dans cette implémentation qui joue sur le vecteur de couleur pour ne visiter chaque sommet et chaque arc qu'une et une seule fois).

Si on adapte l'idée au code que j'ai proposé dans #6 on obtient ceci :

def list_visited(redirections, current) -> set:
    visited = set()
    while current not in visited:
        visited.add(current)
        current = redirections[current]
    return visited

n = 6
cinemas = ["cinema{d}" for i in range(n)]
redirections = [1, 2, 0, 3, 5, 4]
assert set(redirections) == {i for i in range(n)}
cycles = list()
processed = set()
for start in range(n):
    if start not in processed:
        visited = list_visited(redirections, start)
        processed |= visited
        cycles.append(visited)
print(cycles)

Résultat :

[{0, 1, 2}, {3}, {4, 5}]

Mais bon, je ne sais pas si ça répond à la question sur la complexité. En tout cas, je ne pense pas qu'on puisse faire mieux.

0