Discussion :

[noscollections]

Bonjour,

Voici le contexte :
J'ai une liste qui ressemble à cela : init_list=['C..','C..','D..','Gd.','Gd.','Gd.','Gd.','END']
Chaque élément de cette liste représente une référence de rail de circuit de voiture électrique (je ne citerai pas de marque)
Objectif : trouver toutes les combinaisons de circuits possibles avec les rails
Ensuite chaque combinaison est testée pour vérifier que le circuit est bien bouclé (360°) plus quelques autres paramètres comme longueur max ou mini du circuit. Mais cette partie fonctionne bien.

Comme indiqué dans le titre, le problème vient de l'arrangement de ma liste d'origine.

Jusqu'à 10-11 valeurs dans cette liste tout va bien, mais après, je ma machine fige.

Pour faire mon arrangement je me suis basé sur les liens suivant :

http://www.developpez.net/forums/d11...sible-d-liste/

http://www.developpez.net/forums/d96...eau-n-entrees/

Que ce soit avec le code de message 1 avec list(permutations([1,2,3])) ou avec la fonction du second message., j'ai le même problème au dela de 11 paramètres il n'y a plus de réponse, cela sature.
J'aimerai pouvoir gérer dans les 40 ou 50 paramètres

Dans mon cas avec ['C..','C..','D..','Gd.','Gd.','Gd.','Gd.','END']
mon arrangement donne 3 628 800 possibilités
ensuite je filtre pour supprimer les doublons list_track=list(set(list_track))

j'arrive avec 15120 possibilités

je lance mon traitement pour vérifier que le circuit fait un boucle (360°)
Gd. = 90° donc ['C..','C..','D..','Gd.','Gd.','Gd.','Gd.','END'] -> 4*90° = 360°
par contre je m'arrète au END donc ['C..','C..','D..','Gd.','Gd.','END','Gd.','Gd.'] = 2x90=180 °

il me reste 2880 possibilités et maintenant ma liste ressemble a ceci :
['C..C..D..Gd.Gd.'],['C..D..C..Gd.Gd.'],['C..C..D..Gd.Gd.']
je refiltre ma_track=list(set(ma_track))
il me reste 2267 possibilités que je test tranquillement avec une fonction

Pour le temps de calcule je peu être patient, auriez vous quelques conseils ou techniques pour repousser ma limite de 11-12 paramètres

La fonction permutations dois me donner trop de valeurs et je sature la mémoire.

Vous remerciant pour vos futurs conseils

Bien cordialement,

[wiztricks]

Salut,

J'ai une liste qui ressemble à cela : init_list=['C..','C..','D..','Gd.','Gd.','Gd.','Gd.','END']
Chaque élément de cette liste représente une référence de rail de circuit de voiture électrique (je ne citerai pas de marque)
Objectif : trouver toutes les combinaisons de circuits possibles avec les rails

Si vous avez des doublons, c'est que vos éléments ne sont pas distincts.
Et le gros soucis c'est que pour les trier, il va falloir garder toutes les combinaisons en mémoire. Et comme leur nombre est factorielle(n), çà explose assez vite.

Je dirais que ces doublons traduisent un problème mal posé.

Pourquoi ne pas partir d'une quantité d'éléments semblables: 2 x 'C..', 1 x 'D..', 4 x 'Gd.' à partir desquels on va construire toutes les séquences de longueur <= 7.
Ce qui en ajoutant 1 x END équivaut à construire toutes les séquences de longueur 8 dont on ne garde que la partie jusqu'à 'END'.

Est ce que ma reformulation du problème vous semble correcte?

- W

[picodev]

Bonjour,

Dans mon cas avec ['C..','C..','D..','Gd.','Gd.','Gd.','Gd.','END']
mon arrangement donne 3 628 800 possibilités
...

Là tu as un gros problème de compréhension … avec un multiensemble du genre {C,C,D,G,G,G,G} tu n'as que 350 permutations de longueur 0 à 7 possibles … tu en 10000 fois de trop !

Si tu es à l'aise en algo je ne peux que te conseiller d'essayer l'algo L de Knuth publié dans fascicule 2b Generating All Permutations.

