LPNHE - UMR 7585 - permutations et appel récursif

Aller au menu
Aller à la recherche
Aller au contenu
Aller à la navigation

Partenaires

Rechercher

Accueil > Le LPNHE > Pages du personnel permanent > Beau Tristan > Divers > Vielleries > permutations et appel récursif

permutations et appel récursif

15 septembre 2005

par Tristan Beau - 18 mai 2017

Voici un code utilisant une fonction récursive.
En entrée standard, donnez des lettres (par exemple).
Le programme vous fournira en sortie toutes les permutations possibles des caractères entrés. La limitation du nombre de caractères possibles est donné par la constante IMAX ; cela fait tout de même 20 != 2 432 902 008 176 640 000 possibilités...

lancement :

$ gcc perm.c

$ echo "abcd" | ./a.out

#include <stdio.h>
#include <strings.h>

#define IMAX 20

void rec(char* base, int nb, char* toperm, int np) {
 
 int i,j,k;
 char p[IMAX];
 bzero(p,IMAX);

 if ( !np ) {
    base[nb]=0;
    printf("%s\n",base);
    return ;
  }
  
  for(i=0;i<np;i++) { 

     for(j=0,k=0;j<np;j++) 
       if (j!=i) p[k++]=toperm[j];

     base[nb] = toperm[i];
     rec(base,nb+1,p,np-1);
  }

  return ;
}

int main ( ) {

  char c;
  int  i=0;
  char t[IMAX];
  char b[IMAX];  
  
  bzero(t,IMAX); bzero(b,IMAX);  

  while ( (c=getchar()) != EOF && i<IMAX ) {
    if ( c != '\n' ) {
      t[i]=c;
      i++;
    }
  }

  rec(b,0,t,i);

  return 0;
}

Dans la même rubrique :

Partenaires

Menu

Rechercher

Navigation

permutations et appel récursif