ensemble des partiesRésolu

Question

Bonjour à  tous ;
je cherche un algorithme qui me permet de renvoyer l'ensemble de partie .

par exemple :

input:{a,b,c}
output:ensemble des parties={ vide, a,b,c,ab,ac,bc,abc}

cs_habbou · Accepted Answer

Bonjour vychnou; Merci a vous .J'ai trouvé la solution Voici la solution. et encord merci

class combinaisons{
//renvoi toutes les combinaisons de t booléens
staticboolean[][]Combinaisons(int t){//t=taille de la chaine
boolean[][]comb=newboolean[(int)Math.pow(2,t)][t];
for(int i=0;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
staticchar[][] Combinaisons(String mot){
int longueur=mot.length();
int nbr=(int)Math.pow(2,longueur);//nbr=nombre de combinaisons
char[][] comb=newchar[nbr][longueur];
int k=0;
for(int i=0;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;
}
staticvoid afficher(char[][] a){
for(int i=0;ilength;i++){
for(int j=0;jlength;j++){
System.out.print(a[i][j]);
}
System.out.println();
}
}
staticvoid afficher(boolean[][] a){
for(int i=0;ilength;i++){
for(int j=0;jlength;j++){
System.out.print(a[i][j]);
}
System.out.println();
}
}
publicstaticvoid main(String[]adrien){
afficher(Combinaisons(5));
afficher(Combinaisons("abcd"));
}
}

cs_vychnou · Answer

Euh j'avais fait ça en python, d'une manière "relativement" simple (je peux le poster si tu veux), sinon en java j'ai ce code à te proposer (il y a sans doute de meilleurs algorithmes): /** * Résoudre et afficher les résultats du pb pour un certain 'nb' * @param int nb : nombre de couple */ private static void resoudrePourNb(int nb) { // Constituer les nb lettres String [] nLettres = null; nLettres = new String[nb]; for (int i = 0; i < nb; i++) { nLettres [i] = i+""; } // Trouver les nb! combi String[][] combisPossibles = trouveCombis(nLettres); // Les compter et compter les OK float cpt = combisPossibles.length; float cptOk = 0; for (int i = 0; i < cpt; i++) { int j = 0; for (j = 0; j < combisPossibles[i].length && !combisPossibles [i][j].equals(j+""); j++) { } if (j < combisPossibles[i].length && combisPossibles [i][j].equals(j+"")) { cptOk++; } } // Afficher le résultat pour nb float pct = cptOk/cpt; System.out.println("Pour '" + nb + "', nb de combis OK / nb total " + cptOk + " / " + cpt + " " + pct + " %"); } /**/ private static String[][] trouveCombis(String[] lettres) { String[][] ret = null; int n = lettres.length; String[] tmp = new String[n]; int cpt = 0; if (n >= 1) { ret = new String[fact(n)][n]; if (n == 2) { ret[0] = lettres; tmp = new String[] {lettres[1], lettres[0]}; ret[1] = tmp; } else if (n < 2) { ret[0] = lettres; } else { for (int i = 0; i < lettres.length; i++) { String[] lettreSansI = enleveI(lettres, i); String[][] res = trouveCombis(lettreSansI); for (int j = 0; j < res.length; j++) { for (int k = 0; k < res[j].length; k++) { tmp[k] = res[j][k]; } tmp[n - 1] = lettres[i]; ret[cpt++] = tmp; tmp = new String[n]; } } } } return ret; } /** * Enlève la ième chaîne d'un tableau de chaîne * @param String[] tabStr * @param int i * @return String[] ret */ private static String[] enleveI(String[] tabStr, int i) { String[] ret = new String[tabStr.length - 1]; for (int j = 0; j < tabStr.length; j++) { if (j < i) { ret[j] = tabStr[j]; } else if (j > i) { ret[j-1] = tabStr[j]; } } return ret; } /** * Factorielle * @param int n * @return int ret */ private static int fact(int n) { int ret = 1; if (n > 1) { for (int i = 1; i <= n; i++) { ret = ret * i; } } return ret; } }

Ensemble des parties

2 réponses

Votre réponse

Discussions similaires