Garde cependant à l'esprit que l'espace que tu vas parcourir peut exploser de façon combinatoire … avec 10 éléments tous distincts tu arrives à 4.037.914 possibilités, 43.954.714 pour 11, 522.956.314 pour 12, …, 128.425.485.935.180.314 pour 20. Pour te donner un autre ordre de grandeur, si ton multiensemble contient 5 éléments distincts chacun en 4 exemplaires tu as 904.434.761.801 possibilités.

Tu peux essayer dans certains cas d'élaguer ta recherche en utilisant l'algo L, mais bon.

[noscollections]

Je suis parti sur le premier script simple et fait au mieux pour mon besoin mais ce n'est pas propre.

Je l'ajoute un paramètre donc des millions de résultat dans le seul objectif de simuler des résultats de 1 à X valeurs car je ne prend pas en compte à partir du End.

Déjà je pense que prendre un script qui génère les résultats de 1 à X serait une bonne idée. Et plutôt que de tout enregistrer dans une liste, et ensuite traiter la liste pour vérifier la validité d'un circuit, je devrais vérifier dès qu'une combinaison est générer et ainsi stocker dans ma liste les valides.

Ensuite j'ai mon problème de doublons.
Ayant plusieurs fois la même valeur de paramètres mon arrangement lui voit plusieurs 'id' et mélange
A, A donne A, A et A, A
La il faut que je cherche un meilleur script.

Le problème vient peut être aussi de ma liste de départ .
Pour la faire j'ai ceci:
Track_C=2
Track_G=4
...
Malist=['C..']*Track_C+['G..']*Track_G

Et encore normalement si je dit 4 G. C'est faux car un rail courbe suivant qu'on le positionne d'un coté ou de l'autre, c'est un virage à droite ou à gauche
Donc pour un G je n'ai pas G.. mais Gd. Ou Gg. Pour cela je me général autant de liste de départ que de combinaisons Gg / Gd et j'additionnai les résultats.

Pour alléger le nombre de paramètre au lieu de mettre 'C..','C..','C..','C..','C..','C..',, je met 'C..','C..','C..C..C..C..' j'impose une série de 4 rail droite pour imposer une belle ligne droite, cela réduit les paramètres.

Mais l'idée est de pouvoir augmenter les paramètres sachant qu'il y a déjà 20 rails différents par la qt de chaque que l'on peut utiliser, ça fait beaucoup!

Pour le pdf indiqué je ne maîtrise pas l'algo

wiztricks, tu as très bien posé le problème et cerné mon besoin.

A la lecture de vos remarques, je vais essayer de ne pas stocker l'ensemble des résultats dans une liste (qui serait trop grosse) mais de récupérer les résultats un par un pour les traiter et ne garder que ceux qui sont valident j'aurai ainsi une liste plus petite

[wiztricks]

Salut,

A la lecture de vos remarques, je vais essayer de ne pas stocker l'ensemble des résultats dans une liste (qui serait trop grosse) mais de récupérer les résultats un par un pour les traiter et ne garder que ceux qui sont valident j'aurai ainsi une liste plus petite

En faisant cela, vous évitez les dépassements de mémoire... mais vous ne traitez pas la combinatoire i.e. le temps mis pour fabriquer des solutions qui devront être validées avant d'être probablement jetées.
Et pour réduire la combinatoire, il faut limiter le nombre de solutions à valider en essayant de mettre au point un algo. qui sera un peu plus intelligent.
Par exemple pour fermer votre circuit, il faudra que la différence entre les Gd et les Gg soit de 4. De plus, pour un circuit tel que Gd = Gg + 4 va exister un circuit symétrique tel que Gd + 4 = Gg. Si vous avez 4 x Gd, vous ne pourrez faire que des circuits "rectangulaires"...
Donc il est possible de réduire la complexité combinatoire et si des algorithmes existent, il serait bon d'aller voir si quelqu'un a des idées dans la rubrique/forum ad hoc.

- W

[noscollections]

Salut,

