Trouver toutes les combinaisons d'apres un tableau et un algorithme

**frederic89** · 25/08/2016, 12h09

Bonjour à tous,
Bon voila, j'arrive à me débrouiller avec les fonctions de EXCEl mais j'ai un cas insolvable par des fonctions classiques d'excel et c'est pour cela que je cherche à savoir si cela est possible par l’intermédiaire du VBA.
Mon cas est compliqué à expliquer donc j'ai préférer faire un fichier excel sur lequel je mets mes attentes. Je ne sais pas si cela est réalisable mais je l’espère car c'est impossible de le faire sans automatisation....
Bon, je vous laisse regarder ma PJ en croissant les doigts.
MErci d'avance,
Salutations,

**Jean-Philippe André** · 25/08/2016, 12h32

Salut,

je me desole de me dire que ton fichier m'a plus embrouille qu'apporter des reponses

Ce que je crois avoir compris :
- tu as une serie de 7 lettres (B G M N O R V J)

- tu as un tableau avec une lettre de depart / une lettre de fin

Combinaion Zone Gauche Zone droite
B G B G
B N B N
B N B N
G N G N
G N G N
G O G O
G V G V
M B M B
M G M G
M N M N
M J M J
N V N V
O N O N
O V O V
R B R B
R G R G
R N R N
R N R N
R O R O
R V R V
R V R V
V B V B
V N V N
J B J B
J G J G
J N J N

- tu cherches a faire un chemin en partant de chaque lettre
- lorsque tu reviens a ton point de depart tu arretes ton processus, idem si tu repasses 2 fois par un point intermediaire

Par contre la notion de mot recherche, la je suis perdu

Quel est ton objectif ?

**eriiic** · 25/08/2016, 15h37

Bonjour,

Concretement pour la lettre B...

Je n'ai pas compris la règle qui faisait que tu omets M puis O,R sur la 1ère ligne.

Ceci dit l'algorithme de Myrna Larson t'intéressera peut-être : https://groups.google.com/d/msg/micr...8/PMhSJOnuUCEJ
eric

**frederic89** · 25/08/2016, 15h50

De quelle premiere ligne me parles tu?
Salutaitions :

Pour infi une autre explication :

Bonjour,
Mon explication n'est si simple à comprendre alors quelques explications complémentaires.
J'ai 8 lettres (mais dans les faits ceux sont des mots)
B
G
M
N
O
R
V
J

ces 8 lettres forment des combinaisons (Colonne A)
En colonne B j'ai la valeur Gauche de cette combinaison et en colonne C j'ai la valeur droite de cette combinaison

