[Algo] Permutations et arrangements

**rbag** · 09/10/2003, 10h02

Salut,

j'ai une question d'algo que je n'arrive pas à résoudre, pas que j'en ai vraiment besoin mais la démarche pour résoudre ce problème m'intéresserait. j'arrive avec une procédure récursive à générer tout les arrangements de lettres possibles en dessous d'une certaine taille de mot. Le programme donne une sortie comme suit:

a aa aaa aab aac aad ...

Le problème est que je n'arrive pas à trouver l'algo pour avoir une sortie du type:

a b c d ... aa ab ac ...zz aaa aab...

Je sais que ça fait un peut crackeur de mot de passe mais j'aimerais tout de même avoir votre avis sur la méthode à utiliser pour avoir une sortie de ce type car ça fait un moment que je me triture les neurones... (et ne vous inquietez pas, ce n'est pas à des fins peu louables

)

**Masterglob** · 09/10/2003, 16h19

Ca devrait fonctionner a peu pres:
Desolé pour ceux qui n'aiment pas PASCAL!!

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
 
function Donne_valeur_suivante(ch:string)
const 
DEBUT='a';
FIN=char(ord('z')+1);
var l:integer;
begin
l=length(ch)
 
repeat
ch[l]:=char(ord(ch[l])+1); //On prend le suivant
if ch[l]=FIN
then ch[l]=DEBUT;
dec(l);
until (l=0) or (ch(l+1)<>DEBUT)
if l=0
then ch=DEBUT+ch;

**rbag** · 09/10/2003, 18h07

A vrai dire c'est une bonne piste mais pas vraiment au point... Ca se plante assez rapidement.

**Trap D** · 09/10/2003, 19h19

En c on peut peut-être écrire :

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
 
void ecriremot(char *motdejafait, int nbl)
{
   int i;
   char tmp[100];
   for(i = 0; i < 26; i++)
   {
       sprintf(tmp, "%s%c", motdejafait, 'a'+i);
       puts(tmp);
    }
    if (nbl > 1)
    {
        for(i = 0; i < 26; i++)
       {
          sprintf(tmp, "%s%c", motdejafait, 'a'+i);
           ecriremot(tmp, nbl-1);
        }
     }
}

Tu fais l'appel avec ecriremot("", 5) par exemple.

**rbag** · 10/10/2003, 08h44

Eh ben non, raté encore une fois... Je l'ai traduit en delphi, ça donne qqchose comme ça, j'ai peut-être fait une erreur:

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
 
  procedure EcrireMot(ch: string; nb: integer);
  var
    i : integer;
    tmp: string;
  begin
     for i := 0 to 25 do begin
      tmp := ch + chr(ord('a') +  i);
      memo1.Lines.Add(tmp);
    end;
    if nb > 1 then
      for i := 0 to 25 do begin
        tmp := ch + chr(ord('a') +  i);
        EcrireMot(tmp, nb - 1);
      end;
  end;

la sortie est :

a ... z aa ab... az ... aaa aab

**Trap D** · 10/10/2003, 13h21

Je ne comprends pas bien

:
Tu dis au début que tu n'arrives pas à avoir la sortie :

a b c d ... aa ab ac ...zz aaa aab...

Avec l'algo que je te propose tu obtiens

a ... z aa ab... az ... aaa aab

et ça ne te va pas ?
Est-ce parce que ton prog s'arrète à aab (dans ce cas tu as une erreur quelque part) ou ce n'était pas ce que tu voulais au départ ?

**rbag** · 10/10/2003, 14h06

Pardon, je l'ai mal noté. La sortie de ton prog est:

a ... z aa ab... az aaa aab

sans faire az ba bb bc ... etc

**Trap D** · 10/10/2003, 15h04

Si, mais pas dans le bon ordre effectivement

Il me vient une idée, tu dérécursives, mais au lieu d'empiler tu enfiles les données à traiter
exemple

Code :

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