Et pour réduire la combinatoire, il faut limiter le nombre de solutions à valider en essayant de mettre au point un algo. qui sera un peu plus intelligent.
Par exemple pour fermer votre circuit, il faudra que la différence entre les Gd et les Gg soit de 4. De plus, pour un circuit tel que Gd = Gg + 4 va exister un circuit symétrique tel que Gd + 4 = Gg. Si vous avez 4 x Gd, vous ne pourrez faire que des circuits "rectangulaires"...
Donc il est possible de réduire la complexité combinatoire et si des algorithmes existent, il serait bon d'aller voir si quelqu'un a des idées dans la rubrique/forum ad hoc.

- W

Pour la boucle, je compte les Gd (virages a droite) les Gg (virages à gauche) nb_Gd*90+nb_Gg*-90= boucle, si c'est un multiple de 360 c'est que c'est une boucle fermée.

Je vais jeter un coup d’œil au lien indiqué

Merci, toutes les pistes sont bonnes à prendre

[noscollections]

Bonjour,

Je suis partie du script trouvé sur un autre message du forum

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
# -*- coding: cp1252 -*-
 
# générer les injections de {1,2,..,p} dans E représenté comme liste
def GenInj(p,E):
    if p==1:
        return [[x] for x in E] #cas où p=1
    else:
        R=[]
        for x in E:
            F=E[:] # recopier E
            F.remove(x) # enlever x
            PGI=GenInj(p-1,F) # appel récursif
            Cx=PGI[:] # recopie du résultat
            for A in Cx:
                A.append(x)# recombiner avec x tous les éléments
            R+=Cx # Ajouter les résultats obtenus
    return R
 
def main():
    E=['a','b','c']
    R=[]
    for i in range(len(E)+1):
        R+=GenInj(i,E)
    print len(R)
    print R
 
 
if __name__ == '__main__':
    main()

Le script fait le JOB dans la configuration que j'étais au début, on récupère les résultats dans une liste.

Après plusieurs essais a taton

J'ai modifié le script pour envoyer chaque résultat vers ma fonction analyse qui pour le moment se contente d'afficher chaque résultat.

Cela fait le JOB mais j'ai du doublon par rapport au résultat dans la liste
exemple liste = 1956
moi ma fonction est sollicité 8550 fois, ce qui veut dire que je vais tester la validité de certains résultats plusieurs fois

J'ai pensé passer par un enregistrement des valeurs dans sqlite pour détecter les doublons, je reporte mon problème de mémoire sur le disque (et a mon avis les temps d'accès vont pas être a mon avantage ! Du coup vérifier plusieurs un résultat pour rien n'est peut être pas si mal !

De plus en mémoire je doit avoir une variable intermédiaire qui gonfle car en mémoire windows le script monte à plus de 11Giga

Sinon pour 11 paramètres le temps d’exécution est de 610 secondes ( sans filtrage, juste pour donner a la fonction analyse toutes les valeurs et générer le compteur de passage dans la fonction.

pour 10 paramètres : c'est 45 secondes

le coté temps ne m'embete pas si je doit laisser un Script tourner plusieurs jours pas de problème, mais le coté mémoire toujours présent m’embête un peu plus

Voici 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
33
34
35
36
37
38
39
40
 
qt=0
 
def analyse(data):
    global qt
    print (data)
    qt=qt+1
 
 
def GenInj(p,E):
    if p==1:
        if len(E)==1:
            analyse (E)
        return [[x] for x in E] #cas où p=1
    else:
        R=[]
        for x in E:
            F=E[:] # recopier E
            F.remove(x) # enlever x
            PGI=GenInj(p-1,F) # appel récursif
            Cx=PGI[:] # recopie du résultat
            for A in Cx:
                A.append(x)# recombiner avec x tous les éléments
                analyse (A)
            R+=Cx # Ajouter les résultats obtenus
    return R
 
def main(E):
    R=[]
    for i in range(len(E)+1):
        TRF=GenInj(i,E)
        ##print (str(TRF))
        R+=TRF # a mettre en remarque pour ne pas charger mémoire
    # affiche le nombre de résultats trouvé
    print()
    print (str(len(R)))
 
E=['a','b','c','d','e','f']
main(E)
print (qt)

Il va falloir que je trouve une meilleur programmation si cela est possible. Hélas j'ai peur que mes capacités en programmation ne soient pas a la hauteur.

Mais qui n’essaie rien, n'aura rien !