Python, listes Résolu/Fermé

Question

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

heyquem · Answer

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

heyquem · Answer

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,'
'
li_wo_dbl = []
li_wo_dbl.extend( el for el in li if el not in li_wo_dbl)
print li_wo_dbl

heyquem · Answer

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 '
On veut obtenir [[1, 4],[4, 8], [8, 7],[7, 3],[3, 6], [6, 1]]
'\
      "c'est à dire  1,4,8,7,3,6,1 "


print "
================================================="

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 "
n == %d
li == %r
notthis == %r" % (n,li,notthis)
        if running and n==depart:
            print '  ici premier return break'
            return 'break'
        elif n in d:
            print ("  d[%d] == %r
"
                   "  d[%d][-1] == %d
"
                   "  (%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 "

Résultat : %r" % cherche_chemin(the_list)

heyquem · Answer

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 :
 %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 ('
dictionnaire  d :
%s' % '
'.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 ("
n == %d
li == %r
notthis == %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
" 
                        "  d[%d][-1] == %d
" 
                        "  (%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 ('
sommets sont : %s
' % ', '.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 ('
%s' % '
'.join("départ == %d    résultat : %r" % res 
                              for res in resulti) 
           ) 


print '

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

Python, listes

4 réponses

Discussions similaires