Discussion :

[Syarko]

Bonsoir,

J'ai un peu de mal à faire un exercice. Le but est de calculer toutes les combinaisons d'un ensemble donné. Ici, l'ensemble est tous les entiers de 1 à k.
Comme corps de la fonction, on nous donne ca :

Code :

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

1
2
3
4
 
private static void permutations(int[] p, int i) {
 
}

Cette methode doit être recursive. Lorsque on appelle cette fonction pour la première fois (c'est à dire dans une autre méthode), on rentre un tableau de int (ex: [1, 2, 3], et 0).

Le problème, c'est que je vois absolument pas comment faire. A chaque fois, j'ai une piste, mais soit elle n'est pas implementable de ce cas là, ou soit ca rend un resultat faux. Donc avez vous des pistes qui pourraient me guider sur la bonne voie ?

Merci

[joel.drigo]

Salut,

Dis-toi que les permutations d'un ensemble[i₀, i₁, i₂...in], ce sont :

• des tableaux ;
  
  • certains ont pour premier élément i⁰,suivi des autres éléments dans tous les ordres possibles;
  • certains autres ont pour premier élément i₁, suivi de tous les autres éléments dans tous les ordres possibles,
  • puis i₂, suivi de tous les autres éléments dans tous les ordes possibles...
  • ...i_n suivi des autres dans tous les ordres possibles... ;
  • tous les autres éléments dans tous les ordres possibles peut être dit autrement : les permutations des autres éléments.

[Syarko]

Je suis d'accord pour ça. Moi je ne vois pas comment l'implémenter avec seulement comme paramètre un tableau de int représentant tous les éléments de l'ensemble et un int représentant je suppose le niveau auquel on se trouve. Surtout que l'on peut même pas enlever un éléments de tableau pour dire qu'il a été pris ou non. Car je ne comprends pas comment on peut faire pour savoir si on déjà utilisé un éléments de l'ensemble ou pas.

Merci

[joel.drigo]

Oui, je conçois que le tableau en paramètre peut être trompeur. En fait, le tableau on en a juste besoin pour stocker les valeurs que l'on va générer dans la récursion : on a pas besoin de le remplir avant le premier appel.

L'appel peut s'écrire comme ça :

Code :

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

1
2
3
4
5
6
7
8
9
public static void main(String[] args) {
 
   permutations(3); // ensemble de 1 à 3
 
}
 
public static void permutations(int k) {
   permutations(new int[k], 0);
}

Ensuite, il m'est difficile de donner l'algorithme en pseudocode, car il est tellement simple que c'est comme si je te donnais le code directement ou presque. Réfléchis un peu avant de regarder la solution : comment placer une valeur au début du tableau, et les permutations du reste par récursivité.

Code pseudocode :

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

1
2
3
4
5
6
7
8
9
10
 
permutations(p, i)
   si ( i>= p.length) afficher p
   sinon 
      pour index de 1 à p.length (inclus) 
         p[i]=index;
         permutation(p, i+1)
      finpour
   finsi
finpermutations

Je peux te donner un canevas pour te donner le début :

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
public static void main(String[] args) {
 
   permutations(3); // ensemble des valeurs de 1 à 3
 
}
 
public static void permutations(int k) {
   permutations(new int[k], 0);
}
 
private static void permutations(int[] p, int i) {
   if (i>=p.length) { // condition d'arrêt de la récursivité
      System.out.println(Arrays.toString(p));
   }
   else {
      /* ... */
   }
}

[Syarko]

J'ai peut être mal précisé mais c'est toutes les combinaisons sans repetitions. Par exemple pour 3, il me faut : (1,2,3) (1,3,2) (2,1,3) (2,3,1) (3,1,2) (3,2,1).
L'algo que tu m'as indiqué c'est pour toutes les combinaisons possible avec repetitions. C'est pour faire sans repetition que je coince, car je n'arrive pas à savoir comment on fait pour savoir si tel chiffre de l'ensemble a déjà été utilisé auparavant.
J'avais pensé à rajouter une deuxième boucle for dans la première pour verifier si le chiffre a déjà été utilisé. Ca ressemble à ca :

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
 
private static void permutations(int[] p, int i) {
    	boolean exist = false;
    	 if (i>=p.length) { // condition d'arrêt de la récursivité
    	      print(p);
    	 }
    	 else {
    	    for(int k = 1; k <= p.length; ++k) {
    	    	p[i] = k;
    	    	for(int j = 0; j < i; ++j){
    	    		if(p[i] == p[j])
    	    			exist = true;
    	    	}
    	    	if(!exist)
    	    		permutations(p, i+1);
    	    }
    	 }
	}

Mais ca ne fonctionne pas. Ca m'affice uniquement 3,2,1.

PS : La fonction print est une fonction qui permet d'afficher proprement le tableau.
Merci

[joel.drigo]

Ah oui, je vois.

Une solution évidente serait de faire (à peu de chose près ce que j'ai dit, mais au lieu de prendre les entiers de 1 à k, on permute les éléments du sous-tableau [i+1..k], et avec chaque [i] comment premier élément d'un tableau résultat :

Code :

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

1
2
3
4
5
6
7
8
private static void permutations(int[] p, int i) {
   for (int j = i; j < p.length; j++) { // on parcourt tous les éléments pour les avoir en premier élément du résultat
      swap(p, i, j); // on permute
      System.out.println(Arrays.toString(p));
      permutations(p, i+1); // on permute le reste du tableau
      swap(p, i, j); // on restaure le tableau
   }
}

Avec

Code :

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

1
2
3
4
5
private static void swap(int[] p, int i, int j) {
   final int val = p[i];
   p[i] = p[j];
   p[j] = val;
}

Mais comme tu pourras le voir, ça affiche plusieurs fois les mêmes combinaisons. Solution : trouver une condition pour afficher une fois chaque résultat. Pourquoi les résultats s'affichent plusieurs fois : parce qu'on permute i_i avec i_i (ça simplifie le code - il y'a peut-être une solution pour éviter ça en jouant sur les bornes de la boucle, ou en distinguant les cas par des méthodes différentes). Réflechis à cette condition (elle est simple).

Code :

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

1
2
3
4
5
6
7
8
9
10
private static void permutations(int[] p, int i) {
   for (int j = i; j < p.length; j++) {
      swap(p, i, j);
      if ( /** condition**/ ) { 
	 System.out.println(Arrays.toString(p));
      }
      permutations(p, i+1);
      swap(p, i, j);
   }
}

[Syarko]

Merci beaucoup !

Au final cela donne ca :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
 
private static void permutations(int[] p, int i) {
    	for (int j = i; j < p.length; j++) {
	      swap(p, i, j); 
	      if ( i == p.length-1) { 
	    	  print(p);
	      }      
	      permutations(p, i+1); 
	      swap(p, i, j);
    	}
}

J'avais pensé au swap. Mais j'avais pas pensé à en refaire un juste après la permutations.

Merci beaucoup pour ton aide. Je reviendrais avec plaisir sur ce forum si j'ai d'autres questions.

[joel.drigo]

Autre possibilité de condition : if (i!=j||j==0), qui colle plus à la logique. La duplication des combinaisons est due au fait qu'on parcourt l'ensemble du tableau et qu'on permute des éléments avec eux-même (donc cas à retirer, sauf pour i=0), ce qu'on est obligé de faire uniquement pour le premier (en changeant le bornage de la boucle, on obtient bien les combinaisons une fois, sauf qu'on obtient qu'une seule combinaison qui commence par 1).