Toutes les Combinaisons possibles

Salut,

C'est un exercice extrait de la série proposée par Mlle Soumaya (cliquer ici)

Ecrire une procédure récursive qui génère toutes les combinaisons possibles d'une chaine de caractères.
Exemple: abc, acb, bac, bca, cab, cba

Merci pour la participation.

SVP: pour ceux qui ont posté des solutions dans d'autres sujets, déplacer vos solutions ici (copier coller)

amicalement.

OK, dès que j'aurai le temps je la déplacerai.

Si on veut déterminer le nombre des combinaisons possibles, ça va être combien?

n! avec n est le nombre de caractères de la chaîne.

Difficile la question methodiX.

manianis: mmmm, n!
je ne crois pas qu'il est aussi têtu que tu le crois
Tu as posé une hypothèse très limitative, c'est que les caractères sont deux à deux distincts!

donc ce n'est plus n! en dehors de cette hypothèse.

C'est beaucoup plus compliqué si on a des caractères identiques.

Même la procédure récursive change de forme en dehors de cette hypothèse.

informix a écrit:

Ecrire une procédure récursive qui génère toutes les combinaisons possibles d'une chaine de caractères.
Exemple: abc, acb, bac, bca, cab, cba

Bonsoir,
Je peux proposer une solution pour ce problème mais je ne sais pas le nombre de combinaisons possibles...

Principe:
Permuter la première lettre avec chacune des autres lettres jusqu'à la fin.
Pour chacun des mots trouvés, on ne touche pas à la première lettre et on refait le même traitement en commençant de la 2ème lettre...puis en commençant de la 3ème lettre des mots obtenus ainsi de suite...

Code:

Code:

procedure Combinaison(ch: string; i: integer);
var j: integer;
begin
      if i = length(ch) then write(ch+' ')
  else
      for j := i to length(ch) do
      begin
        Echange(ch, i, j);
        Combinaison(ch, i + 1);
        Echange(ch, i, j);
    end;
end;

Remarque: la procédure Echange permet de permuter (ou échanger) les valeurs de deux variables de type carcactère.

Cordialement

J'essaye votre programme bien que suis presque sûr qu'il fonctionne bien.

Trés bien. Il fonctionne bien.

Très méthodologique la présentation.

Que pensez-vous de cette modification?

Code:

procedure Combinaison(ch: string; i: integer);
var j: integer;
begin
      if (i<=0) then i:=1;
      if ((i >= length(ch)) then write(ch+' ')
      .......


??

Qu'est-ce que vous proposez si on relâche l'hypothèse:
Les lettres sont différentes deux à deux?

methodiX a écrit:Très méthodologique la présentation.

Que pensez-vous de cette modification?

Code:

procedure Combinaison(ch: string; i: integer);
var j: integer;
begin
      if (i<=0) then i:=1;
      if ((i >= length(ch)) then write(ch+' ')
      .......


??

Vous traitez les cas où i est mal entré ! bien que çà évite les erreurs mais c'est aussi maladroit comme solution car votre procédure devra vérifier une condition de plus à chaque appel.

Malheureusement, il n'y pas la gestion des exceptions en Pascal.
Manianis, si jamais on veut "offrir" au public, une fonction qui affiche les combinaisons possibles, on doit ajouter ces contrôles.
Au moins on ajoute :

Code:

if ((i >= length(ch)) then write(ch+' ')

car sinon, le procédure ne s'arrêtera jamais.
Que serait le plus important: plusieurs "IF" ajoutés ou bien une boucle infinie?

nabiL a écrit:

Code:

if ((i >= length(ch)) then write(ch+' ')

car sinon, le procédure ne s'arrêtera jamais.
Que serait le plus important: plusieurs "IF" ajoutés ou bien une boucle infinie?

Bonjour,
Merci bien pour les bonnes suggestions..
Bien sûr qu'on doit prévoir les cas d'erreurs de frappe par exemple ou ceux d'inattention de la part de l'utilisateur..

Merci une autre fois

nabiL a écrit:Malheureusement, il n'y pas la gestion des exceptions en Pascal.
Manianis, si jamais on veut "offrir" au public, une fonction qui affiche les combinaisons possibles, on doit ajouter ces contrôles.
Au moins on ajoute :

Code:

if ((i >= length(ch)) then write(ch+' ')

car sinon, le procédure ne s'arrêtera jamais.
Que serait le plus important: plusieurs "IF" ajoutés ou bien une boucle infinie?

J'ai dû être plus clair Nabil. Je paralais, en fait, du

Code:

if (i <= 0) then i:=1;

que je trouve inutile.

En ce qui concerne :

Code:

if ((i >= length(ch)) then write(ch+' ')

Je trouve que le supèrieur ou égal est maladroit, je dirai plutôt qu'il est exact, mais comme il ne peut pas être supèrieur à la longueur de la chaîne sauf si le programmeur ne controle pas le flux de son programme pour que les cas extrêmes puissent surgir, alors je le qualifie de maladroit.

Autre avis, si cette procédure est destinée à être placée dans une bibliothèque de fonctions, ces contrôles devront être ajoutés parce qu'on ne sait pas ce que le public utilisateur pourra faire à l'aide de cette procédure donc son comportement doit être prévisible.

Et comment on fait pour avoir toutes les combinaisons en itératif ?

L'idée générale est de se servir d'une "Pile" (pour ceux qui ne connaissent pas la structure Pile, pensez à un tableau de caractère...)
Je vais expliquer l'idée à travers un exemple:
Supposant que la chaine est ABC.

1. On met dans la pile, tous les caractères de la chaine:
A|B|C
ceci veut dire que les combinaisons peuvent commencer par A ou B, ou C.

2. On dépile la pile. On obtient C. On empile les succeurs de C, qui sont A et B. La pile devient:
A|B|A|B

3. On dépile. On obtient B. on la concatène au mot Buffer courant C. On obtient "CB". On empile les succ. de B sachant qu'on a utilisé "CB" La pile devient:
A|B|A|

4. Le buffer devient CBA. Pas de successeurs. On affiche le mot donc. On passe à un autre en dépilant. Le nouveau Buffer est B. On empile ses successeurs, la pile devient:
A|A|C

5. etc...

On s'arrête lorsque la pile devient Vide.

En résumé, lorsqu'il n'y a pas de successeurs à empiler, on est sur que le buffer correspond bien à une Combinaison prête à être affichée.

J'espère que c'est clair.

Une méthode trés élégante merci methodiX

Voici un petit bout de code qui retrouve toutes les combinaisons d'une façon itérative.

Code:

procedure combinaison(ch:string);
var
  i, j, k, n : integer;
begin
  n := Length(ch);
 
  repeat
    Writeln(ch);
    i:=n; j:=n;
    while (i > 1) and (ch[i-1] >= ch[i]) do i:=i-1;
    while (j > 1) and (ch[i-1] >= ch[j]) do j:=j-1;
    if (i >= 2) then begin
      Permuter(ch[i-1], ch[j]);
      if (i <> n) then begin
        for k:=i to (n+i) div 2 do begin
          Permuter(ch[k], ch[n-k+i]);
        end;
      end;
    end;
  until (i<2);
end;

Si vous n'arrivez pas à comprendre la démarche je suis prêt à la détailler.