Problème boucle Python "Out of Range"

Version imprimable

Bonjour,

Je debute en python. Tout d'abord j'explique ce que je cherche a faire.
J'ai une liste d'entier, [3,8,9,4,5,1,8], je cherche a regrouper les entiers de facon a tant que " liste[i] < liste[i+1] ". Ce qui donnerai en resultat pour l'exemple au dessus [3,8,9], [4,5], [1,8]. Je reange tout sa dans une liste final. Mon probleme vient d'une boucle dont l'index depasse l'index max de la liste.
Code:

1 2 3 4 5 6 7 8 9 10 11 12 def func(listeNB) : i = 0; j = 0; liste = []; while (len(listeNB)>0) : j=1; while ((listeNB[j] > listeNB[j-1]) and (j < len(listeNB))): j+=1; liste.append(listeNB[:j]); # print liste; PRINT DE VERIFICATION listeNB = listeNB[j:]; print liste;
Donc mon script ne marche pas :
while ((listeNB[j] > listeNB[j-1]) and (j < len(listeNB))):
IndexError: list index out of range

Mon print de verification me donne cela :
[[3, 8, 9]]
[[3, 8, 9], [4, 5]]
et bug au prochain tour de boucle.

J'ai beau chercher l'erreur dans la condition de la boucle, elle me parait logique. Ma logique est peut etre en compote, je m'en remet a vous pour m'eclairer sur ce petit problème, je suis sur tout bête.

Merci d'avance

01/12/2011, 15h24
afranck64

Citation:

Envoyé par Aigaio

Code:

while ((listeNB[j] > listeNB[j-1]) and (j < len(listeNB))):;

Il me semble que vous ne vérifiez pas que j soit inférieur à la taille de la liste avant de la comparaison des éléments.
01/12/2011, 15h25
afranck64

Euh, je voulais dire que le test sur la longueur doit être le premier a être effectué :lol:

Bonjour

sauf dans certains cas où les performances peuvent s'en ressentir, je trouve qu'il est préférable d'abandonner la façon de coder en C (en ...) quand on passe à Python. Ici, pourquoi s'embêter à ce point avec des indices de listes ?

De la façon suivante, on ne risque guère de se prendre les pieds dans le tapis avec des indices trop grands ou des trucs dans le genre :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 >>> def func(listeNB): ... # initialisation de la liste retour avec 1 liste contenent le 1er element ... result = [[listeNB[0]]] ... # boucle sur les elements restants ... for elt in listeNB[1:]: ... # création d'une nouvelle liste vide si besoin ... if elt <= result[-1][-1]: ... result.append(list()) ... # ajout systématique en fin de dernière liste ... result[-1].append(elt) ... return result ... >>> >>> >>> initiale = [3,8,9,4,5,1,8] >>> >>> print func(initiale) [[3, 8, 9], [4, 5], [1, 8]] >>>

01/12/2011, 16h23
Aigaio

@afranck64 : J'étais toujours exposer au même probleme.

@plxpy : Il est vrai que c'est bien plus efficace. Comme je l'ai dis, je debute en python, et je suis pas un professionnel en matiere de programmation. Donc la facon de coder est comme un reflexe.

Un grand merci a vous deux. Rapide et Efficace.

Citation:

Envoyé par Aigaio

@afranck64 : J'étais toujours exposer au même probleme.

Vraiment?
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 lst = [3,8,9,4,5,1,8] def func(listeNB) : i = 0; j = 0; liste = []; while (len(listeNB)>0) : j=1; while ( j< len(listeNB) and (listeNB[j] > listeNB[j-1])): j+=1; liste.append(listeNB[:j]); # print liste; PRINT DE VERIFICATION listeNB = listeNB[j:]; print liste; func(lst)
Citation:

*** Remote Interpreter Reinitialized ***
>>>
[[3, 8, 9], [4, 5], [1, 8]]

