Publicité
+ Répondre à la discussion
Affichage des résultats 1 à 8 sur 8
  1. #1
    Rédacteur/Modérateur
    Avatar de pseudocode
    Homme Profil pro Xavier Philippeau
    Architecte système
    Inscrit en
    décembre 2006
    Messages
    9 960
    Détails du profil
    Informations personnelles :
    Nom : Homme Xavier Philippeau
    Âge : 41
    Localisation : France, Hérault (Languedoc Roussillon)

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

    Informations forums :
    Inscription : décembre 2006
    Messages : 9 960
    Points : 15 081
    Points
    15 081

    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 :
    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 Xavier Philippeau
    Architecte système
    Inscrit en
    décembre 2006
    Messages
    9 960
    Détails du profil
    Informations personnelles :
    Nom : Homme Xavier Philippeau
    Âge : 41
    Localisation : France, Hérault (Languedoc Roussillon)

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

    Informations forums :
    Inscription : décembre 2006
    Messages : 9 960
    Points : 15 081
    Points
    15 081

    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 :
    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 945
    Détails du profil
    Informations personnelles :
    Localisation : Luxembourg

    Informations forums :
    Inscription : juin 2006
    Messages : 6 945
    Points : 8 774
    Points
    8 774

    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 :
    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 Xavier Philippeau
    Architecte système
    Inscrit en
    décembre 2006
    Messages
    9 960
    Détails du profil
    Informations personnelles :
    Nom : Homme Xavier Philippeau
    Âge : 41
    Localisation : France, Hérault (Languedoc Roussillon)

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

    Informations forums :
    Inscription : décembre 2006
    Messages : 9 960
    Points : 15 081
    Points
    15 081

    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 :
    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 Serge
    Inscrit en
    octobre 2004
    Messages
    349
    Détails du profil
    Informations personnelles :
    Nom : Homme Serge
    Localisation : France, Nord (Nord Pas de Calais)

    Informations forums :
    Inscription : octobre 2004
    Messages : 349
    Points : 126
    Points
    126

    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 :
    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

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

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

    Informations forums :
    Inscription : décembre 2006
    Messages : 9 960
    Points : 15 081
    Points
    15 081

    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.

Liens sociaux

Règles de messages

  • Vous ne pouvez pas créer de nouvelles discussions
  • Vous ne pouvez pas envoyer des réponses
  • Vous ne pouvez pas envoyer des pièces jointes
  • Vous ne pouvez pas modifier vos messages
  •