Discussion :

[Amniote]

Salut,

Supprimer l'interaction qu'on va utiliser et la rajouter ensuite ne pose pas de problème particulier... Si?

- W

Je ne suis pas sûr d'avoir bien compris la question...

Lorsque l'interaction est ajoutée à notre chaîne (1), on peut en effet la supprimer (pour quelle ne soit pas réutilisée dans cette même chaîne (1) ) et ensuite la rajouter pour quelle soit de nouveau imbriquable dans une nouvelle chaîne (2) (et une fois qu'elle sera ré-imbriquée dans cette nouvelle chaîne (2), on la supprime pour cette chaîne (2)) et ainsi de suite...

Cela réponds à votre question ?

[wiztricks]

Je ne suis pas sûr d'avoir bien compris la question...

Je disais juste que modifier le code pour qu'il prenne en compte cela (ou autre chose) est assez facile.

Code :

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

1
2
3
4
5
6
7
8
def chain(nodes, path=None, limit=3):
 
    next_ = nodes.get(path[-1], None)
    if next_ is None or len(path) >= limit:
        yield path
    else:
        for m in next_:
            yield from chain(nodes, path + [m])

Dans les 2 dernières lignes, next_ est l'ensemble des interactions de path[-1].
Pour chaque "m", le retirer de l'ensemble avant de descendre dans le chainage suivant, et l'y remettre au retour ne présente pas de difficultés.

- W

[Amniote]

Merci pour les indices

J'ai fait ceci et j'ai l'impression que cela fonctionne, cela vous semble t'il correct (d'un point de vue algorithmique) ?

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
 
with open ("C:/Users/lveillat/Desktop/Données stage/Données/resultats_matrice_avec_scores_sans_localisation.txt","r") as f1:
	for ligne in f1:
		lp = ligne.rstrip('\n').split(" ")
		prot1 = lp[0] #je sélectionne la première protéine de chaques interactions
		prot2 = lp[1] #je sélectionne la seconde protéine de chaques interactions
		dd[prot1].add(prot2) #Je crée mon dictionnaire avec en clé la première prot de l'interaction et en valeurs l'ensembles des prots avec qui elle peut interagir
 
def chain(nodes, path=None, limit=100): #Je définis une fonction chain( , chaine d'interactions ,la taille de la chaine)
	next_ = nodes.get(path[-1], None)
 
	if next_ is None or len(path) >= limit: #Si la taille dépasse la limite de taille alors on passe a la chaine suivante
		yield path
                setdejavu.clear()
 
	else:
		for m in next_: # next_ est l'ensemble des interactions de path[-1]
			if m not in setdejavu:
				setdejavu.add(m)
				yield from chain(nodes, path + [m]) #On rajoute une autre prot à la chaine
 
 
for k in dd: # Pour chaques prot du dico
	for z in chain(dd, path = [k]): #Pour chaques chaines
		print (' '.join(z),'\n')

Je ne comprends pas dans l’algorithme a quoi sert "path=None" pouvez vous me l'expliquer svp ?

[wiztricks]

J'ai fait ceci et j'ai l'impression que cela fonctionne

Demandez à Python d'exécuter votre code... et vous pourriez avoir une réponse rapide.

cela vous semble t'il correct (d'un point de vue algorithmique) ?

Faites un ou plusieurs jeux d'essais pour lesquels vous savez le résultat attendu et vous comparez avec le résultat calculé.

- W

[Sve@r]

J'ai fait ceci et j'ai l'impression que cela fonctionne, cela vous semble t'il correct (d'un point de vue algorithmique) ?

Je ne vois pas la création de setdejavu mais si ça fonctionne chez-toi, il y est alors forcément.

Je ne comprends pas dans l’algorithme a quoi sert "path=None" pouvez vous me l'expliquer svp ?

Valeur par défaut d'un paramètre de fonction. def carre(x=0): return x**2 tu peux l'appeler ainsi r2=carre(2) ou bien ainsi r0=carre().

[wiztricks]

Je ne comprends pas dans l’algorithme a quoi sert "path=None" pouvez vous me l'expliquer svp ?

Il ne sert à rien: vous pouvez supprimer le "=None"

- W

[Amniote]

Bonjour, je reviens avec une petite question concernant ce fameux code

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
 
import sys
sys.setrecursionlimit(10000)
from collections import defaultdict
dd = defaultdict(set)
setdejavu=set()
 
with open ("C:/Users/lveillat/Desktop/Données stage/Données/resultats_matrice_avec_scores_sans_localisation.txt","r") as f1:
	for ligne in f1:
		lp = ligne.rstrip('\n').split(" ")
		prot1 = lp[0] #je sélectionne la première protéine de chaques interactions
		prot2 = lp[1] #je sélectionne la seconde protéine de chaques interactions
		dd[prot1].add(prot2) #Je crée mon dictionnaire avec en clé la première prot de l'interaction et en valeurs l'ensembles des prots avec qui elle peut interagir
		#print(dd)
def chain(nodes, path=None, limit=4370): #Je définis une fonction chain( , chaine d'interactions ,la taille de la chaine)
	next_ = nodes.get(path[-1], None)
 
	if next_ is None or len(path) >= limit: #Si la taille dépasse la limite de taille alors on passe a la chaine suivante
		yield path
		setdejavu.clear() #On réinisialise les protéines déjà vues car on passe a une nouvelle chaine
 
	else:
		for m in next_: # next_ est l'ensemble des interactions de path[-1] (donc la deuxième protéine de l'interaction précédente)
			if m not in setdejavu: #Si l'interaction n'est pas dans la liste des interactions déjà utilisées
				setdejavu.add(m) #On ajoute l'interaction imbriquée dans la chaine pour ne pas la reprendre ensuite
				yield from chain(nodes, path + [m]) #On rajoute une autre prot à la chaine
 
 
for k in dd: # Pour chaques prot du dico
	for z in chain(dd, path = [k]): #Pour chaques chaines
		print (' '.join(z),'\n')

L'algorithme fonctionne très bien, cependant j'essaie de trouver la longueur maximale possible de la première chaine.
Pour ce faire, je modifie la valeur "limit" et regarde si l'algorithme arrive a me générer des chaines de la longueur demandée.

Cependant par exemple ici, avec une longueur de 4370 (idem pour d'autres valeurs), quand je lance l'algorithme, parfois l'algorithme me génère des chaines et parfois non (il me sort alors [Finished in 1.6s])…
Je me demande donc pourquoi dans certains cas l'algorithme me trouve des chaines de la longueur voulue et parfois il ne me trouve aucun résultats ?

[wiztricks]

Salut,

Je me demande donc pourquoi dans certains cas l'algorithme me trouve des chaines de la longueur voulue et parfois il ne me trouve aucun résultats ?

Ce que vous montrez c'est juste du code, l'algorithme çà fait plusieurs fois qu'on vous demande de le décrire: on l'attends toujours!

Dommage car le décrire vous aurait permis de fabriquer un jeu de tests avec un minimum de nœuds qui aurait permis de valider que le code réalisait bien l'algorithme attendu et sinon poster de quoi reproduire.

edit: testez votre code avec ce simple graphe et limit=4

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
data = '''1 3
1 2
2 3
2 1
3 1
3 2
'''
 
dd = defaultdict(set)
for z in data.splitlines():
    a, b = z.split(' ')
    dd[a].add(b)

vous devriez sortir:

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
1 3 2 1
1 3 1 3
1 3 1 2
1 2 3 1
1 2 1 3
1 2 1 2
2 3 2 1
2 3 1 3
2 3 1 2
2 1 3 2
2 1 3 1
2 1 2 3
2 1 2 1
3 2 3 1
3 2 1 3
3 2 1 2
3 1 3 2
3 1 3 1
3 1 2 3
3 1 2 1

En gras, quelque transitions qui se répètent joyeusement.
Pas besoin de 2000 nœuds pour "voir" qu'il y a quelque chose qui "cloche".

- W

[Amniote]

Salut,

En gras, quelque transitions qui se répètent joyeusement.
Pas besoin de 2000 nœuds pour "voir" qu'il y a quelque chose qui "cloche".

- W

Bonjour, j'ai cherché ces derniers jours à comprendre d'où pouvait bien venir cette erreur mais vraiment je ne vois pas...

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
 
from collections import defaultdict
dd = defaultdict(set)
setdejavu=set()
 
with open ("C:/Users/lveillat/Desktop/Données stage/Fichiers tests/chaines infinies 5prots.txt","r") as f1:
	for ligne in f1:
		lp = ligne.rstrip('\n').split(" ")
		prot1 = lp[0] #je sélectionne la première protéine de chaques interactions
		prot2 = lp[1] #je sélectionne la seconde protéine de chaques interactions
		dd[prot1].add(prot2) #Je crée mon dictionnaire avec en clé la première prot de l'interaction et en valeurs l'ensembles des prots avec qui elle peut interagir
		#print(dd)
 
def chain(maillon, pathway, limite=4): #Je définis une fonction chain(maillon, chaine d'interaction, limite de taille de la chaine)
	next_ = maillon.get(pathway[-1], None) #next_ = On rajoute un maillon à la chaine existante en fonction de la dernière protéine du pathway
 
	if next_ is None or len(pathway) >= limite : #Si il n'y a pas de protéine trouvée interagissant avec la dernière protéine du pathway, ou si la taille dépasse la limite alors on passe a la chaine suivante
		yield pathway #yield est pratique quand on sait que la fonction va retourner de nombreuses valeurs qu’on ne souhaite lire qu’une seule fois (c'est notre cas ici), permet d'économiser de la mémoire.
		setdejavu.clear() #On réinisialise les protéines déjà vues car on passe a une nouvelle chaine.
 
	else: #Si on trouve encore des protéines interagissant  avec la dernière protéine du pathway et si la taille limite n'est pas atteinte,
		for m in next_: # pour une interaction dans l'ensemble des interactions possibles de pathway[-1]
			if m not in setdejavu:#Si cette interaction n'est pas dans notre liste d'interactions déjà utilisées
				setdejavu.add(m) #alors on ajoute l'interaction imbriquée dans la chaine pour ne pas la reprendre ensuite (sinon créerai des chaines infinies)
				yield from chain(maillon, pathway + [m]) #On rajoute une autre prot à la chaine
 
 
for k in dd: # Pour chaques prot du dico
	for z in chain(dd, pathway = [k]): #Pour chaques chaines
		print (' '.join(z))

Pourtant dans mon algorithme nous avons bien :

Code :

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

1
2
3
4
 
if next_ is None or len(pathway) >= limite : 
   yield pathway 
   setdejavu.clear()

Où je réinitialise la liste des interactions déjà rencontrées afin d'initier une nouvelle chaine sans considérer les protéines déjà rencontrées dans la chaine précédente...
Et où j'affiche mon pathway car il est terminé car mes conditions ne sont plus respectées

et :

Code :

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

1
2
3
4
5
6
 
else: 
    for m in next_: 
        if m not in setdejavu:
            setdejavu.add(m) 
            yield from chain(maillon, pathway + [m])

Où je prends chaques interactions possibles pour pathway[-1] (m)
Si m n'est pas dans setdejavu alors je l'ajoute dans setdejavu et j'ajoute m à mon pathway
et donc si il n'y est pas je ne fais rien...

Pour moi cela me semble logique, je ne vois vraiment pas pourquoi je me retrouve avec des protéines qui apparaissent en double tel que 2 1 2 1 dans votre exemple...

[wiztricks]

Pour moi cela me semble logique, je ne vois vraiment pas pourquoi je me retrouve avec des protéines qui apparaissent en double tel que 2 1 2 1 dans votre exemple...

Pour comprendre, il faut mimer avec patience ce que font les instructions.
Si vous n'avez pas l'habitude de ce genre de code, vous ne pourrez pas le faire "mentalement, il va falloir poser çà sur une feuille de papier avec un crayon.

Et vous organiser un peu car, même si je vous ai trouvé un exemple facile, pour arriver à:

Code :

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

1
2
1 3 2 1
1 3 1 3

rien que la sortie de la première ligne, c'est appeler "chain" 4 fois pour arriver à la feuille, poursuivre le 3ème appel à "chain" suspendu par le 4ème appel, ...

C'est le boulot que tout ceux qui se sont frottés aux fonctions récursives ont du faire pour apprendre et comprendre ce genre de code.

- W

[Amniote]

Bonjour,

Il me semble avoir trouvé la solution, je n'avais pas besoin de faire de liste, il me suffisait de comparer m au reste du pathway

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
 
import sys
sys.setrecursionlimit(1000000)
from collections import defaultdict
dd = defaultdict(set)
 
with open ("C:/Users/lveillat/Desktop/Données stage/Fichiers tests/testchaines3.txt","r") as f1:
	for ligne in f1:
		lp = ligne.rstrip('\n').split(" ")
		prot1 = lp[0] #je sélectionne la première protéine de chaques interactions
		prot2 = lp[1] #je sélectionne la seconde protéine de chaques interactions
		dd[prot1].add(prot2) #Je crée mon dictionnaire avec en clé la première prot de l'interaction et en valeurs l'ensembles des prots avec qui elle peut interagir
	print(dd)
 
def chain(maillon, pathway, limite=4): #Je définis une fonction chain(maillon, chaine d'interaction, limite de taille de la chaine)
	next_ = maillon.get(pathway[-1], None) #next_ = On rajoute un maillon à la chaine existante en fonction de la dernière protéine du pathway
 
	if next_ is None or len(pathway) >= limite : #Si il n'y a pas de protéine trouvée interagissant avec la dernière protéine du pathway, ou si la taille dépasse la limite alors on passe a la chaine suivante
		yield pathway #yield est pratique quand on sait que la fonction va retourner de nombreuses valeurs qu’on ne souhaite lire qu’une seule fois (c'est notre cas ici), permet d'économiser de la mémoire.
 
	else: #Si on trouve encore des protéines interagissant  avec la dernière protéine du pathway et si la taille limite n'est pas atteinte,
		for m in next_: # pour une interaction dans l'ensemble des interactions possibles de pathway[-1]
			#print(m)
			if m not in pathway:
				yield from chain(maillon, pathway + [m]) #On rajoute une autre prot à la chaine uniquement si la protéine que l'on rajoute n'est pas déjà apparue dans la chaine
 
for k in dd: # Pour chaques prot du dico
	for z in chain(dd, pathway = [k]): #Pour chaques chaines
		print (' '.join(z))

Merci encore de votre aide

[Amniote]

Normalement dernier soucis avant la fin de l'algorithme...

J'ai mon fichier test que voici :

1 4
1 6
4 9
6 9
9 33
9 66
4 1
6 1
9 4
9 6
33 9
66 9

mon algorithme :

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
 
import sys
sys.setrecursionlimit(1000000)
from collections import defaultdict
dd = defaultdict(set)
 
with open ("C:/Users/lveillat/Desktop/Données stage/Fichiers tests/testchaines3.txt","r") as f1:
	for ligne in f1:
		lp = ligne.rstrip('\n').split(" ")
		prot1 = lp[0] #je sélectionne la première protéine de chaques interactions
		prot2 = lp[1] #je sélectionne la seconde protéine de chaques interactions
		dd[prot1].add(prot2) #Je crée mon dictionnaire avec en clé la première prot de l'interaction et en valeurs l'ensembles des prots avec qui elle peut interagir
	print(dd)
 
def chain(maillon, pathway, limite=4): #Je définis une fonction chain(maillon, chaine d'interaction, limite de taille de la chaine)
	next_ = maillon.get(pathway[-1], None) #next_ = On rajoute un maillon à la chaine existante en fonction de la dernière protéine du pathway
 
	if next_ is None or len(pathway) >= limite : #Si il n'y a pas de protéine trouvée interagissant avec la dernière protéine du pathway, ou si la taille dépasse la limite alors on passe a la chaine suivante
		yield pathway #yield est pratique quand on sait que la fonction va retourner de nombreuses valeurs qu?on ne souhaite lire qu?une seule fois (c'est notre cas ici), permet d'économiser de la mémoire.
 
	else: #Si on trouve encore des protéines interagissant  avec la dernière protéine du pathway et si la taille limite n'est pas atteinte,
		for m in next_: # pour une interaction dans l'ensemble des interactions possibles de pathway[-1]
			#print(m)
			if m not in pathway:
				yield from chain(maillon, pathway + [m]) #On rajoute une autre prot à la chaine uniquement si la protéine que l'on rajoute n'est pas déjà apparue dans la chaine
 
for k in dd: # Pour chaques prot du dico
	for z in chain(dd, pathway = [k]): #Pour chaques chaines
		print (' '.join(z))

et la sortie de l'algorithme :

defaultdict(<class 'set'>, {'1': {'6', '4'}, '4': {'9', '1'}, '6': {'9', '1'}, '9': {'6', '66', '33', '4'}, '33': {'9'}, '66': {'9'}})
1 6 9 66
1 6 9 33
1 6 9 4
1 4 9 6
1 4 9 66
1 4 9 33
4 9 6 1
4 1 6 9
6 9 4 1
6 1 4 9
9 6 1 4
9 4 1 6
33 9 6 1
33 9 4 1
66 9 6 1
66 9 4 1

Je n'ai plus le problème des répétitions, mais cette fois lorsque mon fichier contient les interactions dans les deux sens ( 1 4 et 4 1) (ce qui est le cas pour le fichier sur lequel je travaille), les interactions intermédiaires ne sont plus affichées !
Il devrait par exemple apparaître 66 9 33... Je comprends pas pourquoi lorsque les interaction sont a double sens dans le fichiers, je ne retrouve plus les interactions intermédiaires...

[wiztricks]

Je comprends pas pourquoi lorsque les interaction sont a double sens dans le fichiers, je ne retrouve plus les interactions intermédiaires...

C'est essentiellement parce que dans un graphe, il y a des nœuds et des arcs (qui relient les nœuds). Dans votre cas, une interaction est représentée par un arc alors que jusqu'à présent vous ne regardez que les nœuds par lesquels on est passé.
Il y a plein de tuto. pour apprendre ce genre de programmation là. Si vous voulez progresser, il faut vous en trouver un et passer du temps à le potasser.

- W

[Amniote]

Bonjour à tous,

Je suis en train de créer un algorithme qui me permettrai de me trouver toutes les chaines d'interactions de taille 4 dans cet arbre en prenant en compte le fait que nous pouvons remonter dans l'arbre (les interactions sont à double sens) (et on ne peut pas retrouver deux fois le même chiffre dans une chaîne).

Code :

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

1
2
3
4
5
6
7
8
9
10
11
 
                                 1
                                -  -
                               -     -
                             6       4
                              -        -
                                 -      -
                                     -   9
                                        -   -
                                       -     -
                                     33       66

J'ai réussi a générer les chaines de tailles 4 (voici ce que me trouve actuellement mon algorithme)

1 6 9 66
1 6 9 4
1 6 9 33
1 4 9 6
1 4 9 66
1 4 9 33
4 1 6 9
4 9 6 1
6 1 4 9
6 9 4 1
9 6 1 4
9 4 1 6
33 9 6 1
33 9 4 1
66 9 6 1
66 9 4 1

Cependant il me faudrait aussi les "chaines intermédiaires", c'est a dire les chaines qui sont "bloquées" avant d'atteindre la taille de 4, par exemple :

4-9-33
6-9-33
9-33
9-66
66-9-33
33-9-66
6-9-66
ect...

ça ne doit pas être grand chose à modifier/rajouter, j'ai fait des recherches sur de potentielles fonctions (intertools notamment) permettant cela mais je ne trouve rien qui résolve mon problème...

Voici le fichier sur lequel je travaille:

1 4
1 6
4 9
6 9
9 33
9 66
4 1
6 1
9 4
9 6
33 9
66 9

Voici mon algorithme actuel (je travaille sur des protéines, représentées ici par les chiffres):

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
 
import sys
sys.setrecursionlimit(1000000)
from collections import defaultdict
dd = defaultdict(set)
 
with open ("C:/Users/lveillat/Desktop/Données stage/Fichiers tests/testchaines3.txt","r") as f1:
	for ligne in f1:
		lp = ligne.rstrip('\n').split(" ")
		prot1 = lp[0] #je sélectionne la première protéine de chaques interactions
		prot2 = lp[1] #je sélectionne la seconde protéine de chaques interactions
		dd[prot1].add(prot2) #Je crée mon dictionnaire avec en clé la première prot de l'interaction et en valeurs l'ensembles des prots avec qui elle peut interagir
	print(dd)
 
def chain(maillon, pathway, limite=4): #Je définis une fonction chain(maillon, chaine d'interaction, limite de taille de la chaine)
	next_ = maillon.get(pathway[-1], None) #next_ = On rajoute un maillon à la chaine existante en fonction de la dernière protéine du pathway
 
	if next_ is None or len(pathway) >= limite : #Si il n'y a pas de protéine trouvée interagissant avec la dernière protéine du pathway, ou si la taille dépasse la limite alors on passe a la chaine suivante
		yield pathway #yield est pratique quand on sait que la fonction va retourner de nombreuses valeurs qu?on ne souhaite lire qu?une seule fois (c'est notre cas ici), permet d'économiser de la mémoire.
 
	else: #Si on trouve encore des protéines interagissant  avec la dernière protéine du pathway et si la taille limite n'est pas atteinte,
		for m in next_: # pour une interaction dans l'ensemble des interactions possibles de pathway[-1]
			if m not in pathway:
				yield from chain(maillon, pathway + [m]) #On rajoute une autre prot à la chaine uniquement si la protéine que l'on rajoute n'est pas déjà apparue dans la chaine
 
for k in dd: # Pour chaques prot du dico
	for z in chain(dd, pathway = [k]): #Pour chaques chaines
		print (' '.join(z))

et voici ma sortie actuelle :

defaultdict(<class 'set'>, {'1': {'6', '4'}, '4': {'1', '9'}, '6': {'1', '9'}, '9': {'6', '66', '4', '33'}, '33': {'9'}, '66': {'9'}})
1 6 9 66
1 6 9 4
1 6 9 33
1 4 9 6
1 4 9 66
1 4 9 33
4 1 6 9
4 9 6 1
6 1 4 9
6 9 4 1
9 6 1 4
9 4 1 6
33 9 6 1
33 9 4 1
66 9 6 1
66 9 4 1

Merci de votre aide

[wiztricks]

Salut,

Cependant il me faudrait aussi les "chaines intermédiaires", c'est a dire les chaines qui sont "bloquées" avant d'atteindre la taille de 4, par exemple :

4-9-33
6-9-33
9-33
9-66
66-9-33
33-9-66
6-9-66
ect...

Ces chaînes là ne sont pas bloquées, elles commencent par... et ont une longueur inférieure aux conditions que vous avez fixé: il suffit de changer ces conditions.
Ce que vous avez déjà dans les versions d'algo. qui vous ont déjà été proposées au début de cette longue discussion notamment par VinsS.

- W

[Amniote]

Salut,

Ces chaînes là ne sont pas bloquées, elles commencent par... et ont une longueur inférieure aux conditions que vous avez fixé: il suffit de changer ces conditions.
Ce que vous avez déjà dans les versions d'algo. qui vous ont déjà été proposées au début de cette longue discussion notamment par VinsS.

- W

Etes vous sur qu'elles ne sont pas bloquées ? Si je prends 4-9-33 et que je ne l'autorise pas à reprendre un chiffre déjà utilisé, alors elle doit bien s'arréter là non ?

Je cherche depuis hier une solution et je ne trouve toujours pas

Je suis sur cette idée actuellement (ligne 21 à 26) mais je ne sais pas du tout si je vais dans la bonne direction...

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
 
import sys
sys.setrecursionlimit(1000000)
from collections import defaultdict
dd = defaultdict(set)
 
with open ("C:/Users/lveillat/Desktop/Données stage/Fichiers tests/testchaines3.txt","r") as f1:
	for ligne in f1:
		lp = ligne.rstrip('\n').split(" ")
		prot1 = lp[0] #je sélectionne la première protéine de chaques interactions
		prot2 = lp[1] #je sélectionne la seconde protéine de chaques interactions
		dd[prot1].add(prot2) #Je crée mon dictionnaire avec en clé la première prot de l'interaction et en valeurs l'ensembles des prots avec qui elle peut interagir
	print(dd)
 
def chain(maillon, pathway, limite=4): #Je définis une fonction chain(maillon, chaine d'interaction, limite de taille de la chaine)
	next_ = maillon.get(pathway[-1], None) #next_ = On rajoute un maillon à la chaine existante en fonction de la dernière protéine du pathway
 
	if next_ is None or len(pathway) >= limite : #Si il n'y a pas de protéine trouvée interagissant avec la dernière protéine du pathway, ou si la taille dépasse la limite alors on passe a la chaine suivante
		yield pathway #yield est pratique quand on sait que la fonction va retourner de nombreuses valeurs qu?on ne souhaite lire qu?une seule fois (c'est notre cas ici), permet d'économiser de la mémoire.
 
	if len(pathway) < limite  : #Si on trouve encore des protéines interagissant  avec la dernière protéine du pathway et si la taille limite n'est pas atteinte,
		for m in next_: # pour une interaction dans l'ensemble des interactions possibles de pathway[-1]
			if m not in pathway:
				yield from chain(maillon, pathway + [m]) #On rajoute une autre prot à la chaine uniquement si la protéine que l'on rajoute n'est pas déjà apparue dans la chaine
			Si m apparait déja dans le pathway[-1] et que les autres 'm' ont déjà été utilisés alors: 
				yield pathway
 
for k in dd: # Pour chaques prot du dico
	for z in chain(dd, pathway = [k]): #Pour chaques chaines
		print (' '.join(z))

[wiztricks]

Etes vous sur qu'elles ne sont pas bloquées ? Si je prends 4-9-33 et que je ne l'autorise pas à reprendre un chiffre déjà utilisé, alors elle doit bien s'arréter là non ?

Ça n'en fait rien car 33 est connecté à 9.
Donc ligne 18, next_ n'est pas vide et la longueur de 4-9-33 est inférieure à 4...
Et donc on continue pour arriver ligne 23 où 9 étant déjà dans le chemin...

Si tout cela n'est pas logique pour vous, çà se comprends très bien: c'est de la programmation difficile et pas très intuitive: soit vous prenez le temps d'apprendre, soit vous continuez à patauger et avoir mal au crane.


- W

[Amniote]

Bonjour à tous,

J'avais réussi à terminer ce fameux code, il faut maintenant que j'y apporte quelques modifications:

je dois maintenant demander deux protéines (chiffres) à l'utilisateur. Le premier chiffre rentré sera la protéine qui initiera la chaîne, le second chiffre sera la protéine qui terminera la chaîne. Ensuite l'algorithme doit me trouver tout les chemins possibles reliant ces deux protéines.

Pour l'instant je pense ne pas m'en sortir trop mal

voici le fichier test que j'utilise:

1 4
4 1
1 6
6 1
1 66
66 1
4 9
9 4
6 9
6 66
66 6
9 6
9 33
33 9
9 66
66 9

et le code:

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
 
import sys
sys.setrecursionlimit(1000)
from collections import defaultdict
dd = defaultdict(set)
 
with open("testchaines3.txt","r") as f1:
	for lignes in f1:
		lignes=lignes.rstrip('\n').split(" ")
		prot1=lignes[0]
		prot2=lignes[1]
		dd[prot1].add(prot2)
	#print(dd)
 
proteine1 = (input("Enter the first protein in the chain : "))
proteine2 = (input("Enter the last protein in the chain : "))
 
def chain(proteine1, proteine2, maillon, pathway, limite=10): 
	next_= maillon.get(pathway[-1], None) 
	if len(pathway)<limite:
		for m in next_:
			if m not in pathway:
				if m==proteine2 and pathway[0]==proteine1:
					pathway.append(m)
					yield pathway
				if m != proteine2:
					yield from chain(proteine1, proteine2, maillon, pathway + [m])
					pass
 
for k in dd: 
	for z in chain(proteine1,proteine2, dd, pathway = [k]):
		print (' '.join(z))

Cependant j'ai un petit soucis, lorsque je print le résultat, je ne vais jamais avoir les combinaisons qui apparaissent, soit je les ais toutes, soit il m'en manque une partie!

par exemple pour protéine1 = 1 et protéine2 = 6 :

Un coup je vais avoir cela :

Enter the first protein in the chain : 1
Enter the last protein in the chain : 6
1 66 9 6
1 66 6
1 6

un autre coup cela :

Enter the first protein in the chain : 1
Enter the last protein in the chain : 6
1 6

ou encore cela (qui est la réponse attendue):

Enter the first protein in the chain : 1
Enter the last protein in the chain : 6
1 66 9 6
1 66 6
1 4 9 66 6
1 4 9 6
1 6

je ne comprends pas d'où viens ce problème...

Merci de votre aide

[wiztricks]

Salut,

je ne comprends pas d'où viens ce problème...

Si vous affichez dd, vous devriez constater que d'une exécution à l'autre les ensembles de protéines ne sont pas rangées dans le même ordre.
Et suspecter que si le parcours de votre graphe (et ce que çà affiche en sortie) dépend de cet ordre là... c'est qu'il y a encore du boulot pour le mettre au point.


- W

[Amniote]

Salut,

Si vous affichez dd, vous devriez constater que d'une exécution à l'autre les ensembles de protéines ne sont pas rangées dans le même ordre.
Et suspecter que si le parcours de votre graphe (et ce que çà affiche en sortie) dépend de cet ordre là... c'est qu'il y a encore du boulot pour le mettre au point.

- W

Certes, l'ordre des protéines changent dans le dictionnaire, mais cela ne modifie pas le parcours du graphe ? les chemins restent bien les mêmes ? je ne vois pas en quoi cela bloque l'algorithme...