[java] Permutations et Combinaisons

[pseudocode]

Petit bout de code récursif pour calculer les combinaisons C(n,p) sans remise

Par exemple, pour p=3 et n=5 (0,1,2,3,4) on obtient:
[0,1,2] [0,1,3] [0,1,4] [0,2,3] [0,2,4] [0,3,4] [1,2,3] [1,2,4] [1,3,4] [2,3,4]

Code java :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
 
static int n = 5;
static int p = 3; 
static boolean ordered=true;
 
// liste construite par la recursion  
static int[] liste = new int[p];
 
// construction recursive des listes possibles
public static void partition(int index) {
	if (index>=p) {
		// la liste est construite -> FIN 
		System.out.println(Arrays.toString(liste));
		return;
	}
 
	// ajoute un nouvel element candidat dans la liste
	// - sans ordre -> candidat: tous les elements
	// - avec ordre -> candidat: seulement les elements supérieurs au précédant
 
	int start=0;
	if (ordered && index>0) start=liste[index-1]+1;
 
	for(int i=start;i<n;i++) {
		liste[index]=i;
		partition(index+1);
	}
}
 
public static void main(String[] args) {
	partition(0);
}

NB: en mettant la variable "ordered=false", on obtient la liste de tous les arrangements avec remise (= n^p possibilités)

[pseudocode]

Petit bout de code récursif pour calculer les permutations d'elements

Par exemple, pour size=3 on obtient:
[0, 1, 2], [0, 2, 1], [1, 0, 2], [1, 2, 0], [2, 0, 1], [2, 1, 0]

Code java :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
 
// taille de la liste à construire
static int size = 3; 
 
// table des elements utilisés 
static boolean[] elements = new boolean[size];
 
// liste construite par la recursion  
static int[] liste = new int[size];
 
// construction recursive des listes possibles
public static void permut(int rank) {
	if (rank>=size) {
		// la liste est construite -> FIN 
		System.out.println(Arrays.toString(liste));
		return;
	}
 
	// parcours les elements
	for(int i=0;i<size;i++) {
		// deja utilisé -> suivant
		if (elements[i]) continue;
		// sinon on choisi cet element
		elements[i]=true;
		// on l'ajoute a la liste
		liste[rank]=i;
		// on construit le reste de la liste par recursion
		permut(rank+1);
		// on libere cet element
		elements[i]=false;
	}
 
}
 
public static void main(String[] args) {
	permut(0);
}

J'ai l'erreur suivant avec ces codes alors que j'ai JDK 1.5.09

--------------------Configuration: Combinaison - JDK version 1.5.0_09 <Default> - <Default>--------------------
E:\Combinaison\src\Combinaison.java:26: cannot find symbol
symbol : variable Arrays
location: class Combinaison
System.out.println(Arrays.toString(liste));
^
1 error

Process completed.

Arrays.toString() n'est pas reconnu!!
Pourquoi?

[millie]

Envoyé par bruce-willis

J'ai l'erreur suivant avec ces codes alors que j'ai JDK 1.5.09

Arrays.toString() n'est pas reconnu!!
Pourquoi?

C'est pourtant OK depuis le JDK 1.5 d'après la doc.

Le contenu de la méthode est :

Code java :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
    public static String toString(int[] a) {
        if (a == null)
            return "null";
	int iMax = a.length - 1;
	if (iMax == -1)
            return "[]";
 
        StringBuilder b = new StringBuilder();
        b.append('[');
        for (int i = 0; ; i++) {
            b.append(a[i]);
	    if (i == iMax)
		return b.append(']').toString();
            b.append(", ");
        }
    }

[pseudocode]

Envoyé par bruce-willis

Arrays.toString() n'est pas reconnu!!
Pourquoi?

Sans doute parce que le package n'est pas inclu. J'inclus rarement les packages "usuels" dans mes contributions, pour clarifier le code.

Au début de ta classe, ajoute la ligne:

Code java :

