Combinaisons

Soyez le premier à donner votre avis sur cette source.

Snippet vu 8 278 fois - Téléchargée 35 fois

Contenu du snippet

Renvoi toutes les combinaisons de n booléens et toutes les combinaisons d'une chaine de caractère.

Algorythme :
Utilise le fait que les combinaisons d'un octets (en binaire évidemment) sont les chiffres en base 10 de 0 à 255

Code :
Deux fonctions : une qui travaille sur des booléens et une sur des chaînes de caractère.
+des fonctions d'affichage et de test

Source / Exemple :


class combinaisons{
 //renvoi toutes les combinaisons de t booléens
 static boolean[][]Combinaisons(int t){//t=taille de la chaine
     boolean[][]comb=new boolean[(int)Math.pow(2,t)][t];
     for(int i=0;i<comb.length;i++){
      int a=i;
      for(int j=comb[0].length-1;j>=0;j--){
       if(a%2==1){
        comb[i][j]=true;
        a=(int)(a/2);
       }
       else{
        a/=2;
       }
      }
     }
     return comb;
    }
    
    //renvoi toutes les combinaisons d'une chaine de caractère
    static char[][] Combinaisons(String mot){
     int longueur=mot.length();
  int nbr=(int)Math.pow(2,longueur);//nbr=nombre de combinaisons
     char[][] comb=new char[nbr][longueur];
     int k=0;
     for(int i=0;i<nbr;i++){
      k=i;
      for(int j=longueur-1;j>=0;j--){
       if(k%2==0){
        k/=2;
       }
       else{
        comb[i][j]=mot.charAt(j);
        k/=2;
       }
      }
     }
     return comb;
    }
    static void afficher(char[][] a){
     for(int i=0;i<a.length;i++){
      for(int j=0;j<a[0].length;j++){
       System.out.print(a[i][j]);
      }
      System.out.println();
     }
    }
    static void afficher(boolean[][] a){
     for(int i=0;i<a.length;i++){
      for(int j=0;j<a[0].length;j++){
       System.out.print(a[i][j]);
      }
      System.out.println();
     }
    }
    public static void main(String[]adrien){
     afficher(Combinaisons(5));
     afficher(Combinaisons("abcd"));
    }
}

Conclusion :


Remarques :
Remplacez les tableaux par des listes si vous ne voulez pas de blanc dans les combinaisons.
Ne dépassez pas la capacité du type primitif utilisé !!!
  • ne marche pas pour les mots de plus de n lettres :
  • n tq : 2^n=capacité du type
  • pour les byte n=1*8=8
  • pour les short n=2*8=16
  • pour les int : n=4*8=32
  • pour les long : n=8*8=64


Signature :
Le danseur de Java qui fume des Caml

A voir également

Ajouter un commentaire Commentaire
Messages postés
10
Date d'inscription
mercredi 18 mai 2005
Statut
Membre
Dernière intervention
24 juillet 2008

Je cherchais à faire plus ou moins la même chose ... :-)


import java.util.Vector;
import java.util.Enumeration;

public class Combinaisons{

/**
* La fonction java.lang.Long.toBinaryString(long value) retourne
* la valeur passée en argument sous la forme d'une chaine de
* caractères (formee de bits : 0 ou 1) représentant un nombre binaire (base 2).
* Pour notre utilisation, il est nécessaire de compléter ce nombre
* par la gauche avec un nombre précis de zéros tel que :
* [Nombre de zéros complémentaires]=[Nombre total d'élements]-[Nombre de bits dans le nombre]
*/
private static String completerParDesZeros(String str, int nbreChiffres){
StringBuffer buffer=new StringBuffer(str);
for(long diff=nbreChiffres-buffer.length();diff>0;diff--) buffer.insert(0,"0");
String tmp=buffer.toString();
buffer=null;
return tmp;
}

/**
* La fonction compte et retourne le nombre de bits à 0 dans le
* nombre binaire passé en argument sous la forme d'une chaine de caractères.
*/
private static int nombreDe0(String binaire){
int compteur=0;
for(int i=0;i000 1->001 2->010 3->011 4->100 5->101 6->110 7->111
*
* transforme cette valeur en binaire; ensuite, si le nombre de bits à 1 est égal au nombre d'éléments demandé
* le masque est utilisé pour construire une combinaison.
*
* Comment ne plus filtrer la liste de toutes les combinaisons possibles de 0 à n éléments, mais bel et bien
* Génerer seulement les combinaisons de x éléments demandées???
*/
protected static Enumeration toutesLesCombinaisons(String listeElements, int nombreElementsDansCombinaison){
final int nbreElements = listeElements.length();
final double nbreLignes = Math.pow(2,nbreElements);

Vector vector= new Vector((int)nbreLignes);
long valeur=(long)nbreLignes-1L;

while(valeur>0){
String binaire=completerParDesZeros(Long.toBinaryString(valeur),nbreElements);
if(nombreElementsDansCombinaison==nombreDe1(binaire)){
String mot=remplacerChiffresParElements(binaire,listeElements);
vector.add(mot);
}
valeur--;
}
return vector.elements();
}

/**
* La méthode imprime sur la console le contenu de l'objet java.util.Enumeration
*/
protected static void lister(Enumeration enumeration){
while(enumeration.hasMoreElements()){
System.out.println((String)enumeration.nextElement());
}
}
/**
* Méthode principale
* @author REQUENA Ludwig
*/
public static void main(String[] args){
long dep1=System.currentTimeMillis();
try{
if(args.length==2) lister(toutesLesCombinaisons(args[0],Integer.parseInt(args[1])));
else System.exit(0);
}catch(OutOfMemoryError oomerr){
System.err.println("La methode a consomme trop de ressources");
}
long fin1=System.currentTimeMillis();
long diff1=fin1-dep1;
System.out.println("nouvelle methode executee en : "+diff1+" millisecondes.");
}

}

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.