Toutes les Combinaisons possibles

Voir le sujet précédent Voir le sujet suivant Aller en bas

Toutes les Combinaisons possibles

Message par informix le Dim 6 Jan - 17:24

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.

_________________
informix, Ecole d'ingénieurs
Les passions font vivre l'Homme; sa sagesse le fait seulement durer.
avatar
informix
Nombre Rationnel
Nombre Rationnel

Nombre de messages : 399
Réputation : 4
Points : 3911
Date d'inscription : 19/03/2007

Feuille de personnage
Capacité linguistique:
1000/1000  (1000/1000)

Revenir en haut Aller en bas

Re: Toutes les Combinaisons possibles

Message par informix le Dim 6 Jan - 17:26

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

amicalement.

_________________
informix, Ecole d'ingénieurs
Les passions font vivre l'Homme; sa sagesse le fait seulement durer.
avatar
informix
Nombre Rationnel
Nombre Rationnel

Nombre de messages : 399
Réputation : 4
Points : 3911
Date d'inscription : 19/03/2007

Feuille de personnage
Capacité linguistique:
1000/1000  (1000/1000)

Revenir en haut Aller en bas

Re: Toutes les Combinaisons possibles

Message par manianis le Dim 6 Jan - 22:59

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

manianis
Nombre Réel
Nombre Réel

Masculin
Nombre de messages : 975
Localisation : Tunisie
Réputation : 4
Points : 3640
Date d'inscription : 11/10/2007

Feuille de personnage
Capacité linguistique:
999/1000  (999/1000)

http://manianis.sitesled.com/

Revenir en haut Aller en bas

Re: Toutes les Combinaisons possibles

Message par methodiX le Mer 16 Jan - 1:18

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

_________________
Sami - Methodix, tunis
Le génie de Newton a consisté à dire que la lune tombe alors que tout le monde voit bien qu'elle ne tombe pas.
(Paul Valéry)
_____
Cliquer ici: Voir les nouveaux messages depuis votre dernière visite
Cliquer ici: Astuce: Utiliser l'outil "Recherche" du forum
avatar
methodiX
Admin
Admin

Masculin
Nombre de messages : 1260
Localisation : Le couloir de l'école polytechnique de Tunis
Réputation : 68
Points : 4639
Date d'inscription : 22/03/2007

Feuille de personnage
Capacité linguistique:
1000/1000  (1000/1000)

Revenir en haut Aller en bas

Re: Toutes les Combinaisons possibles

Message par manianis le Jeu 17 Jan - 16:31

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

Difficile la question methodiX. Very Happy

manianis
Nombre Réel
Nombre Réel

Masculin
Nombre de messages : 975
Localisation : Tunisie
Réputation : 4
Points : 3640
Date d'inscription : 11/10/2007

Feuille de personnage
Capacité linguistique:
999/1000  (999/1000)

http://manianis.sitesled.com/

Revenir en haut Aller en bas

Re: Toutes les Combinaisons possibles

Message par Napoléon le Jeu 17 Jan - 19:39

manianis: mmmm, n! Smile
je ne crois pas qu'il est aussi têtu que tu le crois Smile
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.

_________________
Nabil - tunis
خير الناس أنفعهم للناس
avatar
Napoléon
Admin
Admin

Masculin
Nombre de messages : 2934
Localisation : Tunisie
Réputation : 122
Points : 5257
Date d'inscription : 19/03/2007

Feuille de personnage
Capacité linguistique:
999/1000  (999/1000)

http://infomath.online-talk.net

Revenir en haut Aller en bas

Re: Toutes les Combinaisons possibles

Message par manianis le Jeu 17 Jan - 19:47

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

manianis
Nombre Réel
Nombre Réel

Masculin
Nombre de messages : 975
Localisation : Tunisie
Réputation : 4
Points : 3640
Date d'inscription : 11/10/2007

Feuille de personnage
Capacité linguistique:
999/1000  (999/1000)

http://manianis.sitesled.com/

Revenir en haut Aller en bas