1
2
3
4
5
6
7
8
9
10
11
	enfiler ("", 3)
	tant que la file n'est pas vide
	debut
		defiler(chaine, longueur)
		pour car de 'a' à 'z'
			afficher chaine+car
		si longueur > 1 alors
			pour car de 'a' à 'z'
				enfiler chaine + car, longueur - 1
		fin si
	fin

Je n'ais pas le temps d'essayer, mais ça pourrait bien marcher !
Prévois une file longue !!!

**Trap D** · 11/10/2003, 16h20

c'est fait :

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
typedef struct file
{
	struct file *suivant;
	char mot[10];
	int len;
} file;
 
file *ptrfin, *ptrcur;
 
void deletepile(void)
{
   delete ptrcur;
}
void initfile (void)
{
	ptrcur = new(file);
	ptrfin = ptrcur;
}
void enfiler (char *mot, int len)
{
	strcpy(ptrcur->mot, mot);
	ptrcur->len = len;
	ptrcur->suivant = new(file);
	ptrcur = ptrcur->suivant;
}
 
int filevide (void)
{
	return ptrfin == ptrcur;
}
 
int defile(char *mot, int *len)
{
	if (filevide())
		return 0;
 
	strcpy(mot, ptrfin->mot);
	*len = ptrfin->len;
	file *tmp = ptrfin;
	ptrfin = ptrfin -> suivant;
	delete tmp;
	return 1;
}
 
int main(void)
{
	char tmp[50];
	char mot[50];
	int len;
 
	initfile();
	enfiler("", 3);
	while (filevide() == 0)
	{
		if (defile(mot, &len) == 0)
		{
			puts("Pb");
			return(0);
		}
		for(int i = 0; i < 26; i++)
		{
	       printf("%s%c ", mot, 'a'+i);
		   if (len > 1)
		   {
				sprintf(tmp, "%s%c", mot, 'a'+i);
				enfiler(tmp, len - 1);
		   }
		}
 
	}
    deletepile();
	return 0;
}

**rbag** · 13/10/2003, 11h40

Bravo ! Le résultat est parfait... Pour ce que ça intéresse, une petite traduction en Delphi. Non exempte d'erreurs car faite en fin de week end

...

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
 
 PFile = ^TFile;
 TFile = record
   Suivant : PFile;
   Mot : string;
   len : integer;
 end;  
 
procedure TForm1.Button1Click(Sender: TObject);
var
  PtrFin, PtrCur : PFile;
 
  procedure DeleteFile;
  begin
    Dispose(PtrCur);
  end;
 
  procedure InitFile;
  begin
    New(PtrCur);
    PtrFin := PtrCur;
  end;
 
  procedure Enfiler(Ch : string; Len : integer);
  begin
    PtrCur^.Mot := Ch;
    PtrCur^.Len := Len;
    PtrCur^.Suivant := New(PFile);
    PtrCur := PtrCur^.Suivant;
  end;
 
  function FileVide: boolean;
  begin
    Result := PtrFin = PtrCur;
  end;
 
  function Defile(var Ch: string; var Len : integer): boolean;
  var
    tmp : PFile;
  begin
    if FileVide then begin
      Result := false;
      Exit;
    end;
 
    Ch := Ptrfin^.Mot;
    Len := PtrFin^.len;
    Tmp := PtrFin;
    PtrFin := PtrFin^.Suivant;
    Dispose(Tmp);
    Result := true;
  end;
var
  Tmp : string;
  Mot : string;
  len, i : integer;
begin
  InitFile;
  Enfiler('', 3);
  while not FileVide do begin
    if not Defile(Mot, Len) then
      raise Exception.Create('Problem');
 
    for i := 0 to 25 do begin
      Memo1.Lines.Add(Mot + Chr(Ord('a') + i));
      if Len > 1 then begin
        Tmp := Mot + Chr(Ord('a') + i);
        Enfiler(Tmp, Len - 1);
      end;
    end;
  end;
  DeleteFile;
end;

[Algo] Permutations et arrangements

Algorithmes et structures de données

Discussions similaires

Partager

Partager