p
u
b
l
i
c
i
t
é
publicité
  1. #1
    Rédacteur/Modérateur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    décembre 2006
    Messages
    9 957
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 42
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : décembre 2006
    Messages : 9 957
    Points : 15 790
    Points
    15 790

    Par défaut [java] Permutations et Combinaisons

    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 : 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
    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)
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  2. #2
    Rédacteur/Modérateur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    décembre 2006
    Messages
    9 957
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 42
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : décembre 2006
    Messages : 9 957
    Points : 15 790
    Points
    15 790

    Par défaut Permutations

    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 : 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
    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);
    }
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  3. #3
    bruce-willis
    Invité(e)

    Par défaut

    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?

  4. #4
    Rédacteur/Modérateur

    Avatar de millie
    Profil pro
    Inscrit en
    juin 2006
    Messages
    6 943
    Détails du profil
    Informations personnelles :
    Localisation : Luxembourg

    Informations forums :
    Inscription : juin 2006
    Messages : 6 943
    Points : 9 795
    Points
    9 795

    Par défaut

    Citation Envoyé par bruce-willis Voir le message
    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 : 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
        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(", ");
            }
        }
    Je ne répondrai à aucune question technique en privé

  5. #5
    Rédacteur/Modérateur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    décembre 2006
    Messages
    9 957
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 42
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : décembre 2006
    Messages : 9 957
    Points : 15 790
    Points
    15 790

    Par défaut

    Citation Envoyé par bruce-willis Voir le message
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    import java.util.Arrays;

    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  6. #6
    Membre habitué
    Homme Profil pro
    Inscrit en
    octobre 2004
    Messages
    352
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Nord (Nord Pas de Calais)

    Informations forums :
    Inscription : octobre 2004
    Messages : 352
    Points : 140
    Points
    140

    Par défaut

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

  7. #7
    Invité de passage
    Inscrit en
    octobre 2008
    Messages
    5
    Détails du profil
    Informations forums :
    Inscription : octobre 2008
    Messages : 5
    Points : 1
    Points
    1

    Par défaut Approche non récursive

    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
      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 : 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
      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 : Sélectionner tout - Visualiser dans une fenêtre à part
      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

  8. #8
    Rédacteur/Modérateur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    décembre 2006
    Messages
    9 957
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 42
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : décembre 2006
    Messages : 9 957
    Points : 15 790
    Points
    15 790

    Par défaut

    Citation Envoyé par Aliasse Voir le message
    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)
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

Discussions similaires

  1. Permutation et combinaison
    Par shayw dans le forum Contribuez
    Réponses: 0
    Dernier message: 23/03/2012, 14h15
  2. Problème (Permutation?) pour générer des combinaisons
    Par diendjao dans le forum Général Algorithmique
    Réponses: 9
    Dernier message: 08/10/2008, 10h25
  3. combinaison de java et c++
    Par afnane dans le forum Interfaces Graphiques en Java
    Réponses: 2
    Dernier message: 12/09/2008, 19h58
  4. permutations/combinaisons sur des tableaux dynamiques
    Par pEAk230 dans le forum Langage
    Réponses: 5
    Dernier message: 19/04/2006, 13h18

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo