Python, listes
Résolu
hautDébit
-
hautDébit -
hautDébit -
Bonjour,
Je débute dans python et la programmation en général, et je voudrais trier un tableau de tableaux :
exemple: [[1, 4], [4, 8], [6, 3], [6, 1], [7, 8], [1, 6], [8, 7], [1, 4], [3, 7], [3, 6], [8, 4], [4, 1], [7, 3]]
de façon à ce que je n'aie pas un couple qui se répète, et que les couples qui se croisent se suivent
Ici, je devrais avoir :
[[1, 4],[4, 8], [8, 7],[7, 3],[3, 6], [6, 1]]
voilà,
j'ai fais tout ce que je pouvais, mais sans résultat
Si vous pouvez m'aider svp!
Merci par avance
Je débute dans python et la programmation en général, et je voudrais trier un tableau de tableaux :
exemple: [[1, 4], [4, 8], [6, 3], [6, 1], [7, 8], [1, 6], [8, 7], [1, 4], [3, 7], [3, 6], [8, 4], [4, 1], [7, 3]]
de façon à ce que je n'aie pas un couple qui se répète, et que les couples qui se croisent se suivent
Ici, je devrais avoir :
[[1, 4],[4, 8], [8, 7],[7, 3],[3, 6], [6, 1]]
voilà,
j'ai fais tout ce que je pouvais, mais sans résultat
Si vous pouvez m'aider svp!
Merci par avance
A voir également:
- Python, listes
- Citizen code python avis - Accueil - Outils
- Listes déroulantes excel - Guide
- Listes déroulantes en cascade excel - Guide
- Python est introuvable. exúcutez sans argument pour procúder ó l ✓ - Forum Python
- Mot secret python pix ✓ - Forum Python
4 réponses
Bonjour,
Ce n'est pas un tableau de tableaux.
Il n'y a pas de tableaux en Python autres que ceci:
https://docs.python.org/3/library/array.html#module-array
C'est une liste de listes.
Point-barre
Réponse sur le fond du problème dans prochain post
Ce n'est pas un tableau de tableaux.
Il n'y a pas de tableaux en Python autres que ceci:
https://docs.python.org/3/library/array.html#module-array
C'est une liste de listes.
Point-barre
Réponse sur le fond du problème dans prochain post
Sinon, pour éliminer les doubles, on peut faire
li = [[1, 4], [4, 8], [1,4], [6, 3], [6, 1], [7, 8], [1, 6], [8, 7], [1, 4], [3, 7], [3, 6], [8, 4], [4, 1], [7, 3]] print li,'\n' li_wo_dbl = [] li_wo_dbl.extend( el for el in li if el not in li_wo_dbl) print li_wo_dbl
Alors il faut écrire
Je pense comprendre pourquoi: quand un segment entre deux sommets a été parcouru une fois, tu ne veux pas qu'il soit parcouru ultérieurement dans l'autre sens.
Dans le code que je propose en réponse dans quelques instants, je procède autrement: je garde un doublon (1,4) (4,1) parce que je ne sais pas quel des deux sens sera parcouru en premier,
et lorsqu'un sens est parcouru j'élimine la possibilité de reparcourir le même sens et son sens inverse en les signalant comme vus en les mettant dans une liste notthis
li_wo_dbl.extend( el for el in li if el not in li_wo_dbl and list(reversed(el)) not in li_wo_dbl)
Je pense comprendre pourquoi: quand un segment entre deux sommets a été parcouru une fois, tu ne veux pas qu'il soit parcouru ultérieurement dans l'autre sens.
Dans le code que je propose en réponse dans quelques instants, je procède autrement: je garde un doublon (1,4) (4,1) parce que je ne sais pas quel des deux sens sera parcouru en premier,
et lorsqu'un sens est parcouru j'élimine la possibilité de reparcourir le même sens et son sens inverse en les signalant comme vus en les mettant dans une liste notthis
Je propose la solution suivante. Je ne sais pas ce qu'elle vaudrait appliquée à une autre liste, mais au moins pour ta liste elle fournit le résultat voulu. Sauf qu'il est en sens inverse, mais bon ce n'est pas grave je pense.
J'ai la flemme de tester avec d'autres listes. Teste toi-même et signale moi les erreurs d'exécution les ou résultats erronés.
J'ai conçu le code de sorte qu'il prenne en charge des listes dans lesquelles un sommet peut être relié à plus de deux autres sommets. Dans ta liste, chaque sommet n'est potentiellement liable qu'à seulement deux autres sommets. cf le dictionaire d dans mon code
J'espère que tu vas piger l'algorithme, la récursivité, ce n'est pas évident.
J'ai fait stopper la récursivité quand le processus retombe sur la valeur de départ. Mais j'ai eu du mal à obtenir un stop à cet endroit sans égréner la suite des nombres, ce qui raccourcit la liste déjà obtenue. Le stop que j'ai trouvé, avec deux return break, est tordu. J'avoue que je ne comprends pas très bien comment ça marche à cet endroit. Mais bon, l'ensemble marche.
J'ai la flemme de tester avec d'autres listes. Teste toi-même et signale moi les erreurs d'exécution les ou résultats erronés.
J'ai conçu le code de sorte qu'il prenne en charge des listes dans lesquelles un sommet peut être relié à plus de deux autres sommets. Dans ta liste, chaque sommet n'est potentiellement liable qu'à seulement deux autres sommets. cf le dictionaire d dans mon code
J'espère que tu vas piger l'algorithme, la récursivité, ce n'est pas évident.
J'ai fait stopper la récursivité quand le processus retombe sur la valeur de départ. Mais j'ai eu du mal à obtenir un stop à cet endroit sans égréner la suite des nombres, ce qui raccourcit la liste déjà obtenue. Le stop que j'ai trouvé, avec deux return break, est tordu. J'avoue que je ne comprends pas très bien comment ça marche à cet endroit. Mais bon, l'ensemble marche.
the_list = [[1, 4], [4, 8], [1,4], [6, 3], [6, 1], [7, 8], [1, 6], [8, 7],
[1, 4], [3, 7], [3, 6], [8, 4], [4, 1], [7, 3]]
print 'the_list :',the_list
print '\nOn veut obtenir [[1, 4],[4, 8], [8, 7],[7, 3],[3, 6], [6, 1]]\n'\
"c'est à dire 1,4,8,7,3,6,1 "
print "\n================================================="
def cherche_chemin(entry):
entry_wo_dbl = []
entry_wo_dbl.extend( el for el in entry if el not in entry_wo_dbl)
from collections import defaultdict
d = defaultdict(list)
for f,l in entry_wo_dbl:
d[f].append(l)
print 'dictionnaire d :'
for k,v in d.iteritems():
print k,":",v
notthis = []
def cherchech(n,running = True):
print "\nn == %d\nli == %r\nnotthis == %r" % (n,li,notthis)
if running and n==depart:
print ' ici premier return break'
return 'break'
elif n in d:
print (" d[%d] == %r\n"
" d[%d][-1] == %d\n"
" (%d,%d) in notthis est %s"
% (n, d[n], n, d[n][-1], n, d[n][-1], (n,d[n][-1]) in notthis))
if (n,d[n][-1]) in notthis:
print " je n'examine pas %r" % ((n,d[n][-1]),)
del d[n][-1]
if d[n]==[]:
del d[n]
return None
else:
notthis.append((n,d[n][-1]))
notthis.append((d[n][-1],n))
print " je vais examiner %r et notthis est maintenant %r" % ((n,d[n][-1]),notthis)
li.append(d[n][-1])
what = cherchech(d[n][-1])
print " what ==",what
if what is None:
del d[n][-1]
if d[n]==[]:
del d[n]
print " li maintenant :",li
return cherchech(li[-1])
elif what=='break':
print ' ici deuxième return break'
return 'break'
else:
li.append(what)
else:
print " %d is not in d" % n
del li[-1]
if li:
return cherchech(li[-1])
#---------------------------------------
depart = entry_wo_dbl[0][0]
li = [depart]
cherchech(depart,False)
return li
print "\n\nRésultat : %r" % cherche_chemin(the_list)
J'ai encore réfléchi un peu à ton sujet, qui est apparemment la recherche de chemins fermés entre les sommets de polygones.
Les sous-listes à deux éléments de la liste de départ sont manifestement des trajets autorisés entre deux sommets.
Donc, à partir d'un nombre suffisant de trajets autorisés, il est évident qu'il existe plusieurs chemins fermés pour une liste donnée, même si on se limitait à des trajets autorisés tels que chaque sommet ne peut être liable qu'à deux autres sommets.
c'est encore plus vrai si chaque sommet est liable à plus de deux autres sommets.
Par curiosité, j'ai voulu vérifier cette idée.
Comme mon code prend un point de depart fixé par
En fait, le résultat est toujours le même parce que le sommet de départ est fixé ainsi et parce que les listes qui sont les valeurs du dictionnaire d sont toujours avec leurs éléments dans le même sens.
Mais si on changeait le sommet de départ et l'ordre des valeurs de d, on obtiendrait des résultats divers.
Cependant, c'est trop compliqué à faire, alors j'ai pris une autre solution:
- d'une part j'itère sur tous les sommets pour les prendre comme point de départ
- j'itère pour brasser la liste de départ avec random.shuffle
Ca donne le code suivant, dans lequel il suffit de changer la valeur dans
Il suffit aussi de changer les valeurs de affdat et aff pour afficher plus ou moins de choses durant l'exécution.
Note que le code ne marche que si la fonction cherche_chemins() est une fonction génératrice (présence de yield)
Un exemple de résultat
Soit dit en passant, je ne crois pas que quelqu'un pourrait aboutir à un tel code en 24 heures en utilisant Java ou C++.
Python offre des facilités incroyables, et ça dépote....
Les sous-listes à deux éléments de la liste de départ sont manifestement des trajets autorisés entre deux sommets.
Donc, à partir d'un nombre suffisant de trajets autorisés, il est évident qu'il existe plusieurs chemins fermés pour une liste donnée, même si on se limitait à des trajets autorisés tels que chaque sommet ne peut être liable qu'à deux autres sommets.
c'est encore plus vrai si chaque sommet est liable à plus de deux autres sommets.
Par curiosité, j'ai voulu vérifier cette idée.
Comme mon code prend un point de depart fixé par
depart = entry_wo_dbl[0][0]il va donner toujours le même résultat pour une liste donnée.
En fait, le résultat est toujours le même parce que le sommet de départ est fixé ainsi et parce que les listes qui sont les valeurs du dictionnaire d sont toujours avec leurs éléments dans le même sens.
Mais si on changeait le sommet de départ et l'ordre des valeurs de d, on obtiendrait des résultats divers.
Cependant, c'est trop compliqué à faire, alors j'ai pris une autre solution:
- d'une part j'itère sur tous les sommets pour les prendre comme point de départ
- j'itère pour brasser la liste de départ avec random.shuffle
Ca donne le code suivant, dans lequel il suffit de changer la valeur dans
for i in xrange(10)pour obtenir une diversité plus ou moins grande de chemins.
Il suffit aussi de changer les valeurs de affdat et aff pour afficher plus ou moins de choses durant l'exécution.
Note que le code ne marche que si la fonction cherche_chemins() est une fonction génératrice (présence de yield)
import random
the_list = [[1, 4], [4, 8], [1, 4], [6, 3], [6, 1], [7, 8], [1, 6], [8, 7],
[1, 4], [3, 7], [3, 6], [8, 4], [4, 1], [7, 3], [9, 1], [1, 9],
[7,14], [14,7 ], [13,8 ], [8,13, ], [15,2 ], [2,15 ], [3,11 ], [11,3 ],
[17,5 ], [5,17 ], [9,17 ], [17,9 ], [1,20 ], [20,1 ], [21,4 ], [4,21 ],
[15,8 ], [8,15 ], [17,14 ], [14,17 ], [20,7 ], [7,20 ],
[21,17 ], [17,21 ], [13,5], [5,13], [2,20], [20,2], [21,8], [8,21],
[15,17], [17,15], [9,15], [15,9], [9,17], [17,9]]
def cherche_chemins(entry,affdata=False):
if affdata:
print ('liste entrée :\n %r' % entry)
entry_wo_dbl = []
entry_wo_dbl.extend( el for el in entry if el not in entry_wo_dbl)
from collections import defaultdict
d = defaultdict(list)
for f,l in entry_wo_dbl:
d[f].append(l)
if affdata:
print ('\ndictionnaire d :\n%s' % '\n'.join(" %d : %r" % el for el in d.items()))
def cherchech(n,running = True,notthis=[],aff=False):
# notthis est défini une seule fois, lors de la définition de la fonction
# Chaque fois que cherchech() est ensuite appelée, notthis est toujours le même objet,
# mais comme c'est un objet mutable, sa valeur subit des variations.
# Pour disposer d'une liste notthis vide chaque fois qu'une nouvelle recherche est
# lancée (à ce moment là running est à False), il faut vider notthis
if not running:
notthis[:] = []
if aff: print ("\nn == %d\nli == %r\nnotthis == %r" % (n,li,notthis))
if running and n==depart:
if aff: print (' ici premier return break')
return 'break'
elif n in d:
if aff:
print ((" d[%d] == %r\n"
" d[%d][-1] == %d\n"
" (%d,%d) in notthis est %s"
% (n, d[n], n, d[n][-1], n, d[n][-1], (n,d[n][-1]) in notthis)))
if (n,d[n][-1]) in notthis:
if aff: print (" je n'examine pas %r" % ((n,d[n][-1]),))
del d[n][-1]
if d[n]==[]: del d[n]
return None
else:
notthis.append((n,d[n][-1]))
notthis.append((d[n][-1],n))
if aff: print (" je vais examiner %r et notthis est maintenant %r" % ((n,d[n][-1]),notthis))
li.append(d[n][-1])
what = cherchech(d[n][-1])
if aff: print (" what == %s" % what)
if what is None:
if len(d[n]): del d[n][-1]
if d[n]==[]: del d[n]
if aff: print (" li maintenant : %r" % li)
return cherchech(li[-1])
elif what=='break':
if aff: print (' ici deuxième return break')
return 'break'
else:
li.append(what)
else:
if aff: print (" %d is not in d" % n)
del li[-1]
if li:
return cherchech(li[-1])
#---------------------------------------
sommets = sorted(set( sum(entry_wo_dbl,[])))
if affdata:
print ('\nsommets sont : %s\n' % ', '.join(map(str,sommets)))
for depart in sommets:
li = [depart]
cherchech(depart,running=False)
# running= False permet à la fonction récursive de savoir qu'elle vient de démarrer
# les appels récursifs se font ensuite tous avec running=True implicite dans la récursion
yield depart,li
listing = []
for i in xrange(10):
random.shuffle(the_list)
resulti = []
for res in cherche_chemins(the_list):
if len(res[1])>2:
listing.append(res[1])
resulti.append(res)
print ('\n%s' % '\n'.join("départ == %d résultat : %r" % res
for res in resulti)
)
print '\n\n\n'
print '\n'.join(map(repr,listing))
Un exemple de résultat
départ == 1 résultat : [1, 6, 3, 7, 14, 17, 21, 4, 8, 7, 20, 2, 15, 9, 1] départ == 2 résultat : [2] départ == 3 résultat : [] départ == 4 résultat : [] départ == 5 résultat : [] départ == 6 résultat : [] départ == 7 résultat : [] départ == 8 résultat : [] départ == 9 résultat : [] départ == 11 résultat : [] départ == 13 résultat : [] départ == 14 résultat : [] départ == 15 résultat : [] départ == 17 résultat : [] départ == 20 résultat : [] départ == 21 résultat : [] départ == 1 résultat : [1, 6, 3, 7, 8, 4, 21, 8, 13, 5, 17, 14, 7, 20, 2, 15, 9, 1] départ == 2 résultat : [2] départ == 3 résultat : [] départ == 4 résultat : [] départ == 5 résultat : [] départ == 6 résultat : [] départ == 7 résultat : [] départ == 8 résultat : [] départ == 9 résultat : [] départ == 11 résultat : [] départ == 13 résultat : [] départ == 14 résultat : [] départ == 15 résultat : [] départ == 17 résultat : [] départ == 20 résultat : [] départ == 21 résultat : [] départ == 1 résultat : [1, 20, 2, 15, 9, 17, 15, 8, 7, 3, 6, 1] départ == 2 résultat : [2, 15, 17, 5, 13, 8, 4, 1, 9, 17, 14, 7, 20, 2] départ == 3 résultat : [] départ == 4 résultat : [] départ == 5 résultat : [5] départ == 6 résultat : [] départ == 7 résultat : [7] départ == 8 résultat : [] départ == 9 résultat : [9] départ == 11 résultat : [] départ == 13 résultat : [13] départ == 14 résultat : [14] départ == 15 résultat : [] départ == 17 résultat : [] départ == 20 résultat : [] départ == 21 résultat : [] départ == 1 résultat : [1, 9, 15, 2, 20, 7, 3, 6, 1] départ == 2 résultat : [2, 20, 7, 8, 4, 1, 9, 15, 2] départ == 3 résultat : [3, 6, 1, 9, 15, 2, 20, 7] départ == 4 résultat : [] départ == 5 résultat : [] départ == 6 résultat : [6] départ == 7 résultat : [] départ == 8 résultat : [] départ == 9 résultat : [] départ == 11 résultat : [] départ == 13 résultat : [] départ == 14 résultat : [] départ == 15 résultat : [] départ == 17 résultat : [] départ == 20 résultat : [] départ == 21 résultat : [] départ == 1 résultat : [1, 20, 7, 8, 15, 9, 17, 5, 13, 8, 4, 1] départ == 2 résultat : [] départ == 3 résultat : [3, 7, 14, 17, 21, 8, 4, 1, 6, 3] départ == 4 résultat : [4] départ == 5 résultat : [] départ == 6 résultat : [] départ == 7 résultat : [] départ == 8 résultat : [8] départ == 9 résultat : [] départ == 11 résultat : [] départ == 13 résultat : [] départ == 14 résultat : [] départ == 15 résultat : [] départ == 17 résultat : [] départ == 20 résultat : [] départ == 21 résultat : [21] [1, 6, 3, 7, 14, 17, 21, 4, 8, 7, 20, 2, 15, 9, 1] [1, 6, 3, 7, 8, 4, 21, 8, 13, 5, 17, 14, 7, 20, 2, 15, 9, 1] [1, 20, 2, 15, 9, 17, 15, 8, 7, 3, 6, 1] [2, 15, 17, 5, 13, 8, 4, 1, 9, 17, 14, 7, 20, 2] [1, 9, 15, 2, 20, 7, 3, 6, 1] [2, 20, 7, 8, 4, 1, 9, 15, 2] [3, 6, 1, 9, 15, 2, 20, 7] [1, 20, 7, 8, 15, 9, 17, 5, 13, 8, 4, 1] [3, 7, 14, 17, 21, 8, 4, 1, 6, 3]
Soit dit en passant, je ne crois pas que quelqu'un pourrait aboutir à un tel code en 24 heures en utilisant Java ou C++.
Python offre des facilités incroyables, et ça dépote....
heyquem ,
t'as l'air assez callé en python,
pourrais tu me donner des astuces pour optimiser un code que j'ai fait ( comment mieux écrire une boucle, comment éviter de stocker des informations qu'on utilise pas, comment parcourir une liste de la meilleure manière possible?)
est ce que ça serait possible???
Merci
t'as l'air assez callé en python,
pourrais tu me donner des astuces pour optimiser un code que j'ai fait ( comment mieux écrire une boucle, comment éviter de stocker des informations qu'on utilise pas, comment parcourir une liste de la meilleure manière possible?)
est ce que ça serait possible???
Merci
Oui merci j'avais remarqué,
et pour ma question précédente? ("heyquem ,
t'as l'air assez callé en python,
pourrais tu me donner des astuces pour optimiser un code que j'ai fait ( comment mieux écrire une boucle, comment éviter de stocker des informations qu'on utilise pas, comment parcourir une liste de la meilleure manière possible?)
est ce que ça serait possible???
Merci")
Merci
et pour ma question précédente? ("heyquem ,
t'as l'air assez callé en python,
pourrais tu me donner des astuces pour optimiser un code que j'ai fait ( comment mieux écrire une boucle, comment éviter de stocker des informations qu'on utilise pas, comment parcourir une liste de la meilleure manière possible?)
est ce que ça serait possible???
Merci")
Merci
Merci pour la réctification,
et sinon pour le problème en lui même? :d
Mais ton énoncé n'est pas assez clair:
- dans le résultat [[1, 4],[4, 8], [8, 7],[7, 3],[3, 6], [6, 1]] que tu donnes, la liste suivant [1, 4] commence par 4 , la liste suivant [4, 8] commence par 8, etc Est-ce que ça doit toujours être ainsi ?
- pourquoi le résultat ne serait il pas:
[[1, 4],[4, 8],[8, 4],[4,1],[1,6],[6, 1]]
Et si la liste était plus longue, il y aurait des éléments [7,13],[7,9],[7,22],[7,56].... qui permettraient d'autres détours plus compliqués
- je remarque qu'il n'y a pas de sous-liste de la liste qui contienne comme deuxième élément un nombre qui ne soit pas présent aussi à titre de premier élément dan,s d'autres sous-listes. Est-ce toujours le cas ? La liste de sous-listes vérifie-t-elle toujours certaines propriété telles que celle-ci ?
Je pense qu'il faut utiliser une procédure récursive. J'essaye de mettre ça au point.