Re: Toutes les Combinaisons possibles

Message par Napoléon le Jeu 17 Jan - 20:02

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

_________________
Nabil - tunis
خير الناس أنفعهم للناس
avatar
Napoléon
Admin
Admin

Masculin
Nombre de messages : 2934
Localisation : Tunisie
Réputation : 122
Points : 5257
Date d'inscription : 19/03/2007

Feuille de personnage
Capacité linguistique:
999/1000  (999/1000)

http://infomath.online-talk.net

Revenir en haut Aller en bas

Re: Toutes les Combinaisons possibles

Message par Islam le Jeu 17 Jan - 23:10

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... Embarassed

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

Islam
Entier Naturel
Entier Naturel

Féminin
Nombre de messages : 9
Age : 34
Localisation : Sud
Réputation : 0
Points : 3541
Date d'inscription : 16/01/2008

Feuille de personnage
Capacité linguistique:
1000/1000  (1000/1000)

Revenir en haut Aller en bas

Re: Toutes les Combinaisons possibles

Message par manianis le Ven 18 Jan - 0:31

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

manianis
Nombre Réel
Nombre Réel

Masculin
Nombre de messages : 975
Localisation : Tunisie
Réputation : 4
Points : 3640
Date d'inscription : 11/10/2007

Feuille de personnage
Capacité linguistique:
999/1000  (999/1000)

http://manianis.sitesled.com/

Revenir en haut Aller en bas

Re: Toutes les Combinaisons possibles

Message par manianis le Ven 18 Jan - 0:35

Trés bien. Il fonctionne bien.

manianis
Nombre Réel
Nombre Réel

Masculin
Nombre de messages : 975
Localisation : Tunisie
Réputation : 4
Points : 3640
Date d'inscription : 11/10/2007

Feuille de personnage
Capacité linguistique:
999/1000  (999/1000)

http://manianis.sitesled.com/

Revenir en haut Aller en bas

Re: Toutes les Combinaisons possibles

Message par methodiX le Ven 18 Jan - 1:18

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+' ')
      .......

??

_________________
Sami - Methodix, tunis
Le génie de Newton a consisté à dire que la lune tombe alors que tout le monde voit bien qu'elle ne tombe pas.
(Paul Valéry)
_____
Cliquer ici: Voir les nouveaux messages depuis votre dernière visite
Cliquer ici: Astuce: Utiliser l'outil "Recherche" du forum
avatar
methodiX
Admin
Admin

Masculin
Nombre de messages : 1260
Localisation : Le couloir de l'école polytechnique de Tunis
Réputation : 68
Points : 4639
Date d'inscription : 22/03/2007

Feuille de personnage
Capacité linguistique:
1000/1000  (1000/1000)

Revenir en haut Aller en bas

Re: Toutes les Combinaisons possibles

Message par methodiX le Ven 18 Jan - 1:37

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

study scratch

_________________
Sami - Methodix, tunis
Le génie de Newton a consisté à dire que la lune tombe alors que tout le monde voit bien qu'elle ne tombe pas.
(Paul Valéry)
_____
Cliquer ici: Voir les nouveaux messages depuis votre dernière visite
Cliquer ici: Astuce: Utiliser l'outil "Recherche" du forum
avatar
methodiX
Admin
Admin

Masculin
Nombre de messages : 1260
Localisation : Le couloir de l'école polytechnique de Tunis
Réputation : 68
Points : 4639
Date d'inscription : 22/03/2007

Feuille de personnage
Capacité linguistique:
1000/1000  (1000/1000)

Revenir en haut Aller en bas

Re: Toutes les Combinaisons possibles

Message par manianis le Ven 18 Jan - 12:07

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.

manianis
Nombre Réel
Nombre Réel

Masculin
Nombre de messages : 975
Localisation : Tunisie
Réputation : 4
Points : 3640
Date d'inscription : 11/10/2007

Feuille de personnage
Capacité linguistique:
999/1000  (999/1000)

http://manianis.sitesled.com/