import java.util.Arrays;

[senacle]

Pour ceux que ça intéresse, la version php : http://www.developpez.net/forums/d10...s/#post5735781

[Aliasse]

Je vous propose à travers ces quelques lignes une approche différente et non récursive pour calculer les combinaisons possibles pour un charset donné et une longueur n.
Les éléments nécessaires sont les suivants :

Code :

1
2
3
4
5
// Charset
private char[] _charset = "012345".toCharArray();
// Longueur max
private Integer _longueur = 8;

Voici grosso modo les grands traits de cette méthode :

• On calcule le nombre exact de combinaisons possibles à partir de la longueur et du charset proposé. Ceci grâce à une fonction qui ressemble à ça :
  
  Code :

  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  // Fonction qui calcule le nombre de combinaisons max pour un charset et une longueur données
  private Integer maxCombi (Integer charsetsize, Integer longueur) 
  {
      // Variable qui cumule les combinaisons possibles (par défaut = 0)
      Double max = 0.0;
  
      // Cumul pour toutes les longueurs possibles
      for (int j=1;j<=longueur;j++) 
     {
          max += Math.pow((double)charsetsize, (double)j);
      }
  
      return max.intValue();
  }

• On peut maintenant dans notre main (ou ailleurs) appeler cette fonction pour effectuer une itération maxCombi-fois, voici le code de l'appel :
  
  Code :

  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  public static void main(String[] args) 
  {
  	// Nombre de combinaisons possibles pour le charset _charset et la longueur _longueur définie plus haut
  	Integer nbCombinaison = maxCombi(_charset.length, _longueur);
  
          // Mot composé par la methode computeMot
          String mot = "";
  
          // Iteration sur la méthode computeMot
          for (int i=0;i<nbCombinaison;i++) 
          {
              mot = computeMot (_charset.length,i);
              System.out.println (mot);
          }
  }

• Il ne me reste maintenant plus qu'à expliquer mon approche pour calculer les combinaisons possibles. Celle-ci n'est pas vraiment simple mais vraiment efficace. Il suffit de partir du principe que l'on va manipuler des index depuis le _charset et que l'itération du main est en faite un parcours des indices. Techniquement on demande à chaque tour de boucle le mot indexé à la position i+1. Je ne suis pas vraiment fort pour les explications, voici plutôt le code :
  
  Code :

  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  private String computeMot (Integer charsetsize, Integer indice) 
  {
      // Mot à retourner (par défaut vide)
      String result = "";
  
      // Calcul du mot
      while (indice>=0) {
           result = _charset[(indice%charsetsize)] + result;
           indice = (indice/charsetsize) - 1;
      }
  
      return result;
  }

Voilà la méthode que je propose. Elle est basée sur un calcul de modulo à partir d'indice et sur la reconstruction du mot à trouver depuis ces indices calculés. Je ne suis pas vraiment pédagogue donc désolé si certains d'entres vous sont un peu perdu
J’essaierai de répondre aux questions si il y a des problèmes de compréhension ou d’exécution
Bien sur n'hésitez pas à donner votre avis, la méthode proposée n'est pas parfaite et peut surement être améliorée

[pseudocode]

Envoyé par Aliasse

JVoilà la méthode que je propose. Elle est basée sur un calcul de modulo à partir d'indice et sur la reconstruction du mot à trouver depuis ces indices calculés. Je ne suis pas vraiment pédagogue donc désolé si certains d'entres vous sont un peu perdu

Ca revient plus ou moins à compter en base N, ou N est le nombre d'éléments de l'ensemble. Le calcul via les modulo permet de convertir un nombre en base 10 en un nombre en base N.

Ensemble = {A,B,C,D}
i=54 (base 10) = 3*4² + 1*4 + 2*1 = 312 (base 4) ---> {D,B,C}

Il y a cependant une astuce dans la conversion qui introduit un biais et permet de distinguer les 0 non significatifs ("1" et "01" par exemple)