Recherche de toutes combinaisons

Le
Driss HANIB
Bonjour à tous,

soit un tableau qui contient un nombre non défini de lignes (en fait 6 à
10, pour l'intant 6) de chaine que l'on notera A B C D E (dans le cas ou il
y en a 5)
(en fait ce tableau contient aussi une valeur numérique rattaché à ces
chaines dy type 1 2 4 8 16 32 64 .. pour faire des sommes logiques)

Je cherche un algo qui permette (si possible quelque soit le nombre de
lignes) de trouver toutes les combinaisons possibles , celle-ci pouvant être
de 1 à n caractères (n étant le nombre de lignes). l'ordre doit être gardé
et pour moi AB = BA.
Pour commencer l'exemple
A
AB
ABC
ABCD
ABCDE
AC
ACD
ACDE
AD
ADE
AE
B
BC
BCD
BCDE
BD
BDE
BE

etc.

Merci pour vos pistes
Driss
Vidéos High-Tech et Jeu Vidéo
Téléchargements
Vos réponses
Gagnez chaque mois un abonnement Premium avec GNT : Inscrivez-vous !
Trier par : date / pertinence
jean-marc
Le #15355141
"Driss HANIB" news:ebpMD$
Bonjour à tous,

soit un tableau qui contient un nombre non défini de lignes (en fait 6 à
10, pour l'intant 6) de chaine que l'on notera A B C D E (dans le cas ou
il
y en a 5)
(en fait ce tableau contient aussi une valeur numérique rattaché à ces
chaines dy type 1 2 4 8 16 32 64 .. pour faire des sommes logiques)

Je cherche un algo qui permette (si possible quelque soit le nombre de
lignes) de trouver toutes les combinaisons possibles , celle-ci pouvant
être
de 1 à n caractères (n étant le nombre de lignes). l'ordre doit être gardé
et pour moi AB = BA.



Hello,

un grand classique dont la solution est toute simple,
mais il faut y penser !

Il suffit d'utiliser le fait que l'écriture en binaire
d'un nombre sur n bits fait apparaitre toutes les
combinaisons possibles des dits bits.

Ainsi, considérons 3 chaines:
A (1) en binaire 001
B (2) en binaire 010
C (4) en binaire 100

Comptons maintenant de 1 à 2^3-1 (cad de 1 à 7)
et exprimons les nombres du compatge en binaire:
1 001
2 010
3 011
4 100
5 101
6 110
7 111

Maintenant faisons apparaitre la lettre concernée
à chauqe position, en utilisant la combinaison
binaire comme un masque (si 1, je mets la lettre,
sinon, non) :

C B A
-----
0 0 1 => A
0 1 0 => B
0 1 1 => B A = A B
1 0 0 => C
1 0 1 => C A = A C
1 1 0 => C B = B C
1 1 1 => C B A = A B C


Et voila, le tour est joué.

Donc pour implémenter, il sufit de:
- compter de 1 à 2^N - 1, en binaire
- Parcourir la valeur binaire trouvée
caractère par caractère et placer la lettre
au besoin.

Si tu as besoin des AB <=> BA, il suffit de générer
la chaine à l'envers pour chaque chaine.

Cordialement;

--
Jean-marc Noury (jean_marc_n2)
Microsoft MVP - Visual Basic
FAQ VB: http://faq.vb.free.fr/
mailto: remove '_no_spam_' ;
jean-marc
Le #15355131
"Driss HANIB" news:ebpMD$

Pour compléter, tu trouveras dans la FAQ une fonction
pour converir un nombre d'une base à l'autre, sous
forme de chaine (donc de 10 à 2 dans ton cas):
http://faq.vb.free.fr/index.php?question‰

J'ai aussi écrit un programme qui permet de
résoudre des trucs de scrabble ou de Literati
en générant des permuations de lettres, utilisant le
principe sus-mentionné.
Le code est ici:
http://www.vbfrance.com/codes/JOUER-LITERATI-TEXTEXPRESS-MOT-PLUS-LONG-ETC_36617.aspx

Hope this helps;

Cordialement;

--
Jean-marc Noury (jean_marc_n2)
Microsoft MVP - Visual Basic
FAQ VB: http://faq.vb.free.fr/
mailto: remove '_no_spam_' ;
jean-marc
Le #15355121
"Driss HANIB" news:ebpMD$
Bonjour à tous,



Je complète encore:
tu n'es pas obligé de t'embêter avec la représentation
sous forme de chaine des valeurs binaires.
Il suffit de savoir que pour savoir
si le bit b d'un nombre N est à 1, il suffit de faire

SI (N AND (2^b)) = (2^b), alors b est à 1

Du coup, c'est trivial.

Voici un programme qui calcul ce que tu veux, dans
mon exemple les permutations de 4 chaines:

Option Explicit

Const N As Long = 4

Private Sub Command1_Click()
Dim t(N) As String
Dim i As Long, j As Long


t(1) = "J"
t(2) = "E"
t(3) = "A"
t(4) = "N"

For i = 1 To (2 ^ N) - 1
Debug.Print i; " ";
For j = 0 To N - 1
If (i And (2 ^ j)) = (2 ^ j) Then
Debug.Print t(j + 1);
End If
Next j
Debug.Print
Next i
End Sub

Qui produit :

1 J
2 E
3 JE
4 A
5 JA
6 EA
7 JEA
8 N
9 JN
10 EN
11 JEN
12 AN
13 JAN
14 EAN
15 JEAN


Il y a 15 solutions, c'est bien ça. et elles sont
toutes la, aux inversions près.


Cordialement;

--
Jean-marc Noury (jean_marc_n2)
Microsoft MVP - Visual Basic
FAQ VB: http://faq.vb.free.fr/
mailto: remove '_no_spam_' ;
jean-marc
Le #15355111
"jean-marc" news:478b7075$0$29256$

"Driss HANIB" news:ebpMD$
Bonjour à tous,



Je complète encore:



et encore !

La même chose sous forme d'une jolie fonction qui
remplit un tableau dynamique (avec en plus les
inversions : (ABC <=> CBA) ) :

Option Explicit

Const n As Long = 4

Private Function reverse_string(ByVal s As String)
Dim i As Long
Dim rs As String

For i = Len(s) To 1 Step -1
rs = rs & Mid$(s, i, 1)
Next i
reverse_string = rs
End Function

Private Function GenereCombi(t() As String, n As Long) As String()
Dim i As Long, j As Long
Dim nb As Long
Dim r As String
Dim res() As String

ReDim res(n + (2 ^ n - 1 - n) * 2)

For i = 1 To (2 ^ n) - 1
r = ""
For j = 0 To n - 1
If (i And (2 ^ j)) Then
r = r & t(j + 1)
End If
Next j
nb = nb + 1
res(nb) = r

' pour les permuations, commenter si nécessaire
If Len(r) >= 2 Then
nb = nb + 1
res(nb) = reverse_string(r)
End If
' fin generation inversion
Next i
GenereCombi = res
End Function


Et voici l'utilisation, simplissime :


Private Sub Command1_Click()
Dim a(4) As String
Dim t() As String
Dim i As Long

a(1) = "A": a(2) = "B": a(3) = "C": a(4) = "D"

t() = GenereCombi(a, 4)
For i = 1 To UBound(t())
Debug.Print i & vbTab & t(i)
Next i
End Sub

--
Jean-marc Noury (jean_marc_n2)
Microsoft MVP - Visual Basic
FAQ VB: http://faq.vb.free.fr/
mailto: remove '_no_spam_' ;


Driss HANIB
Le #15355091
Salut Jean Marc

Eh bien quel festival avec la progression crescendo..
Je vais regarder tous tes posts qui sont tous de belle facture
Merci pour cet exercice de style
On voit les pros.. et les autres (où je suis bien sur..)

Merci beaucoup

Driss

"jean-marc" news:478b92ce$0$22312$

"jean-marc" news:478b7075$0$29256$
>
> "Driss HANIB" > news:ebpMD$
>> Bonjour à tous,
>
> Je complète encore:

et encore !

La même chose sous forme d'une jolie fonction qui
remplit un tableau dynamique (avec en plus les
inversions : (ABC <=> CBA) ) :

Option Explicit

Const n As Long = 4

Private Function reverse_string(ByVal s As String)
Dim i As Long
Dim rs As String

For i = Len(s) To 1 Step -1
rs = rs & Mid$(s, i, 1)
Next i
reverse_string = rs
End Function

Private Function GenereCombi(t() As String, n As Long) As String()
Dim i As Long, j As Long
Dim nb As Long
Dim r As String
Dim res() As String

ReDim res(n + (2 ^ n - 1 - n) * 2)

For i = 1 To (2 ^ n) - 1
r = ""
For j = 0 To n - 1
If (i And (2 ^ j)) Then
r = r & t(j + 1)
End If
Next j
nb = nb + 1
res(nb) = r

' pour les permuations, commenter si nécessaire
If Len(r) >= 2 Then
nb = nb + 1
res(nb) = reverse_string(r)
End If
' fin generation inversion
Next i
GenereCombi = res
End Function


Et voici l'utilisation, simplissime :


Private Sub Command1_Click()
Dim a(4) As String
Dim t() As String
Dim i As Long

a(1) = "A": a(2) = "B": a(3) = "C": a(4) = "D"

t() = GenereCombi(a, 4)
For i = 1 To UBound(t())
Debug.Print i & vbTab & t(i)
Next i
End Sub

> --
> Jean-marc Noury (jean_marc_n2)
> Microsoft MVP - Visual Basic
> FAQ VB: http://faq.vb.free.fr/
> mailto: remove '_no_spam_' ;




Jean-marc
Le #15376791
Driss HANIB wrote:
Salut Jean Marc



Salut Driss,

Eh bien quel festival avec la progression crescendo..
Je vais regarder tous tes posts qui sont tous de belle facture
Merci pour cet exercice de style



De rien, je me suis aussi bien amusé à le faire :-)

On voit les pros.. et les autres (où je suis bien sur..)



C'est aussi (et surtout) qq années de pratique :---)

Bonne soirée !

--
Jean-marc Noury (jean_marc_n2)
Microsoft MVP - Visual Basic
FAQ VB: http://faq.vb.free.fr/
mailto: remove '_no_spam_' ;
Publicité
Poster une réponse
Anonyme