Revenir en haut Aller en bas

Re: Toutes les Combinaisons possibles

Message par Napoléon le Ven 18 Jan - 12:14

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?
Wink

_________________
Nabil - tunis
خير الناس أنفعهم للناس
avatar
Napoléon
Admin
Admin

Masculin
Nombre de messages : 2934
Localisation : Tunisie
Réputation : 122
Points : 5257
Date d'inscription : 19/03/2007

Feuille de personnage
Capacité linguistique:
999/1000  (999/1000)

http://infomath.online-talk.net

Revenir en haut Aller en bas

Re: Toutes les Combinaisons possibles

Message par Islam le Ven 18 Jan - 17:43

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?
Wink

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

Islam
Entier Naturel
Entier Naturel

Féminin
Nombre de messages : 9
Age : 34
Localisation : Sud
Réputation : 0
Points : 3541
Date d'inscription : 16/01/2008

Feuille de personnage
Capacité linguistique:
1000/1000  (1000/1000)

Revenir en haut Aller en bas

Re: Toutes les Combinaisons possibles

Message par manianis le Sam 19 Jan - 1:10

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?
Wink

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.

manianis
Nombre Réel
Nombre Réel

Masculin
Nombre de messages : 975
Localisation : Tunisie
Réputation : 4
Points : 3640
Date d'inscription : 11/10/2007

Feuille de personnage
Capacité linguistique:
999/1000  (999/1000)

http://manianis.sitesled.com/

Revenir en haut Aller en bas

Re: Toutes les Combinaisons possibles

Message par manianis le Sam 19 Jan - 15:01

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

manianis
Nombre Réel
Nombre Réel

Masculin
Nombre de messages : 975
Localisation : Tunisie
Réputation : 4
Points : 3640
Date d'inscription : 11/10/2007

Feuille de personnage
Capacité linguistique:
999/1000  (999/1000)

http://manianis.sitesled.com/

Revenir en haut Aller en bas

Re: Toutes les Combinaisons possibles

Message par methodiX le Sam 19 Jan - 15:29

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.

_________________
Sami - Methodix, tunis
Le génie de Newton a consisté à dire que la lune tombe alors que tout le monde voit bien qu'elle ne tombe pas.
(Paul Valéry)
_____
Cliquer ici: Voir les nouveaux messages depuis votre dernière visite
Cliquer ici: Astuce: Utiliser l'outil "Recherche" du forum
avatar
methodiX
Admin
Admin

Masculin
Nombre de messages : 1260
Localisation : Le couloir de l'école polytechnique de Tunis
Réputation : 68
Points : 4639
Date d'inscription : 22/03/2007

Feuille de personnage
Capacité linguistique:
1000/1000  (1000/1000)

Revenir en haut Aller en bas

Re: Toutes les Combinaisons possibles

Message par manianis le Sam 19 Jan - 19:15

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

manianis
Nombre Réel
Nombre Réel

Masculin
Nombre de messages : 975
Localisation : Tunisie
Réputation : 4
Points : 3640
Date d'inscription : 11/10/2007

Feuille de personnage
Capacité linguistique:
999/1000  (999/1000)

http://manianis.sitesled.com/

Revenir en haut Aller en bas

Re: Toutes les Combinaisons possibles

Message par manianis le Lun 21 Jan - 1:07

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.

manianis
Nombre Réel
Nombre Réel

Masculin
Nombre de messages : 975
Localisation : Tunisie
Réputation : 4
Points : 3640
Date d'inscription : 11/10/2007

Feuille de personnage
Capacité linguistique:
999/1000  (999/1000)

http://manianis.sitesled.com/

Revenir en haut Aller en bas

Re: Toutes les Combinaisons possibles

Message par Contenu sponsorisé


Contenu sponsorisé


Revenir en haut Aller en bas

Voir le sujet précédent Voir le sujet suivant Revenir en haut

- Sujets similaires

 
Permission de ce forum:
Vous ne pouvez pas répondre aux sujets dans ce forum