Bonjour à tous, voilà, pour la fac je dois écrire un programme listant tous les cycles d'une liste et les renvoyant avec un print.

Pour rappel voici un exemple:

la liste L=[3,4,1,5,10,6,2,7,9,8] est une permutation ( chaque élément n'est présent qu'une fois et est inférieur ou égal à len(L))

quand on part du début, la première case a pour valeur 3, on va a la 3e case, valeur 1, comme on est revenu sur la case, le cycle est complet, c'est le cycle [1,3], on passe à la suite, case 2, valeur 4, case 4 valeur 5 case 5 valeur 10, case 10 valeur 8, case 8 valeur 7, case 7 valeur 2, case 2 valeur 4, cycle fini, c'est le cycle [2,4,5,10,8,7], on passe à la suite, on avance jusqu'à la prochaine case ne faisant pas partie d'un cycle, soit la case 6, de valeur 6, c'est le cycle [6] et enfin la case 9 de valeur 9, le cycle [9]

L'objectif est de renvoyer all_cycles=[[1,3],[2,4,5,10,8,7],[6],[9]]

voici mon code:

def parcours (L):
    dejavu=[]
    all_cycles=[]
    k=0
    cycle_courant=[]
    for i in range(len(L)):
        j=i+1
        valeur=L[k]
        print("rang=",i)
        print("position=",j)
        print("L[i]=",valeur)
        if i not in dejavu:
            print("tour", i, " de la boucle")
            dejavu.append(k)
            print("dejavu=",dejavu)
            cycle_courant.append(j)
            print("cycle_courant=",cycle_courant)
            k=valeur
            all_cycles.append(cycle_courant)
            print("all_cycles=",all_cycles)
        else:
            cycle_courant=[]
    print(all_cycles)

parcours([3,4,1,5,10,6,2,7,9,8])

Le problème c'est que ça marche pas, je sais absolument pas pourquoi, et pour tout arranger je n'ai le droit d'utiliser que des fonctions basiques de python, rien de trop complexe ( on est sensés commencer tout juste, c'est pour "apprendre", mais c'est là galère ). J'aimerais donc savoir si qqn pouvait m'aider à trouver le problème dans les valeurs de sorte à résoudre le problème, je vous invite à lancer le code pour voir ce que ça renvoie, mais c'est pas du tout ce que je veux. Notez aussi que j'ai rajouté plein de print, pour essayer de trouver le problème mais je vois pas, et au bout de 2h de recherches à bloquer là dessus je perds un peu le moral :/

Merci d'avance pour votre aide,

Nocktambule

Je ne ferais pas de boucle for dans ce cas, car tu ne dois pas passer dans les éléments de la liste dans l'ordre. Moi j'ai une solution avec deux boucles while. La première s'assure qu'on n'a pas encore vu tous les éléments while len(dejavu) != len(liste) et la deuxième sert à vérifier qu'on n'a pas encore fini un cycle.

Tu as bien décrit l'algorithme en français. Pourquoi ne pas essayer de le traduire en Python?

T'as correctement établi trois liste : dejavu, cycle_courant et all_cycles.

Tu écris qu'on commence à la première case (donc indice 0). Il te faut une variable qui retienne où t'es parti (afin de comparer si t'es revenu au même endroit, et une variable qui contient l'indice courant. Tu places le premier élément de la liste dans cycle_courant.

Ensuite tu change ton indice courant pour qu'il soit égal à la valeur du premier élément de la liste. Tu regardes si ce nouvel indice n'est pas égal à l'indice de départ.

Si c'est le cas, le cycle est fini, donc tu ajoutes la liste cycle_courant à all_cycles, et tu ajoutes tous les éléments de cycle_courant à dejavu. Tu ré-initialise cycle_courant à une liste vide. Et tu reviens au début (vérifier si la longueur de dejavu est égale à la liste passée en argument).

Sinon, tu ajoutes l'élément à cycle_courant et tu change l'indice courant pour être égale à la valeur dans la liste de l'indice courant.

Tu retournes finalement all_cycles.

Le problème est que j'arrive parfaitement à comprendre et intégrer un algorithme, mais pas à le traduire, il y a toujours quelque chose qui cloche quand je passe par cette phase, alors que dans ma tête, quand j'ai écrit ce code, je l'ai fait " à l'instinct ", sans réfléchir à l'algo, j'ai direct foncé dans le code. Du coup je comprends exactement ce que tu m'explique, mais j'arrive pas à voir comment modifier mon code en conséquence, mis à part la substitution du for par un while, qui a entrainer nombre d'autres adaptation pour garder une boucle stable, très probablement.

quand on part du début, la première case a pour valeur 3

Comment tu pourrais traduire ça en Python? Il faut prendre cette valeur et la mettre dans une variable, non?

on va a la 3e case

Tu fais ça comment?

valeur 1

Et comment tu prends la valeur?

comme on est revenu sur la case, le cycle est complet

Donc il faut une autre variable qui retienne d'où on est parti. Il va falloir qu'à chaque fois qu'on aille dans une autre case, qu'on vérifie que cette case ne soit pas celle de départ, sinon...

c'est le cycle [1,3]

...c'est qu'on a un cycle. Il aura donc fallu ajouter à une liste vide cycle_courant les valeurs visitées depuis le début. Donc on initialise cette variable en début de code à une liste vide, et à chaque voit qu'on prend la valeur d'une case, on ajoute à la liste cette valeur. Maintenant on ajoute cette liste de 2 valeurs à une autre liste all_cycles. Donc il faut aussi initialiser cette variable à une liste vide en début de code et maintenant ajouter notre liste dedans. Ce sera donc une liste de listes.

on passe à la suite, case 2

Donc on incrémente de 1 l'indice de départ. Attention en Python les indices commencent à 0. Donc on voudra commencer à 0. Lorsqu'on lit une valeur d'une case (par exemple 3), on voudra retirer 1 pour obtenir l'indice correspondant L[2] # accède au troisième élément.

> valeur 4, case 4 valeur 5 case 5 valeur 10, case 10 valeur 8, case 8 valeur 7, case 7 valeur 2, case 2 valeur 4, cycle fini, c'est le cycle [2,4,5,10,8,7]

Tout ceci a déjà été expliqué. On ne fait que suivre l'algorithme déjà produit.

on passe à la suite, on avance jusqu'à la prochaine case ne faisant pas partie d'un cycle, soit la case 6

Ah! Donc il ne nous suffit pas d'incrémenter de 1. Il faut ensuite d'assurer que ce nouvel indice ne soit pas déjà visité. On a donc une liste vide dejavu (il faut l'initialiser en début de code). A chaque fois qu'on prend une valeur d'une case, on ajoute cette valeur à la liste dejavu. On n'oubliera pas d'ajouter le tout premier élément aussi, puisque c'est par là qu'on commence. Donc quand on veut passer à la case suivante, on incrémente de 1 tant que cette nouvelle case ne soit pas déjà dans la liste dejavu. Si on arrive en fin de liste, c'est qu'il n'y a plus d'éléments à visité => donc ils doivent être déjà tous dans la liste dejavu.

de valeur 6, c'est le cycle [6] et enfin la case 9 de valeur 9, le cycle [9]

Tout ça est aussi déjà expliqué.

Il ne reste plus qu'à retourner notre liste de listes all_cycles.

-
Edité par Dan737 23 mars 2015 à 8:45:34