Discussion :

[[ZiP]]

Bonjour,

Je cherche à lister toutes les combinaisons possibles pour une chaine de 4 caractères fabriquée à partir de la table de caractères suivante : 'abc'.

Je ne sais pas trop comment développer mon algorithme, j'imagine que je dois utiliser la récursivité ?

Je voudrais pourvoir par la suite pouvoir avec cette même fonction générer toutes les combinaisons possibles pour une chaine de 5 caractères avec 'abcd'.

Comment feriez-vous ?

Pouvez-vous me donner des pistes ?

Merci,
ZiP

[qi130]

Une idée à 4 sous (pas + vue l'heure).

Ca revient à "compter" de 0000 à 2222 en substituant 0 à A, 1 à B et 2 à C et tout ceci en base 3:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
0000 pour AAAA
0001 pour AAAB
0002
0010
0011
0012

...
etc

[Caribensila]

Salut,

En programmation la récursivité est à bannir !
C'est la démarche du sous-préfet : distinguée, mais lourde et sans grand pouvoir.
Laissons cela au raisonnement mathématique et aux mathématiciens qui savent s'en servir à propos.

Si j'ai bien compris, tu veux placer n objets discernables dans k emplacements en tenant compte de l'ordre (aaab <> abaa).
En analyse combinatoire, on appelle ça un arrangement avec répétition.
Tu auras donc n^k arrangements possibles :
3^4 = 81 dans le 1er cas.
4^5 = 1024 dans le 2ème.

Je te donne un exemple pour le 1er cas (fait sous D7).
Je te laisse le soin d'en faire une routine plus générale et plus optimisée. (Bein ouais, quand même )
J'ai choisi une StringList pour le sort et le SaveToFile (bien que la liste soit 'naturellement' triée dans cet exemple) :

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
var TempList    : TStrings;
    C1,C2,C3,C4 : Char;
    i           : Integer;
begin
TempList := TStringList.Create;
try
  for C1 := 'a' to 'c' do begin
    for C2 := 'a' to 'c' do begin
      for C3 := 'a' to 'c' do begin
        for C4 := 'a' to 'c' do begin
          TempList.Add(C1+C2+C3+C4);
        end;
      end;
    end;
  end;
  for i := 0 to TempList.Count-1 do Memo1.Lines.Add(TempList[i])
finally TempList.Free;   end;

PS: J'aime beaucoup l'approche de qi130.
Mais je ne vois pas le moyen de l'exploiter efficacement. Dommage.

[[ZiP]]

Bonjour,

J'avais déjà pensé à ça mais le problème qui se pose, c'est que le nombre de caractères peut varier.

Par conséquent, le notre de boucles for va varier aussi.

Imaginons avec 25 caractères...

C'est pour ça que j'étais parti sur du récursif

L'ordre n'est pas nécessaire dans mon cas, mais juste avoir toutes les possibilités.

Je vais étudier ta proposition,
Merci,
ZiP

[DOLPat®]

bonjour

Tu peux essayer avec ça: (vu ici; Merci à Paul )

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
const
  LongMaxi = 4;
 
procedure Combine(s:string);
var
  c: char;
begin
  if length(s) = LongMaxi+1 then exit;
    Form2.Memo1.Lines.Add(s);
  for c := 'a' to 'c' do
    Combine(s + c);
end;
 
procedure TForm2.FormCreate(Sender: TObject);
var
  i:    Integer;
  c:    Char;
begin
  for c := 'a' to 'c' do
    combine(c);
end;

Mais si tu comptes partir sur une base de de recherche sur 25 caractères, à mon avis, va falloir être patient ou alors écrire le code en assembleur...

Pat.

[Caribensila]

Imaginons avec 25 caractères...

Là, ça devient de la bistromatique.
Il faudrait peut-être revoir la logique de ton application. Car, de fait, on a rarement besoin de devoir lister tous les arrangements possibles. Les parcourir sera dejà assez gourmand en temps !

Es-tu sûr de devoir lister le résultat ?

[mick605]

bonjour

Tu peux essayer avec ça: (vu ici; Merci à Paul )

Une petite réécriture :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
procedure Combine(s:string; N : integer);
var
  C: char;
begin
  if N>0 then
  begin
    for C := 'a' to 'c' do
      Combine(s+C,N-1);
  end;
  else
    Writeln(S);
end;

Pour l'appeler :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

Combine('',4);

Pour afficher toutes les combinaisons de 4 caracteres de A à Z, ca prends environ 25 secondes sur mon PC (i5 @ 2.27 GHz) ...

Mais je rejoins l'avis de Caribensila ... C'est seulement pour un test ? Ou tu as une appli qui nécessite ca ?

[fab256]

En reprenant l'idée de qi130, on peut avoir une fonction générale non recursive pour n'importe quelle chaine s de longueur n a combiner sur k positions

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
procedure Combine(s : string; k : integer);
var tab :array[0..100] of integer;
    n,i,j : integer;
begin
n:=length(s);
for i:=0 to k do tab[i]:=0;
while tab[k]=0 do
  begin
  for i:=k-1 downto 0 do write(s[tab[i]+1]);
  writeln;
  tab[0]:=(tab[0]+1) mod n;
  j:=0;
  while tab[j]= 0 do
    begin
    inc(j);
    tab[j]:=(tab[j]+1) mod n;
    end;
  end;
end;

L'appel se fait par

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

Combine('abc',4);

ou bien

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

Combine('abcd',5);

Si on veux se passer de la fonction mod, on remplace la ligne

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

  tab[0]:=(tab[0]+1) mod n;

par

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
inc(tab[0]); 
if tab[0]=n then tab[0]=0;

meme traitement pour la ligne 16

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
inc(tab[j]); 
if tab[j]=n then tab[j]=0;

[[ZiP]]

Bonjour fab256,

Je viens de tester ton code, c'est exactement ce que je voulais !

Je l'ai modifié ainsi pour le tester :

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
procedure Combine(s: String; k: Integer);
var
     tab : array [0..100] of Integer;
     n,i,j : Integer;
     chaine : String;
begin
     n := Length(s);
 
     for i:=0 to k do
          tab[i] := 0;
 
     while tab[k]=0 do
     begin
          chaine := '';
 
          for i:=k-1 downto 0 do
               chaine := chaine + s[tab[i] + 1];
 
          Form1.ListBox1.Items.Add(chaine);
          tab[0] := (tab[0] + 1) mod n;
          j := 0;
 
          while tab[j]= 0 do
          begin
               Inc(j);
               tab[j] := (tab[j] + 1) mod n;
          end;
     end;
end;
 
procedure TForm1.Button1Click(Sender: TObject);
begin
     Combine('abc', 3);
     Label1.Caption := IntToStr(ListBox1.Count);
end;

Merci !
ZiP

[ShaiLeTroll]

Un gros sujet de 5 Pages "Test possibilités possible longue boucle" a déjà apporter de nombreuses réponses sur la combinatoire !
A Lire !