[Python] Problème de boucle Résolu/Fermé

Question

Bonjour,
Je souhaite réaliser une fonction qui doit renvoyer une liste de couples de nombres de manières aléatoire mais il faut que ces couples ne se "croisent pas", ils doivent suivre un ordre croissant ou décroissant par rapport aux autres couples cad par exemple la liste [(0,1),(2,4),(3,5)] est correcte mais [(0,1),(2,4),(3,3)] n'est pas bon puisque (3,3) croise avec (2,4). J'ai fait une fonction qui me renvoi ce que je veux mais une fois sur 5, j'ai une boucle infinie et une fois arrêtée j'ai ce message:

^CTraceback (most recent call last):
File "RecuitSimule.py", line 64, in <module>
FirstCorresp = TirerFirstCorresp(Seq1,Seq2,3)
File "RecuitSimule.py", line 41, in TirerFirstCorresp
(posSeq1,posSeq2) = (randrange(0,len(seq1)),randrange(0,len(seq2)))
File "/System/Library/Frameworks/Python.framework/Versions/2.7/lib/python2.7/random.py", line 198, in randrange
KeyboardInterrupt

J'ai beau cherché sur internet mais je ne vois pas pourquoi l'invite affiche ça. Ma fonction ressemble à ça:

def TirerFirstCorresp(seq1,seq2,nbCorresp):
	from random import randrange
	ali = []			
	i=0				
	croisement=True
	while i < nbCorresp:		
		if ali==[]:				
			ali.append((randrange(0,len(seq1)),randrange(0,len(seq2))))
			i+=1
		else:			
			while croisement==True:
				(posSeq1,posSeq2)=(randrange(0,len(seq1)),randrange(0,len(seq2)))								
				for l in range(len(ali)):			
					if posSeq1 > ali[l][0] and posSeq2 < ali[l][1] or posSeq1 < ali[l][0] and posSeq2 > ali[l][1] or posSeq1 == ali[l][0] or posSeq2 == ali[l][1]:					
						croisement = True
						break	
					else:
						croisement = False
			ali.append((posSeq1,posSeq2))		
			ali.sort()						
			i +=1
			croisement = True		
	return ali

Je débute en programmation donc j'imagine que ma fonction est assez lourde et je vous demande pas de l'améliorer mais juste si vous avez le temps de m'indiquer pourquoi j'ai une boucle infinie avec cette fonction.
Merci d'avance

Char Snipeur · Answer

Je n'ai pas réfléchi au problème, mais d'expérience j'ai déjà vu ça :
ça ne viendrais pas de la priorité des opérateur or et and ? Met des parenthèses pour être sur de ce que tu fais.

Lionice · Answer

J'avoue ne pas très bien comprendre la priorité des opérateurs. Il faut un ordre de placement?

heyquem · Answer

Bonjour,

Qu'est ce que les paramètres seq1 et seq2 de la fonction doivent recevoir comme arguments , stp ?

Lionice · Answer

seq1 et seq2 sont des listes de caractères, les couples de valeurs aléatoires que la fonction doit renvoyer correspondent aux positions respectivement des caractères de seq1 et seq2. Je les utilise uniquement pour avoir la taille de ces listes et tirer un couple de nombre au hasard.

heyquem · Answer

Il n'est pas clair pour moi quand deux couples se croisent et quand ils ne se croisent pas. 
Peux-tu mieux expliquer ce que tu entends par là ?

(3,3) ne croise pas (2,4) pour moi, il est dedans

Lionice · Answer

C'est quand je tire au hasard un nouveau couple, il faut que les deux valeurs soit supérieures ou inférieures aux couples présents dans la liste. Dans mon exemple quand j'ai dit que (3,3) croise avec (2,4) c'est que la première valeur (3) dans le premier couple est supérieure à la première du deuxième couple (2) mais la deuxième du premier couple est inférieure à la deuxième dans l'autre couple (4). C'est ces "croisements" que je veux éviter en créant ma liste de couples au hasard.

heyquem · Answer

J'ai utilisé le code suivant:

def TirerFirstCorresp(seq1,seq2,nbCorresp):  
    from random import randrange  
    ali = []     
    i=0  
    croisement=True  
    while i < nbCorresp:  
        print 'i == %d   j == %d' % (i,j)  

        if ali==[]:  
            ali.append((randrange(0,seq1),randrange(0,seq2)))  
            print ali  
            print '\n-----------------------------------------------'  
            i+=1  
        else:     
            while croisement==True:  
                (posSeq1,posSeq2)=(randrange(0,seq1),randrange(0,seq2))  
                print '\n(posSeq1,posSeq2) ==',(posSeq1,posSeq2)  
                for l in range(len(ali)):  
                    if ali[l][0] < posSeq1 and posSeq2 < ali[l][1]:  
                        print "   %d,%d dans (%d,%d)" % (posSeq1 , posSeq2,ali[l][0],ali[l][1])  
                    if posSeq1 < ali[l][0] and ali[l][1] < posSeq2:  
                        print "   %d,%d autour de (%d,%d)" % (posSeq1 , posSeq2,ali[l][0],ali[l][1])  
                    if posSeq1 == ali[l][0]:  
                        print "   %d == ali[l][0]" %posSeq1  
                    if posSeq2 == ali[l][1]:  
                        print "   %d == ali[l][1]" % posSeq2  
                    if posSeq1 > ali[l][0] and posSeq2 < ali[l][1]\  
                       or posSeq1 < ali[l][0] and posSeq2 > ali[l][1]\  
                       or posSeq1 == ali[l][0] or posSeq2 == ali[l][1]:  
                        croisement = True  
                        break   
                    else:  
                        croisement = False  
                        print '  OK ==> ',  
            ali.append((posSeq1,posSeq2))    
            ali.sort()  
            print 'ali: %r' % ali  
            if i:  
                raw_input()  
            i +=1  
            croisement = True  
        print  

    return ali  




print TirerFirstCorresp(10,45,5)

Avec 10 et 45 passés en arguments,
pour sortir le prochain couple (posSeq1,posSeq2) :

posSeq1 = randrange(0,10)

c'est à dire que posSeq1 doit prendre au hasard une valeur entre 0 et 9 compris

posSeq2 = randrange(0,45)

c'est à dire que posSeq2 doit prendre au hasard une valeur entre 0 et 44 compris

Lors d'un essai, ça a sorti d'abord le couple (0 , 43) puis le couple (5 , 44). A partir de là c'est une boucle infinie. En effet:

- pour n'importe quelle valeur autorisées pour posSeq1, c'est à dire 0,1,2,3,4, 6,7,8,9 puisque 5 est interdit par la première borne du deuxième couple , il faut que posSeq2 soit supérieure à 43 afin que (posSeq1,posSeq2) ne se retrouve pas à l'intérieur du couple (0,43)

- plus grand que 43, il y a 44 dans le range(0,45). Mais 44 est déjà la borne sup de l'autre couple (5,44) , donc impossibilité de trouver un troisième couple.

Ton problème n'est même pas un problème d'algorithme, c'est que ton problème mathématique de départ est vicié.

Lionice · Answer

Merci pour la réponse aussi rapide, j'espère ne pas t'avoir trop dérangé. Je me suis beaucoup cassé la tête avec ce code et comme je débute, ça m'est pas venu à l'idée de chercher le problème comme tu l'as fait. Encore merci :-)

heyquem · Answer

Mais non ça ne m'a pas dérangé, sinon je ne l'aurais pas fait. Quand on aime programmer et Python, c'est amusant de chercher.

Cependant, si le principe de ton projet n'est pas réaliste, tu restes avec un problème, non ? Que vas tu faire par rapport à ce projet ?

Lionice · Answer

Je crois que je vais directement en parler à mon professeur pour voir si j'ai mal compris le problème.

heyquem · Answer

Tu devrais essayer de trouver d'autres cas où ça part en boucle infinie en faisant tourner mon code qui affiche l'exécution intermédiaire.



Soit dit en passant , je trouve bizarre que le randrange parte toujours de 0.

Note aussi une chose, c'est que les couples créés par

(posSeq1,posSeq2)=(randrange(0,seq1),randrange(0,seq2)) 
ne sont pas nécessairement avec posSeq1 < posSeq2

Char Snipeur · Answer

je revient sur la priorité des opérateurs :

posSeq1 > ali[l][0] and posSeq2 < ali[l][1] or posSeq1 < ali[l][0] and posSeq2 > ali[l][1] or posSeq1 == ali[l][0] or posSeq2 == ali[l][1]

je crois que or et and ont la même priorité (à vérifier en python) et dans ce cas là, prenons un cas faux, où posSeq1 > ali[l][0] et posSeq2 < ali[l][1]. ça nous fait alors :

true and true or false and false or false or false

comme les opérateurs ont la même priorité, il faut calculé par la gauche. Je développe les différentes opérations :

true  or false and false or false or false

true  and false or false or false

 false or false or false

 false

alors que d'après ta règle il devrait donner true.
D'où la protection par parenthèse pour avoir ce que tu veux (faire les deux premiers or d'abord)

heyquem · Answer

Non, and est prioritaire sur or en Python:
https://docs.python.org/3/reference/expressions.html#evaluation-order

Vérification avec un petit programme:

tu = (False,True)
li = []
for a in tu:
    for b in tu:
        for x in tu:
            for y in tu:
                p  = (a and b) or (x and y)
                wp = a and b or x and y
                li.append(p==wp)

print li
print '
all(li)==%s' % all(li)

résulte en 

[True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True]

all(li)==True

Lionice · Answer

C'est vraiment sympa de ta part de m'expliquer cette notion en détail, j'ai mis un peu de temps à répondre parce que j'avais un peu de mal à interpréter ta fonction. J'imaginais pas qu'il y avait de priorité avec les opérateurs.

[Python] Problème de boucle

14 réponses

Discussions similaires