Algorithme de combinaison

Avec des lettres!

Sujet résolu

26 avril 2010 à 20:20:31

Bonjour à tous!

Je souhaite obtenir toutes les "combinaisons" (je m'explique plus bas) d'une série de 9lettres.

Les conditions sont les suivantes:
-l'ordre est important
-il peut y avoir plusieurs fois la même lettre dans la série de départ
-chaque lettre de la série de départ ne peut être utilisée qu'une fois

Mon idée est de mettre chacune des 9lettres en position "1", puis pour chacune de ces séries, je met chacune des 8lettres restantes en position 2, puis les 7 en position 3...

Mais mon code boucle à l'infini! je ne comprends pas pourquoi :

Voici mon main:

int main()
{
    char plaqueini[10];

    printf("Donnez les 9 lettres : ");
    scanf("%s",plaqueini);

    f(0,plaqueini);


    return 0;
}

et ma fonction:

void f(int indice, char plaque[]) // L'indice représente la position de la lettre que l'on traite
{
    int i;
    char mem;

    for(i=indice;i<9;i++) //On boucle pour mettre chacune des 9 lettres en position "indice"
    {
        mem=plaque[indice];
        plaque[indice]=plaque[i];
        plaque[i]=mem;

        printf("%s \n",plaque);

        if(indice<9)
            f(indice+1,plaque); //On recommence avec la position "indice+1"
    }
}

thiblt04

26 avril 2010 à 20:24:37

Indice vaut toujours 0, je ne comprends pas à quoi il sert dans ton code...

De plus, j'aurais mis les lettres dans un autre tableau de char de 9 lettres, rien que pour pouvoir le gérer plus facilement....

meteor2

26 avril 2010 à 20:25:37

Ta fonction récursive n'a aucun moyen de s'arrête, donc elle boucle à l'infinie...

Citation

Je souhaite obtenir toutes les "combinaisons" (je m'explique plus bas) d'une série de 9lettres.

Tu veux dire toutes les permutations, par exemple pour a, b et c?

a b c
a c b
b a c
b c a
c a b
c b a

Pouet_forever

26 avril 2010 à 20:29:57

Tu peux jeter un oeil ici : http://www.developpez.net/forums/d8771 [...] ne-reference/

casus_orez

26 avril 2010 à 20:33:09

Citation

Indice vaut toujours 0

Pourquoi? quand je lance f(indice+1,plaque) le "nouvel indice" est bien incrémenté non?

Citation

Ta fonction récursive n'a aucun moyen de s'arrête, donc elle boucle à l'infinie...

En fait je ne comprends pas pourquoi mon "if(indice<9)" ne suffit pas?
Je pense que c'est lié avec la remarque du dessus...

Citation

Tu veux dire toutes les permutations, par exemple pour a, b et c?

Oui exactement... Avec la condition que la série de départ puisse être : "AAZZERTYL"

Merci

meteor2

26 avril 2010 à 21:10:01

Citation : Pouet_forever

Tu peux jeter un oeil ici : http://www.developpez.net/forums/d8771 [...] ne-reference/

J'ai regardé vite fait...mais tu peux me dire c'est quels codes qui marchent?? Ils m'ont pas l'air très optimisés.

casus_orez > Tu as eu une bonne intuition, cependant ce genre d'exercice n'est pas aisé.

Le principe pour afficher toutes les permutation :

On va remplir un tableau (une pile) avec les lettres au fur et à mesure. Lorsqu'il est plein, on l'affiche. Avant chaque appel on va le remplir d'une lettre, après chaque appel on va lui enlever une lettre.

-On dispose d'un tableau qui contient toutes les lettres (on ne touche pas à ce tableau!)
-On dispose d'une pile (celle qui va stocker les lettres)
-On dispose d'un tableau de boléens, qui, pour la pile entrain de se remplir, va savoir quelle lettre ou non a déjà été utilisée.

fonction anagramme(nbLettres)
{
    si nbLettres = 0
        afficher toutes les lettres de la pile
    sinon
        pour chaque lettre non utilisee
            marquer la lettre
            ajouter la lettre a la pile 
            on appelle angagramme(nbLettres - 1)
            on enlève la lettre de la pile
            on enlève le marqueur
}

Pour savoir si la lettre est déjà présente, on utilise un tableau de boléens (qu'on modifie lorsqu'on marque ou lorsqu'on enlève la marque).

Pouet_forever

26 avril 2010 à 21:12:43

Citation : meteor2

J'ai regardé vite fait...mais tu peux me dire c'est quels codes qui marchent?? Ils m'ont pas l'air très optimisés.

Le mien et celui d'Obsidian.

Après pour l'optimisation, je sais pas si on peut en faire sans tester toutes les solutions.

meteor2

26 avril 2010 à 21:23:14

Citation : Pouet_forever

Citation : meteor2

J'ai regardé vite fait...mais tu peux me dire c'est quels codes qui marchent?? Ils m'ont pas l'air très optimisés.

Le mien et celui d'Obsidian.
Après pour l'optimisation, je sais pas si on peut en faire sans tester toutes les solutions.

Le tiens est pas mal, par contre il fait des répétitions...pas des permutations (je sais pas trop si tu peux l'arranger pour en faire). Pour info l'algo que j'ai proposé, il suffit d'enlever 2 lignes pour qu'il fasse comme le tien.

Celui d'Obsidian...il est itératif, donc beaucoup plus lent, c'est pas du tout le même principe...(il est buggé qui plus est).

Pouet_forever

26 avril 2010 à 21:33:31

Citation : meteor2

il fait des répétitions...pas des permutations

+1 je croyais qu'il voulait faire des combinaisons avec remise. Je l'avais fait, je viens de le retrouver, il est basé sur celui que j'avais mis sur dvp.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void faire_combi(char * str, char * tmp, int len, int ind) {
  int i;
  
  if (ind >= len) {
    printf("%s\n", tmp);
    return;
  }
  
  for (i = 0; i < len; i++) {
    if (str[i] == -1)
      continue;
    tmp[ind] = str[i];
    str[i] = -1;
    faire_combi(str, tmp, len, ind+1);
    str[i] = tmp[ind];
  }
}

void combinaisons(char * str) {
  int len = strlen(str);
  char * tmp = calloc(len + 1, sizeof(char));
  char * util = calloc(len + 1, sizeof(char));
  strcpy(util, str);
  
  faire_combi(util, tmp, len, 0);
  
  free(tmp);
  free(util);
}

int main(void) {
  char str[] = "012";
  combinaisons(str);
  return 0;
}

thiblt04

26 avril 2010 à 22:30:37

Citation

Citation

Indice vaut toujours 0

Pourquoi? quand je lance f(indice+1,plaque) le "nouvel indice" est bien incrémenté non?

Désolé, j'avais mal compris comment tu faisais...

Mais appeler une fonction dans cette même fonction, c'est un peu le principe du goto sauf que c'est en infini et que ca plante...

Anonyme

27 avril 2010 à 9:46:05

Si tu étais en C++, il y a std::next_permutation qui fait exactement ce que tu veux

henri27

27 avril 2010 à 12:50:48

Bonjour
Je viens d'exécuter ton code et je n'ai pas de boucle infini.
C'est long mais ça s'arrête.
Par contre en plaçant un compteur, on s'aperçoit que ton programme sort des doublons.
Pour moi, ça vient de l'affichage

printf("%s\n",plaque);

.
Ta boucle for envisage le cas d'une permutation identité quand i = indice, par conséquent quand tu appelles f(indice+1...) tu vas de nouveau afficher la même combinaison.
Je te propose d'afficher seulement quand tu a effectué 8 permutation.
Ce qui donne :

#include <stdlib.h>
#include <stdio.h>

void f(int indice, char plaque[]) // L'indice représente la position de la lettre que l'on traite
{
    int i;
    char mem;
    static int it = 1;

    if(indice == 8)
    {
        printf("%s %d\n",plaque, it++);
        return;
    }

    for(i=indice;i<9;i++) //On boucle pour mettre chacune des 9 lettres en position "indice"
    {
        mem=plaque[indice];
        plaque[indice]=plaque[i];
        plaque[i]=mem;


        f(indice+1,plaque); //On recommence avec la position "indice+1"

        mem=plaque[indice];
        plaque[indice]=plaque[i];
        plaque[i]=mem;

    }
}

int main()
{
    char plaqueini[100];

    printf("Donnez les 9 lettres : ");
    scanf("%s",plaqueini);

    f(0,plaqueini);


    return 0;
}

Explications :

```
if(indice == 8)
{
    printf("%s %d\n",plaque, it++);
    return;
}
```
si indice = 8, on a effectué 8 permutations donc on affiche et c'est tout

for(i=indice;i<9;i++) //On boucle pour mettre chacune des 9 lettres en position "indice"
    {
        mem=plaque[indice];
        plaque[indice]=plaque[i];
        plaque[i]=mem;


        f(indice+1,plaque); //On recommence avec la position "indice+1"

        mem=plaque[indice];
        plaque[indice]=plaque[i];
        plaque[i]=mem;

    }

La c'est ton code à une chose près. Avec les trois dernières lignes, je suis sûr d'obtenir toutes les combinaisons. En simple, pour un même indice, une permutation n'affectera pas la suivante. Je ne sais pas si, sans ces lignes, on obtient toujours toutes les combinaisons ou non, c'est à vérifier

La variable statique est là pour compter le nombre d'affichage

casus_orez

27 avril 2010 à 17:51:54

eh oui! En fait je ne remettais pas la plaque "en l'état" après l'avoir envoyée à la fonction... J'avais déjà fait cette erreur dans un algo de backtrack pour le solveur de sudoku! Je me damnerai de 100 coups de fouet...

En tout cas merci à tous pour vos réponses!
Bonne fin de journée

LeffeLambert

12 mai 2019 à 14:37:47

Nabnav