Algo: créer toutes les combinaisons possibles [Résolu/Fermé]

Signaler
Messages postés
282
Date d'inscription
vendredi 28 mai 2004
Statut
Membre
Dernière intervention
10 janvier 2008
-
 librequetucrois -
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.

11 réponses

Messages postés
88
Date d'inscription
mardi 14 juin 2005
Statut
Membre
Dernière intervention
21 mars 2008
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
Merci

Quelques mots de remerciements seront grandement appréciés. Ajouter un commentaire

CCM 76687 internautes nous ont dit merci ce mois-ci

Messages postés
282
Date d'inscription
vendredi 28 mai 2004
Statut
Membre
Dernière intervention
10 janvier 2008
212
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 :-)


desoler il te manque AACD et AADC
Messages postés
88
Date d'inscription
mardi 14 juin 2005
Statut
Membre
Dernière intervention
21 mars 2008
24 > scorpions59
Il ne veut pas de doublon !

AACD contient 2 fois A
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.
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
Messages postés
88
Date d'inscription
mardi 14 juin 2005
Statut
Membre
Dernière intervention
21 mars 2008
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
Messages postés
282
Date d'inscription
vendredi 28 mai 2004
Statut
Membre
Dernière intervention
10 janvier 2008
212
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...

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
oups, j'ai oublié

v=[A,B,C];
Messages postés
282
Date d'inscription
vendredi 28 mai 2004
Statut
Membre
Dernière intervention
10 janvier 2008
212
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 :-)
Messages postés
282
Date d'inscription
vendredi 28 mai 2004
Statut
Membre
Dernière intervention
10 janvier 2008
212
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

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
Messages postés
769
Date d'inscription
dimanche 2 décembre 2007
Statut
Membre
Dernière intervention
24 février 2011
161
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.

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.
*************
Messages postés
3
Date d'inscription
mardi 13 janvier 2004
Statut
Membre
Dernière intervention
17 octobre 2007

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
Messages postés
88
Date d'inscription
mardi 14 juin 2005
Statut
Membre
Dernière intervention
21 mars 2008
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.

@++
et pour 'n' elements?
Messages postés
88
Date d'inscription
mardi 14 juin 2005
Statut
Membre
Dernière intervention
21 mars 2008
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 )
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.
Messages postés
1
Date d'inscription
vendredi 5 février 2010
Statut
Membre
Dernière intervention
30 août 2011

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
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
sous matlab il suffit d'utiliser la fonction perms
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.
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 @ +