Algo: créer toutes les combinaisons possibles

Résolu/Fermé

Kobaya Messages postés 282 Date d'inscription Statut Membre Dernière intervention -
librequetucrois - 20 févr. 2012 à 11:36

Bonjour à tous,

Je me creuse la tête depuis un bon moment déjà pour résoudre ceci :
J'ai 3 éléments A, B et C. Comment faire pour construire toutes les combinaisons possibles (ABC, ACB, BAC, BCA, CAB, CBA), sachant que le nombre d'éléments peut aller jusqu'à 4 ou 5. Le nombre de combinaisons est n!, mais part ça...
J'ai essayé en vain plusieurs combinaisons de boucles FOR/NEXT, DO/LOOP...

A défaut de me donner l'algorythme, voire le prog en VB, si quelqu'un a une piste, une idée de départ, c'est pas de refus!

A+,
Kobaya.

Configuration: Windows XP PRO
Pentium 4

Afficher la suite

A voir également:

Algo 32
Trouver toutes les combinaisons possibles - Meilleures réponses
Générateur de combinaison 4 chiffres excel - Meilleures réponses
Power iso 32 bit - Télécharger - Gravure
32 bits - Guide
Algorithme avec alg 32 - Forum Algorithmes / Méthodes
Clé de produit windows 7 professionnel 32 bits gratuit - Guide
32 gb en go ✓ - Forum Windows

11 réponses

Réponse 1 / 11

Meilleure réponse
La meilleure réponse est la réponse qui a été validée par nos équipes.
p.legal Messages postés 89 Statut Membre 24
La modif est simple, j'ai ajouté la "sub" nomée doublon.
```
    text$="ABCDEA"
    debut$=""
    global result$, debut$, glon, nb, blok
    debut$=text$
    glon=len(text$)
    call doublon text$
    if blok=1 then end
    r$=combine$(text$)
    print "il y a ";nb;" réponses."
    input r$
    end

function combine$(text$)
    lon=len(text$)
    for i=1 to lon
        trace 2
        text2$=mid$(text$,i+1)+left$(text$,i-1)
        ch$=mid$(text$,i,1)
        result$=result$+ch$
        if text2$<>"" then
            r$=combine$(text2$)
        else
            rlon=len(result$)
            dlon=glon-rlon
            result$=left$(debut$,dlon)+result$
            debut$=result$
            print result$
            result$=""
            nb=nb+1
        end if
    next i
    combine$=""
    end function

sub doublon txt$
    lon=len(txt$)
    for i=1 to lon
        ch$=mid$(txt$, i, 1)
        for j=1 to lon
            if j=i then exit for
            if ch$=mid$(txt$, j, 1) then blok=1: exit for
        next j
        if blok=1 then exit for
    next i
    if blok=1 then
        notice "Doublon detecté !"+chr$(13)+"Le caractère '"+ch$+"' à été detecté en double."
    end if
    end sub
```
et maintenant, cela te convient t'il ?

voici le resultat pour la chaine "ABCD":
```
ABCD
ABDC
ACDB
ACBD
ADBC
ADCB
BCDA
BCAD
BDAC
BDCA
BACD
BADC
CDAB
CDBA
CABD
CADB
CBDA
CBAD
DABC
DACB
DBCA
DBAC
DCAB
DCBA
il y a 24 réponses.
?
```
38
1. Kobaya Messages postés 282 Date d'inscription Statut Membre Dernière intervention 214
  
  Ca y est ! Ca marche !!!
  
  En fait, je n'ai pas utilisé la procédure doublon(), et ça semble fonctionner (j'ai testé jusqu'à 7 éléments).
  
  Donc, un grand merci à toi p.legal :-)
  
  0
2. scorpions59
  
  desoler il te manque AACD et AADC
  
  -1
  1. p.legal Messages postés 89 Statut Membre 24 > scorpions59
    
    Il ne veut pas de doublon !
    
    AACD contient 2 fois A
    
    0
3. Lmedou
  
  Bonjour,
  
  Je dois être un peu neuneu, mais cette macro semble parfaitement répondre à mon besoin, mais je ne parviens pas à la faire fonctionner.
  
  Quelle nom faut il lui donner ? Un Sub Macro2() la fait planter. Pour info, je suis Excel 2007
  
  Une bonne âme peut elle peut me débloquer ?
  
  Merci.
  
  0
4. Adrien94
  
  Si tu as du mal, tu peux tester le code suivant :
  
  Sub genererCombinaison()
  'On déclare des variables de types Integer qui stockent le code ASCII de la lettre
  Dim char_number_1, char_number_2, char_number_3, char_number_4 As Integer
  'Variable qui va stocker le résultat de notre combinaison
  Dim macombinaison As String
  'Integer qui compte le nombre de combinaisons
  Dim cmb_id As Integer
  
  'Initialisation du compteur
  cmb_id = 1
  
  'la lettre A a pour code ASCII 65
  'la lettre B a pour code ASCII 66
  'la lettre C a pour code ASCII 67
  'la lettre D a pour code ASCII 68
  
  'On parcourt les lettres de A à D
  For char_number_1 = 65 To 68
  'On parcourt les lettres de A à D
  For char_number_2 = 65 To 68
  'On élimine le cas où les 2 premières lettres sont identiques
  If char_number_2 <> char_number_1 Then
  'On parcourt les lettres de A à D
  For char_number_3 = 65 To 68
  'On élimine les cas suivants :
  ' 3ème lettre = 2ème lettre
  ' 3ème lettre = 1ère lettre
  If char_number_3 <> char_number_2 And char_number_3 <> char_number_1 Then
  'On parcourt les lettres de A à D
  For char_number_4 = 65 To 68
  'On élimine les cas suivants :
  ' 4ème lettre = 3ème lettre
  ' 4ème lettre = 2ème lettre
  ' 4ème lettre = 1ère lettre
  If char_number_4 <> char_number_3 And _
  char_number_4 <> char_number_2 And _
  char_number_4 <> char_number_1 Then
  'On concatène les caractères formés à partir des codes ASCII
  macombinaison = Chr(char_number_1) & Chr(char_number_2) & Chr(char_number_3) & Chr(char_number_4)
  'On affiche le numéro de la combinaison et la chaîne de caractères
  Debug.Print ("Combinaison n°" & Trim(Str(cmb_id)) & " : " & macombinaison)
  'On incrémente le compteur
  cmb_id = cmb_id + 1
  End If
  Next
  End If
  Next
  End If
  Next
  Next char_number_1
  End Sub
  
  Cette Sub affiche le résultat dans la console de Debug
  
  0

p.legal Messages postés 89 Statut Membre 24

Voici le code en liberty BASIC

    text$="ABCDE"
    debut$=""
    global result$, debut$, glon, nb
    debut$=text$
    glon=len(text$)
    r$=combine$(text$)
    print "il y a ";nb;" réponses."
    input r$
    end

function combine$(text$)
    lon=len(text$)
    for i=1 to lon
        trace 2
        text2$=mid$(text$,i+1)+left$(text$,i-1)
        ch$=mid$(text$,i,1)
        result$=result$+ch$
        if text2$<>"" then
            r$=combine$(text2$)
        else
            rlon=len(result$)
            dlon=glon-rlon
            result$=left$(debut$,dlon)+result$
            debut$=result$
            print result$
            result$=""
            nb=nb+1
        end if
    next i
    combine$=""
    end function

@++

liberty BASIC France : http://lbasic.atomysk.com
et son Forum d'aide : http://lbasic.atomysk.com/forum

Kobaya Messages postés 282 Date d'inscription Statut Membre Dernière intervention 214

merci pour ta réponse !

J'ai oublié de préciser que chaque lettre ne peut pas être doublée : AABCE ne dois pas être accepté.

J'ai modifié (un peu) et testé ton code, mais malheureusement pour moi, ça ne fonctionne pas...
0

pom

Salut voici en gros l'idée

const int N=3; // par exemple

for(int i=0;i<N;i++)
{
for(int j=0;j<N;j++)
if(j!=i) // test 1
{
for(int k=0;k<N;k++)
if(k!=i && k!=j)
cout<<v[i]<<v[j]<<v[k]<<endl;
} // fin test 1
} // fin pour en i

pom

oups, j'ai oublié

v=[A,B,C];
0
Kobaya Messages postés 282 Date d'inscription Statut Membre Dernière intervention 214

Un si gros problème résolu en si peu de lignes! J'en reste baba...
Je teste ça au plus vite et je te tiens au courant.

merci very much Pom :-)
-1

Kobaya Messages postés 282 Date d'inscription Statut Membre Dernière intervention 214

et voici, un peu étoffé pour pouvoir traiter jusqu'à 6 éléments, ce que ça donne en VBA Excel. Encore merci Pom :-) :

Public Sub CreationChemin()
    Dim intI1 As Integer, intI2 As Integer, intI3 As Integer
    Dim intI4 As Integer, intI5 As Integer, intI6 As Integer, intN As Integer
    Dim strTab As String
    Dim sngChrono As Single
    
    strTab = UCase(InputBox("Saisissez les éléments : ", "Saisie", "ABCDEF"))
    
    sngChrono = Timer
    
    intI1 = 1
    Do Until Cells(1, intI1).Value = ""
        intI1 = intI1 + 1
    Loop
    Cells(1, intI1).Select
    
    intN = Len(strTab)
    ActiveCell.Value = strTab
    ActiveCell.Offset(1, 0).FormulaR1C1 = "=counta(R4C:R65536C)"
    ActiveCell.Offset(3, 0).Select
    
    For intI1 = 1 To intN
        For intI2 = 1 To intN
            If intI2 <> intI1 Then
                For intI3 = 1 To intN
                    If intI3 <> intI1 And intI3 <> intI2 Then
                        If Len(strTab) = 3 Then
                            ActiveCell.Value = Mid(strTab, intI1, 1) & Mid(strTab, intI2, 1) & Mid(strTab, intI3, 1)
                            ActiveCell.Offset(1, 0).Select
                        Else
                            For intI4 = 1 To intN
                                If intI4 <> intI1 And intI4 <> intI2 And intI4 <> intI3 Then
                                    If Len(strTab) > 4 Then
                                        For intI5 = 1 To intN
                                            If intI5 <> intI1 And intI5 <> intI2 And intI5 <> intI3 And intI5 <> intI4 Then
                                                If Len(strTab) > 5 Then
                                                    For intI6 = 1 To intN
                                                        If intI6 <> intI1 And intI6 <> intI2 And intI6 <> intI3 And intI6 <> intI4 And intI6 <> intI5 Then
                                                            ActiveCell.Value = Mid(strTab, intI1, 1) & Mid(strTab, intI2, 1) & Mid(strTab, intI3, 1) _
                                                                            & Mid(strTab, intI4, 1) & Mid(strTab, intI5, 1) & Mid(strTab, intI6, 1)
                                                            ActiveCell.Offset(1, 0).Select
                                                        End If
                                                    Next
                                                Else
                                                    ActiveCell.Value = Mid(strTab, intI1, 1) & Mid(strTab, intI2, 1) & Mid(strTab, intI3, 1) _
                                                        & Mid(strTab, intI4, 1) & Mid(strTab, intI5, 1)
                                                    ActiveCell.Offset(1, 0).Select
                                                End If
                                            End If
                                        Next
                                    Else
                                        ActiveCell.Value = Mid(strTab, intI1, 1) & Mid(strTab, intI2, 1) & Mid(strTab, intI3, 1) & Mid(strTab, intI4, 1)
                                        ActiveCell.Offset(1, 0).Select
                                    End If
                                End If
                            Next
                        End If
                    End If
                Next
            End If
        Next
    Next
    
    Cells(3, ActiveCell.Column).Value = (Timer - sngChrono)
End Sub

Réponse 4 / 11
stef

pour n elements, faut une fonction recursive!
voici l'algo:

fonction init(){
mot("");
}
fonction mot(m : chaine){
lettre =[A,B,C,...] //toutes les lettre
si taille(m)>taille_max_du_mot alors fin //permet de s'arreter!!
pour i=1 à taillle(lettre){
mot(m+lettre[i]); //appel récursif
}
}

stef
7
Vous n’avez pas trouvé la réponse que vous recherchez ?
Posez votre question

cs-bilou Messages postés 836 Statut Membre 164

Sinon en batch:

@echo off
for %%i in (A,B,C,D) do (
for %%j in (A,B,C,D) do (
for %%k in (A,B,C,D) do (
for %%l in (A,B,C,D) do (
echo %%i%%j%%k%%l
)
)
)
)
pause

Je sais pas si c'est sa que tu cherche.
J'espère t'avoir aider.
Bilou.

librequetucrois

salut ; au cas où (si ça peut servir) ; CompteurBoucleFor.bat :

(fait à partir du message de cs-bilou suite à une recherche sur le web concernant les problèmes de vitesse quand on veut trouver toutes les combinaisons possibles en itérant le contenu d'un fichier (j'ai trouvé un petit truc mais sans plus) ; j'aurais aimé imbriquer deux compteurs sans utiliser "set /a" pour la compatibilité)

@echo off
cls

setlocal enableextensions enabledelayedexpansion

for %%i in (A,B,C,D) do (
for %%j in (A,B,C,D) do (
for %%k in (A,B,C,D) do (
for %%l in (A,B,C,D) do (

echo %%i%%j%%k%%l

)
)
)
)

pause
cls

set varfincount=37
set tyty=-1

echo Start test compteur HEX (FFFF) et DEC (65535) (fin = !varfincount!) :
echo.
pause
echo.

for %%i in (0 1 2 3 4 5 6 7 8 9 A B C D E F) do (
for %%j in (0 1 2 3 4 5 6 7 8 9 A B C D E F) do (
for %%k in (0 1 2 3 4 5 6 7 8 9 A B C D E F) do (
for %%l in (0 1 2 3 4 5 6 7 8 9 A B C D E F) do (

set /a tyty+=1

echo 111= %%i%%j%%k%%l

if !tyty! GEQ 0 if !tyty! LEQ 9 set varzero=0000
if !tyty! GEQ 10 if !tyty! LEQ 99 set varzero=000
if !tyty! GEQ 100 if !tyty! LEQ 999 set varzero=00
if !tyty! GEQ 1000 if !tyty! LEQ 9999 set varzero=0
if !tyty! GEQ 10000 if !tyty! LEQ 99999 set varzero=

echo 222= !varzero!!tyty!& pause

if !tyty! GEQ !varfincount! call :suite

if !tyty! GEQ 68 goto fin 

)
)
)
)

:suite

echo.
echo Sortie (compteur DEC = !varfincount!) ...
echo.
pause
echo.
cls
set varfincount=68
echo Re-Start test compteur HEX (FFFF) et DEC (65535) (fin = !varfincount!) :
echo.
exit /B

:fin

endlocal
exit /B

le petit truc :
*************
Modèle ... :

Recherches de correspondances hashs / fichiers :

Itérations successives côte-à-côte du contenu .:

Un fichier vide par ligne est créé et itéré ...:

===============================================
0[+1]: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16! <= base
===============================================
2 PC :
===============================================
!0>1!: 0 1 . . . . . . . . .. .. .. .. .. .. ..! <= constantes
!---!: ----------------------------------------!
0[+2]: 0 . 2 . 4 . 6 . 8 . 10 .. 12 .. 14 .. 16! <= 1 fichier
1[+2]: 0 1 . 3 . 5 . 7 . 9 .. 11 .. 13 .. 15 ..! <= 1 fichier
===============================================
3 PC :
===============================================
!0>2!: 0 1 2 . . . . . . . .. .. .. .. .. .. ..! <= constantes
!---!: ----------------------------------------!
0[+3]: 0 . . 3 . . 6 . . 9 .. .. 12 .. .. 15 ..! <= 1 fichier
1[+3]: 0 1 . . 4 . . 7 . . 10 .. .. 13 .. .. 16! <= 1 fichier
2[+3]: 0 . 2 . . 5 . . 8 . .. 11 .. .. 14 .. ..! <= 1 fichier
===============================================
4 PC :
===============================================
!0>3!: 0 1 2 3 . . . . . . .. .. .. .. .. .. ..! <= constantes
!---!: ----------------------------------------!
0[+4]: 0 . . . 4 . . . 8 . .. .. 12 .. .. .. 16! <= 1 fichier
1[+4]: 0 1 . . . 5 . . . 9 .. .. .. 13 .. .. ..! <= 1 fichier
2[+4]: 0 . 2 . . . 6 . . . 10 .. .. .. 14 .. ..! <= 1 fichier
3[+4]: 0 . . 3 . . . 7 . . .. 11 .. .. .. 15 ..! <= 1 fichier
===============================================
5 PC :
===============================================
!0>4!: 0 1 2 3 4 . . . . . .. .. .. .. .. .. ..! <= constantes
!---!: ----------------------------------------!
0[+5]: 0 . . . . 5 . . . . 10 .. .. .. .. 15 ..! <= 1 fichier
1[+5]: 0 1 . . . . 6 . . . .. 11 .. .. .. .. 16! <= 1 fichier
2[+5]: 0 . 2 . . . . 7 . . .. .. 12 .. .. .. ..! <= 1 fichier
3[+5]: 0 . . 3 . . . . 8 . .. .. .. 13 .. .. ..! <= 1 fichier
4[+5]: 0 . . . 4 . . . . 9 .. .. .. .. 14 .. ..! <= 1 fichier
===============================================

Un fichier par pc ou processeur (...) et avec une itération unique par fichier.

On cherche un hash (un rapide (disons CRC32) puis les autres plus lents pour vérifier si il y a un résultat positif) qui correspond au fichier à reconstruire ; la taille du fichier d'origine en octets est connue et donc la taille du fichier de travail correspond (fsutil file createnew permet de faire un fichier vide) et le hash (crc32 + md5 + sha1 + sha256) provient du fichier d'origine dans un état correcte (pas endommagé).

On itère le contenu du fichier après avoir vérifié si le hash correspond. Si plusieurs pc sont utilisés, la valeur des itérations correspond (...) avec le modèle ci-dessus. On cherche qu'une fois une correspondance.

Les fichiers privées ne doivent pas être récupérés ou reconstruits depuis des fermes de calculateurs publiques ou sans sécurités. La taille et le hash suffise. La sécurité, c'est le temps ; mais le procédé fonctionne.
*************

Réponse 6 / 11
domget Messages postés 3 Statut Membre 1

Salut à tous,

Je suis admiratif des possibilité d'Excel, sans en être un expert, il s'en faut de beaucoup.

J'aimerais savoir comment créer un tableau qui me donnerait une liste des combinaisons de chiffres réalisables avec un nombre x de chiffres; Exemple, combien de combinaisons de 4 chiffres avec 3 chiffres de départ ?)

Je n'arrive pas à trouver la (les) formule(s) adaptée(s)

Bonne journée !

Domget
4
1. p.legal Messages postés 89 Statut Membre 24
  
  C'est presque le même code en liberty BASIC, il suffit d'accepter les doublons et de refuser 0 comme premier élément de la liste.
  
  si tu veux le code en Liberty BASIC fais moi signe.
  
  @++
  
  0
Réponse 7 / 11
BM

et pour 'n' elements?
2
1. p.legal Messages postés 89 Statut Membre 24
  
  Mon code est une fonction récursive. Plus n est grand plus ça prendra de temps mais elle peut traiter n'importe quelle valeur de n (sous reserve de la limitation imposée par ta mémoire vive lol )
  
  0
Réponse 8 / 11
yasmoh2010

