Discussion :

[Aigaio]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[afranck64]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

[afranck64]

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

[plxpy]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

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

[afranck64]

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

Vraiment?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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)

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

[Aigaio]

J'avais fais sa comme sa :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 ?

[afranck64]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

 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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

[Aigaio]

Je me coucherai moin bete se soir

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

Merci !

[Aigaio]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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é... ) 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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

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.

[plxpy]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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)]
>>>

[Aigaio]

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)

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[Aigaio]

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