Python, listes

Résolu/Fermé

hautDébit - 5 juin 2012 à 16:42
hautDébit - 11 juin 2012 à 08:45

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

A voir également:

Python, listes
Citizen code python - Guide
Extraire données fichier texte python ✓ - Forum Python
Additionner deux listes python - Forum Python
Geometry dash python ✓ - Forum Python
Lancer script python linux - Forum Ubuntu

4 réponses

Réponse 1 / 4

heyquem Messages postés 759 Date d'inscription mercredi 17 juin 2009 Statut Membre Dernière intervention 29 décembre 2013 130
5 juin 2012 à 18:31

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

hautDébit
5 juin 2012 à 20:23

Abus de langage,
Merci pour la réctification,
et sinon pour le problème en lui même? :d

heyquem Messages postés 759 Date d'inscription mercredi 17 juin 2009 Statut Membre Dernière intervention 29 décembre 2013 130
Modifié par heyquem le 5/06/2012 à 20:39

Le match Tsonga - Djokovitch m'a éloigné de l'ordi

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 ?

hautDébit
5 juin 2012 à 22:29

OUi, effectivement, la liste des sous liste vérifie cette condition, c'est à dire c'est l'ensemble de plusieurs sous-listes qui forment une boucle, tu peux imaginer un grand polygone et les sous liste sont des segments

heyquem Messages postés 759 Date d'inscription mercredi 17 juin 2009 Statut Membre Dernière intervention 29 décembre 2013 130
6 juin 2012 à 08:31

C'est donc un problème de recherche de chemin ?
Je pense qu'il faut utiliser une procédure récursive. J'essaye de mettre ça au point.

Réponse 2 / 4

heyquem Messages postés 759 Date d'inscription mercredi 17 juin 2009 Statut Membre Dernière intervention 29 décembre 2013 130
5 juin 2012 à 20:45

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

hautDébit
6 juin 2012 à 08:58

Merci pour la méthode, mais ([1, 4], [1, 4]) est un doublon*, et ([1, 4],[4, 1]) aussi :(:(
(dans mon cas)

heyquem Messages postés 759 Date d'inscription mercredi 17 juin 2009 Statut Membre Dernière intervention 29 décembre 2013 130
Modifié par heyquem le 6/06/2012 à 11:28

Alors il faut écrire

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

hautDébit
6 juin 2012 à 11:37

C'est tout à fait ce qu'il me faut, mais ça fait 24 h que je suis dessus et j'avance pas du tout!!!!!!!
je te remercie!

Réponse 3 / 4

heyquem Messages postés 759 Date d'inscription mercredi 17 juin 2009 Statut Membre Dernière intervention 29 décembre 2013 130
6 juin 2012 à 11:40

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.

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)

hautDébit
6 juin 2012 à 13:08

Je te remercie pour ton code qui est très clair
j'ai bien compris l'algorithme mais j'ai un problème lors de l'exécution:
for k,v in d.iteritems():
AttributeError: 'collections.defaultdict' object has no attribute 'iteritems'

:s:s

heyquem Messages postés 759 Date d'inscription mercredi 17 juin 2009 Statut Membre Dernière intervention 29 décembre 2013 130
Modifié par heyquem le 6/06/2012 à 13:51

Je pense que tu utilises Python 3 dans lequel les attributs iteritems() ont été remplacés par items()
De ce fait il faut que tu mettes entre parenthèses tout ce que j'ai mis après des print car print est devenu une fonction en Python 3 alors que c'était un statement en Pyrthon 2

hautDébit
7 juin 2012 à 09:50

Bonjour
Je suis désolé de répondre tardivement,
Merci beaucoup pour ton algorithme, je l'ai testé et il marche très bien, ça m'a vraiment débloqué
et effectivement j'utilise le Python 3
Merci encore
Bonne journée

Réponse 4 / 4

heyquem Messages postés 759 Date d'inscription mercredi 17 juin 2009 Statut Membre Dernière intervention 29 décembre 2013 130
Modifié par heyquem le 7/06/2012 à 13:14

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

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....

hautDébit
8 juin 2012 à 09:21

waw!

hautDébit
8 juin 2012 à 09:39

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

heyquem Messages postés 759 Date d'inscription mercredi 17 juin 2009 Statut Membre Dernière intervention 29 décembre 2013 130
8 juin 2012 à 09:43

J'ai oublié de te signaler que j'ai remplacé une ou deux lignes

del d[n][-1]

par

if len(d[n]):  del d[n][-1]

sinon il y avait parfois une erreur

hautDébit
11 juin 2012 à 08:45

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

Discussions similaires

programme qui n'affiche pas le mot secret

Python introuvable

[Python] différence entre \r et \n

syntaxe pour passer une ligne de code python

[PYTHON] Récupérer position dans liste

Discussions similaires

Newsletters