Bonjour
Voici un programme pascal modulaire qui affiche toutes les combinaisons possibles des caractères numériques (chiffres) ou alphabétiques dans une chaîne ch, sachant que le nombre de combinaisons est égale au factoriel du nombre total des chiffres , exemple pour ch = 123 il existe 3! combinaisons = 6 combinaison= 6 permutations: pour le nombre 123
le programme affiche 213-231-132-312-321-123

Program combinaison;
Uses WinCrt;

Var ch:string;

Procedure Remplir (Var ch:string);
begin
writeln('donner le nombre');
Readln(ch);
End;

procedure permut(var x,y:char);
var aux:char;
begin
aux:=x;
x:=y;
y:=aux
end;

function fact(x:integer):integer;
var f,i:integer;

begin
f:=1;
for i:= 1 to x do
begin
f:=f*i ;
end;
fact:=f;
end;

procedure affichecomb(ch:string);
var i,n,np:integer;
begin
n:=length(ch);
np:=0;
repeat

for i:= 1 to n-1 do
begin
permut(ch[i],ch[i+1]);
np:=np+1;
write(ch,'-');
end;
permut(ch[1],ch[n]);
write(ch,'-');
np:=np+1;

until np =fact(length(ch));
end;

begin
remplir(ch);
writeln;
affichecomb(ch);
end.
2
1. omatdi Messages postés 1 Statut Membre
  
  bonjour tout le monde
  merci yasmoh2010
  voila le programme de permutation qui affiche toutes les combinaisons possibles des caractères numériques (chiffres) ou alphabétiques en vb.net
  par exemple 123
  le programme va afficher:
  213,231,321,312,132,123
  
  Dim ch1 As String
  
  Function fact(ByVal x As Integer) As Integer
  
  Dim f, i As Integer
  f = 1
  For i = 1 To x
  f = f * i
  Next
  fact = f
  
  End Function
  
  Sub Main()
  
  Dim ch, ch1 As String
  Dim j, n As Integer
  Console.WriteLine("donner votre nombre")
  ch = Console.ReadLine
  n = 0
  ch1 = ""
  Do
  j = 1
  For i As Integer = 0 To ch.Length - 1
  j = j + 1
  If i = 0 Then
  ch1 = Mid(ch, j, 1) & Mid(ch, j - 1, 1) & Mid(ch, j + 1, ch.Length - j)
  Console.Write(ch1 & ",")
  ch = ch1
  n = n + 1
  Else
  If ch.Length - j >= 0 Then
  ch1 = Mid(ch1, 1, i) & Mid(ch, j, 1) & Mid(ch, j - 1, 1) & Mid(ch, j + 1, ch.Length - j)
  Console.Write(ch1 & ",")
  ch = ch1
  n = n + 1
  End If
  End If
  Next
  Loop Until n = fact(ch.Length)
  Console.ReadLine()
  
  End Sub
  
  bonne chance a vous tous
  
  3
Réponse 9 / 11
fab

Bonjour,
pouvez vous m'aider à programmer en matlab toutes les combinaison d'une matrice formé de 14 lignes oü ses elements sont 1,2 et 3
2
1. samouaa
  
  sous matlab il suffit d'utiliser la fonction perms
  
  0
Réponse 10 / 11
kobaya

salut BM,

ce poste date un peu, et je n'ai plus trop les données en tête, mais à priori, la fonction récursive devrait fonctionner quelque soit le nombre de caractères à permuter.

Cordialement,
Kobaya.
1
Réponse 11 / 11
PLOP

Ne pas confondre Combinaisons & Permutations

Les Combinaisons sont les suites sans Répetitions des Eléments:
Exemple avec Maximum = 4 on souhaite les Combinaisons de 2 on trouve :

1-2
1-3
1-4
2-3
2-4
3-4

Un algorithme simple se rapproche d'un compteur qui incrémente ( en gros).

max = 4

For a = 1 to max-1

For b = a+1 to max

Affiche A // Affiche B

Next B

Next A

Il suffit de rajouter une boucle For Next pour passer au Combinaisons de 3 ...

Voila @ +
1

Algo: créer toutes les combinaisons possibles

11 réponses

Discussions similaires

Newsletters