Si je prends pour exemple la lettre B, celle si est associé à la lettre G puis à la lettre N puis encore à la lettre N
j'arrive au 'Mot' (je ne savait pas comment l'intitulé) BG puis BN puis BN
Je repart de mot mot BG (le premier pour l'explication mais il faut tous les faire) pour lequel la lettre G est associé aux lettres N N O P
j'arrive au mot BGN
la lettre N est associé à la lettre V ce qui me donne le mot BGNV
La lettre V est associé aux lettre B N ce qui me donne le mot BGNVB a ce niveau j'ai un doublon donc je retire la derniere lettre ce qui me donne BGNV. par trop perdu????
Et enfin la valeu que je souhaite mettre dans mon fameux tableau est la premiere lettre et la derniere lettre de ce fameux mot BGNV soit BV.
Cela peu sembler quand on le fait pour une lettre et un seul niveau mais pour toutes les lettres et tous les niveaux cela est impossible.
Merci d'avance pour votre contribution.
Salutations,

**Theze** · 25/08/2016, 15h59

Bonjour,

Si je prends pour exemple la lettre B, celle si est associé à la lettre G puis à la lettre N puis encore à la lettre N

tu veux dire "Si je prends pour exemple la lettre B, celle si est associé à la lettre G puis à la lettre M puis encore à la lettre N" je suppose

Et donc, BG puis BM puis BN
Ensuite tu dis :

Je repart de mot mot BG (le premier pour l'explication mais il faut tous les faire) pour lequel la lettre G est associé aux lettres N N O P

B
G
M
N
O
R
V
J

Mais où est le P dans ta liste ?

**frederic89** · 25/08/2016, 16h38

Bonjour THEZE
Dans le tableau je regarde la lettre B dans la colonne B puis je regarde les lettres correspondantes dans la colonne C donc B est associé à G puis N puis de nouveau N.
SAlutations et merci.

Désolé j'ai fait une erreur il sagit de la lettre V et non P.
Salutations,

@jpcheck

Bonjour,
Mon explication qui n'est si simple à comprendre.
Pour le début tu as tout compris.
J'ai 8 lettres (mais dans les faits ceux sont des mots)
B
G
M
N
O
R
V
J

ces 8 lettres forment des combinaisons (Colonne A)
En colonne B j'ai la valeur Gauche de cette combinaison et en colonne C j'ai la valeur droite de cette combinaison

Si je prends pour exemple la lettre B, celle si est associé à la lettre G puis à la lettre N puis encore à la lettre N
j'arrive au 'Mot' (je ne savait pas comment l'intitulé) BG puis BN puis BN
Je repart de mot mot BG (le premier pour l'explication mais il faut tous les faire) pour lequel la lettre G est associé aux lettres N N O P
j'arrive au mot BGN
la lettre N est associé à la lettre V ce qui me donne le mot BGNV
La lettre V est associé aux lettre B N ce qui me donne le mot BGNVB a ce niveau j'ai un doublon donc je retire la derniere lettre ce qui me donne BGNV. par trop perdu????
Et enfin la valeu que je souhaite mettre dans mon fameux tableau est la premiere lettre et la derniere lettre de ce fameux mot BGNV soit BV.
Cela peu sembler quand on le fait pour une lettre et un seul niveau mais pour toutes les lettres et tous les niveaux cela est impossible.
Merci d'avance pour ta contribution.
Salutations,

**eriiic** · 25/08/2016, 16h45

Concrètement, en F39 pourquoi BN et non BM ?
Ou bien pourquoi en G29 BGN et non BGM ?
etc...

**frederic89** · 25/08/2016, 17h14

pour F39:
Ma lettre de départ reste le B, donc je cherche les B dans la colonne "B" de mon tableau et je prends les lettre correspondante de la colonne "C" soit : G N N.
pout G29
Je cherche la lettre N dans la colonne "B" (la lettre N résulte d'un recherche précédente) de mon tableau et je prends les lettres correspondantes de la colonne C soit : V

Suis je plus clair?
Merci
@+

**eriiic** · 25/08/2016, 19h59

Désolé mais je ne capte pas.
Soit tu fournis B:C déjà rempli, à ce moment là pourquoi répéter BN B N, GN G N ? Donc ça ne doit pas être ça...
Soit il faut construire B:C au fur et à mesure à partir de (B G M N O R V J), à ce moment là pourquoi N en C2 et non pas M qui suit G ?

edit: en relisant le post 4 et en agrandissant la textbox qui masquait la fin de l'explication (doublons) je pense avoir compris...

**patricktoulon** · 25/08/2016, 22h03

Bonsoir a tous
j'avais fait pour un autre membre un générateurs de mot de passe qui utilisait un algo tres simple pour ne pas avoir de doublons

je l'ai retrouver et j'en ai retirer la méthode

voici un exemple qui te donne les combinaisons possibles sans doublons et normalement sans lettres en double par rapport a une chaine
j'ai testé avec removeduplicate après je n'ai vraiment pas de doublons

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
Sub test()
    Dim nbpuissance, chaine As String, fin As Long, finL As Long, L As String, dico As Object
    strLettres = Split("a,b,c,d,e,f,g", ",")
    Set dico = CreateObject("Scripting.Dictionary")
    Set dicol = CreateObject("Scripting.Dictionary")
    nbpuissance = UBound(strLettres) * UBound(strLettres)
    fin = 0
     Randomize
        Do
       chaine = ""
        finL = 0
        Do
           DoEvents
            L = strLettres(Rnd * 6)
            If Not dicol.exists(L) Then
                dicol(L) = "": finL = finL + 1: chaine = chaine & L
            End If
        Loop Until finL = 7
        If Not dico.exists(chaine) Then
            dico(chaine) = chaine: fin = 0
        Else
            fin = fin + 1
        End If
        dicol.RemoveAll
    Loop Until fin = nbpuissance
    Cells(1, 1).Resize(dico.Count, 1) = Application.Transpose(dico.items())
End Sub

si il faut le commenter y a qu'a demander

**frederic89** · 26/08/2016, 15h38

Bonjour Eriiic
Merci de la collaboration surtout sur pour quelque chose qui n'a rien de simple à comprendre. J'ai fait un schéma (que j’espère plus simple).
Je te laisse le regarder en espérant qu'il t'inspire...
Salutation et merci

Bonjour patrick
J'ai fait un schéma plus simple pour bien comprendre mon besoin (pas simple je l'avoue)
Je te laisse regarder
Merci
SAlutations

Bonjour THEZE
J'ai fait un schéma plus simple pour expliquer mon besoin. J'espere que celui ci te permettra de comprendre.
Merci d'avance,
Salutations,

**eriiic** · 26/08/2016, 16h17

Sans garantie car ça demande du temps pourrais-tu préciser ces points :

1) jamais plus de 6 niveaux ou il vaut mieux prévoir une extension facile ?

2) sur chaque exemple la fin est sur doublon.
Que faire si pas de doublon au 6ème niveau ? (par exemple colonne C non conforme et plus de 6 lettres)
Même si c'est sensé ne jamais arriver il faut une réponse, ne serait-ce que arrêter et alerter...

3) Dans les réponses (ex BN, BV, BV BV, ...) faut-il toutes les réponses ou éliminer les doublons ?

**frederic89** · 26/08/2016, 17h03

Re bonjour
1)Concernant le nombre de niveau, il est malheureusement pas limité à 6 et je ne sais pas jusqu'a combien il peux aller ( j'ai une workstation HP 64 bits avec un très bon processeur et 8 Go de RAM donc mon ordi devrait tenir). Donc idéalement (j en demande certainement beaucoup ) il faudrait que le système puisse "scruter" l'ensemble des combinaisons possible et s'arreter....