J'avais fais sa comme sa :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 lst = [3,8,9,4,5,1,8] def func(listeNB) : j = 0; liste = []; while (len(listeNB)>0) : j=1; if(j< len(listeNB)): while (listeNB[j] > listeNB[j-1]): j+=1; liste.append(listeNB[:j]); # print liste; PRINT DE VERIFICATION listeNB = listeNB[j:]; print liste; func(lst)
Et effectivement si je passais le if, sa empechais pas le while de s'arreter. J'avais mal compris. Mais sa me choque que l'ordre soit important, sa reste un And. Pourquoi ne le prend t'il pas en compte si on le place en deuxieme ?

A & B = B & A
non ?

01/12/2011, 17h01
afranck64

Citation:

Envoyé par Aigaio

Mais sa me choque que l'ordre soit important, sa reste un And. Pourquoi ne le prend t'il pas en compte si on le place en deuxieme ?

L'ordre importe que l on soit en C, Pascal, Cpp, Java, ...
Supposons:
j = 4
len(listeNB) = 4
Le code:

Code:

while ( j< len(listeNB) and (listeNB[j] > listeNB[j-1])):

demande a l interpréteur de:
- vérfier que j est inférieur: non ==> on a False, on arrête d'évoluer.

Tandis que le code:

Code:

while ((listeNB[j] > listeNB[j-1]) and (j < len(listeNB))):

demande à l interpréteur de:
- agir sur listeNB[4]: hors-limite ==> exception. On n a pas pu faire la comparaison sur la taille voulue. :aie:
01/12/2011, 17h30
Aigaio

Je me coucherai moin bete se soir :mouarf:

Et je suis sur que cela m'aurai servis dans d'autres etudes sur lesquelles je bloquais a cause d'une condition semblable.

Merci !

Me revoila avec un autre probleme. Ce que je veux faire est difficile a expliquer, je vais essayé d'etre clair.

Nous avons toujours notre liste d'entier (3,8,4,5,1,8). Je cherche a trouver toutes les sous-suites croissante puis la sous-suite de longueur maximum.
(3,8) est une sous-suite croissante, (3,5,8) en est une autre, (3,4,5,8) est la sous-suite de longueur max.

On ne peux pas deplacer les elements mais on saute un element plus petit que le precedent.
Pour 3,4,5,8 --> on a sauter liste[1] et liste[4].
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 def allSousSuite(i, listeNB): pile = [listeNB[i]] for elt in listeNB[i+1:]: lenPile = len(pile) if(pile[lenPile-1] < elt): pile.append(elt) print "pile "+str(i)+" = "+str(pile) return pile def SousSuite(listeNB): result = [] i=0 while (i < len(listeNB)): temp = allSousSuite(i, listeNB) if(len(temp) > 1): result.append(temp) i += 1 return result def MaxSousSuite(listeNB): listResult = SousSuite(listeNB) result = listResult[0] for elt in listResult[1:] : if (len(elt) > len(result)) : result = elt return result initiale = [3,8,4,5,1,8] print "Sous Suite Max = "+ str(MaxSousSuite(initiale))
allSousSuite nous renvoie (censé... :aie:) toutes les SousSuite avec les singlotons pour 8 par exemple etant l'entier maximum.

SousSuite supprime donc ces singlotons.

MaxSousSuite permet d'afficher la SousSuite la ou une des sous suite la plus longue.

Mon probleme que voici :
la fonction allSousSuite est censé renvoyer 2^n sous-suite pour une liste de longueur n. Hors la je n'ai que n sous suite.

Resultat Terminal :
Code:

1 2 3 4 5 6 7 pile 0 = [3, 8] pile 1 = [8] pile 2 = [4, 5, 8] pile 3 = [5, 8] pile 4 = [1, 8] pile 5 = [8] Sous Suite Max = [4, 5, 8]
é
Je dois trouver :
Code:

1 2 3 4 5 6 7 8 9 10 pile 0 = [3, 8] pile 1 = [3,4,5,8] pile 2 = [3, 5, 8] pile 3 = [3, 8] pile 4 = [8] pile 5 = [4,5,8] pile 6 = [4,8] ... Sous Suite Max = [3,4, 5, 8]
Il doit me manquer une boucle dans la fonction allSousSuite. Je sais pas comment la faire. Si quelqu'un peut m'aider. Ma methode de pile n'est peut etre pas la meilleur. Je m'abstient ainsi d'executer des calculs, ce qui serait sans doute plus malin, mais je ne sais pas le faire :mrgreen:

Merci d'avance !

EDit: Rien qu'a relire, je vois qu'on peux l'optimiser vraiment beaucoup au niveau taille du code. N'y faite pas attention, je corrigerais cela moi meme.

Comme tu débutes en Python, voici une solution "mathématiquement" élégante pour calculer toutes les sous-suites (sous-séquences) qui utilise la récursivité :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def subsequences(sequence,size=None):
 
    assert size is None or (isinstance(size,(int,long) and 0 <= size)
 
    result = list()
 
    if size == None:
        # on calcule TOUTES les sous-séquences
        for size in range(len(sequence)+1):
            result.extend(subsequences(sequence,size))
 
    elif size == 0:
        result.append(list())
 
    elif len(sequence) < size:
        pass
 
    elif size == 1:
        for number in sequence:
            result.append([number])
 
    else:
        for n,num in enumerate(sequence[:-size+1]):
            for intermediate in subsequences(sequence[n+1:],size-1):
                result.append([num]+intermediate)
 
    return result

* je ne suis pas sur d'avoir testé tous les cas "limites"

Par contre, opérationnellement parlant, elle est inutilisable dès que la liste dépasse quelques éléments :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
>>> for i in range(2,30):
...     print "%2d : " % i,
...     numbers = range(i)
...     t0 = time()
...     res = subsequences(numbers)
...     print "%.2f secondes" % (time()-t0)
... 
 2 :  0.06 secondes
 3 :  0.00 secondes
 4 :  0.00 secondes
 5 :  0.00 secondes
 6 :  0.00 secondes
 7 :  0.00 secondes
 8 :  0.00 secondes
 9 :  0.00 secondes
10 :  0.01 secondes
11 :  0.01 secondes
12 :  0.02 secondes
13 :  0.05 secondes
14 :  0.11 secondes
15 :  0.23 secondes
16 :  0.51 secondes
17 :  1.14 secondes
18 :  2.71 secondes
19 :  5.93 secondes
20 :  12.94 secondes
21 :  27.82 secondes
22 :  61.22 secondes
23 :  129.40 secondes
24 :  280.59 secondes
^C25 : 
Traceback (most recent call last):
  File "<stdin>", line 5, in <module>
  File "suites.py", line 13, in subsequences
    result.extend(subsequences(sequence,size))
  File "suites.py", line 24, in subsequences
    for n,num in enumerate(sequence[:-size+1]):
  File "suites.py", line 24, in subsequences
    for n,num in enumerate(sequence[:-size+1]):
KeyboardInterrupt
>>> # j'ai craqué
... 
>>>

Sinon, la fonction combinations du module itertools (en 2.7 du moins) fait ça très bien :

Code:

1
2
3
4
5
6
7
8
9
10
11
>>> from itertools import combinations
>>> 
>>> sequence = [1,2,3]
>>> 
>>> sous_suites = list()
>>> for i in range(len(sequence)+1):
...     sous_suites.extend(combinations(sequence,i))
... 
>>> print sous_suites
[(), (1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)]
>>>

Merci de vous être donner la peine de faire cela de votre coter, mais je trouve ce code trop complexe... Je ne comprend pas tout. Je vais essayer une autre méthode et la proposer quand j'aurai trouver (Si je trouve) :mouarf:

Edit: En cherchant sur le net j'ai trouvé ceci :
Code:

1 2 3 4 5 6 7 pour tous les 0 < i < n pour tous les 0 < j < n Si ( X[j] < X[i]) faire si ( L[j] + 1> L[i]) L[i] = L[j] + 1; fin{j} fin{pour i}
Qu'en pensez vous ?

Link : http://binetacm.wikidot.com/algo:incrsubseq

06/12/2011, 18h24
Aigaio

Je passe en Résolu, mon autre probleme ce trouve ici http://www.developpez.net/forums/d11...e/#post6384794