2) Je pense que cela peut arriver et ce quelque soit le niveau, donc idéalement ce serait de passer au suivant et indiquer cette impossibilité)

3) Il faut garder les doublons car j'ai besoin par la suite de connaitre le nombre de chaque 'combinaison'

Mon objectif est une gestion de couleur de peinture (ou autre support) avec un nuancier et faire des sondage auprès des utilisateurs sur leurs préférences (multi criteres) et d'en ressortir des tendances. (en gros voir les associations de couleur dans une même pièce donc il peut y avoir une multitude de couleurs...)

Merci d'avance pour ta collaboration.
@+

**eriiic** · 27/08/2016, 12h16

Bonjour,

une proposition.
Pas eu le courage de fignoler, le débogage m'a demandé du temps.
- pas de redimensionnement auto du tableau résult. 1000, à ajuster.
- restitution sur 2 colonnes des résultats. Une chaine unique me paraissait mal adaptée, tu sauras sans doute le faire à ton besoin exact quand ça sera testé plus largement.
- pas de contrôle poussé pour éviter les blocages dus à des tableaux non conformes. Tout passe sur cet exemple, on verra sur tes tests s'il y a des cas à traiter (ex : pas de doublons trouvé, si tu pouvais construire un tableau avec ce cas).
- j'ai laissé les lignes qui m'ont servi au débogage. Les activer avec les 2 variables b_debug si tu veux contrôler le fonctionnement.
eric

**eriiic** · 27/08/2016, 19h11

Re,

version avec des contrôles ajoutés.
eric

Invité · 28/08/2016, 14h37

bonjour,
Algorithme de Dijkstra: permet d’établir le chemin le pus court entre 2 points, mais il faut bien établir avant toutes les combinaisons possible, évacuer les impossibilité et calculer la distance la plus courte!

dans ton cas on s'arrête à l'évaluation de toutes les possibilités.

ou car je n'est pas tous lu le chemin le plus long!

https://fr.wikipedia.org/wiki/Algorithme_de_Dijkstra

**eriiic** · 28/08/2016, 15h37

Bonjour,

en l'occurence je pense que c'est plus un algorithme de parcours d'arbre qu'il faut, il faut parcourir tous les chemins (ce que j'ai fait).
Plus simples, la notion de distance minimale ne sert pas ici.
eric

**unparia** · 28/08/2016, 15h40

Bonjour
J' "adore" cette discussion sur je ne sais quoi, n'ayant pas ouvert (je ne le fais jamais) un classeur tiers sans lequel on ne saurait de quoi il peut s'agir et qui, de plus, est susceptible de disparaître un jour (pour "faire le ménage").
Je continue toutefois à la suivre, espérant que quelqu'un saura à un moment ou l'autre exposer de manière précise, complète, claire et technique les tenants et aboutissants. Sera-ce le demandeur lui-même ? Ou sera-ce l'un des autres intervenants ?

Invité · 28/08/2016, 16h15

Bonjour eriiic,
Ne m'en veux pas si j'ai envoyé une fléchette au petit bonheur la chance car toi au moins tu as trouvé le centre de la cible!

Et comme je l'ai dit je n'ai pas tous lu et pas vraiment compris ce que j'ai lu.

Je théorisai sur la possibilité de trouver toutes le combinaison et c'est ce que fait cet algorithme.

**eriiic** · 28/08/2016, 18h14

Ca c'est le demandeur qui dira si j'ai bien compris parce que j'ai eu du mal ;-)
Je suis peut-être à coté de la plaque. Ou bien il manque des branches, les contrôles sont particulièrement ch...
Et je ne peux pas t'en vouloir d'ouvrir des pistes, tu as donné de la lecture intéressante.
Je ne me suis posé la question de l'algorithme qu'après avoir fait, et suite à ta proposition qui m'a poussé à la réflexion. Après ce constat il y a sûrement plus direct et plus efficace que ce que j'ai fait à l'instinct, au fil de l'eau.

Un essai de traduction de ce que j'ai compris. On a une liste de chemins possibles :
A -> B
A -> B
A -> C
B -> D
D -> B
On établit les arbres (racines: A, A, B, D) de tous les chemins possibles (d'où un problème d'élagage avec l'algorithme cité), dès qu'on rencontre un noeud déjà parcouru on sort les 2 extrémités du parcours. Ex : A>B>D>B donne A-D, B ayant déjà été rencontré.
En tenant compte du fait A->B et A->B ne sont pas des doublons mais sont à considérer comme des chemins distincts.
Au demandeur de valider ma traduction...
Par contre j'ai encore du mal à faire le lien avec les couleurs de mon salon :-)
Le fichier n'est qu'un xlsx, pas beaucoup de risques ;-)

Trouver toutes les combinaisons d'apres un tableau et un algorithme [XL-2013]

Macros et VBA Excel

Discussions similaires

Partager

Partager