combinaison binaire en fonction d'un tableau java

Version imprimable

Bonjour,
En fait j'ai un tableau de taille indéfini qui contient des 1 ou des 0.
Exemple : table[]={1,1,1,1}
Sur cet exemple mon objectif est de générer tous les binaires dans cet ordre :
1000, 0100, 0010, 0001, 1100, 1010, 1001, 0110, 0101, 0011, 1110, 1101, 1011 et enfin 0111.

Exemple2 : table2[]={1,1,0,1}
Et sur celui ci on a un élement à 0 donc il ne faut pas les générer du coup ça donne:
1000, 0100, 0001, 1100, 1001, 0101, 1101.

A l'heure actuel je ne sors pas les bons résultats, et je ne tiens pas compte de la longueur du tableau.
Code:

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 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 public class Combinaison { int table[]={1,1,1,1}; int n = table.length; int[] table1 = new int[table.length]; public int numberOfOne(){ int numberOfOne=0; for (int i=0; i< table.length; i++) if(table[i] == 1) numberOfOne++; return numberOfOne; } public void combi(){ int loop = 0; while(loop <= numberOfOne()){ int count = 0; int t=0; for(int i=0; i < table.length ; i++) table1[i] = 0; for(t=0; t < table.length ; t++){ if(table[t] == 1){ table1[t] = 1; count ++; } if (count == loop) break; } while (t<table.length){ System.out.println(); for(int i=0; i < table.length ; i++) System.out.print(table1[i] + "\t"); table1[t] = 0; t++; while ( t < table.length && table[t] == 0 ) t++; if (t < table.length ) table1[t] = 1; } loop ++; } } public static void main(String[] args) { Combinaison c = new Combinaison(); c.combi(); } }
J'espère que vous pourrez m'aider.

18/04/2012, 16h12
prgasp77

Bonjour,
dans l’algorithme final, combien y aura-t-il de bits dans les éléments de sorties (dans l'exemple que tu donnes : 4) ?

cdlt,
18/04/2012, 17h08
lovelace63

Merci pour ta réponse.
Dans l'exemple j'ai un tableau de taille 4 avec les 4 bits à 1.
Au final l'algorithme devra fonctionner pour des tableaux de n'importe quelle taille avec n'importe quel nombre de 1.
En sortie je dois avoir toutes les combinaisons possibles (-2 car je ne veux pas le tout 0 et le tout 1) pour le tableau donné.

A priori, le test pour savoir si une valeur est valide est assez simple.

Ce qui semble compliqué c'est de générer toutes les combinaisons dans l'ordre avant de faire le test. Occupons nous donc déjà de cela:

Code:

1
2
3
4
5
6
7
8
9
int n=4;
MyBinaryArray value = new MyBinaryArray(n);
for(int numberOfOne=1; numberOfOne<n; numberOfOne++) {
	value.setFirstBits(numberOfOne);
	do {
		/* verifier ici si le contenu de 'value' est valide */
		System.out.println(value);
	} while(value.next());
}

Ce qui nous amène à créer la classe MyBinaryArray qui implémente le besoin:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class MyBinaryArray {
	int[] array;
	public MyBinaryArray(int nbbits) {
		array = new int[nbbits];
	}
	public void setFirstBits(int nb) {
		for(int i=0;i<array.length;i++)
			array[i]=(i<nb)?1:0;
	}
	public boolean next() {
		for(int i=array.length-1;i>0;i--)
			if (array[i]==0 && array[i-1]==1) {
				array[i]=1;	array[i-1]=0;
				return true;
			}
		return false;
	}
	@Override public String toString() {
		return Arrays.toString(array);
	}
}

résultat:

[1, 0, 0, 0]
[0, 1, 0, 0]
[0, 0, 1, 0]
[0, 0, 0, 1]
[1, 1, 0, 0]
[1, 0, 1, 0]
[1, 0, 0, 1]
[0, 1, 0, 1]
[0, 0, 1, 1]
[1, 1, 1, 0]
[1, 1, 0, 1]
[1, 0, 1, 1]
[0, 1, 1, 1]

Merci pseudocode :)
Ton code fonctionne presque pour n=4.
Normalement il me faut (2^n)-2 combinaisons, où n est le nombre de bits à 1.
Pour 4 je dois donc avoir 14 combinaisons, il en manque donc une.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
[1, 0, 0, 0]
[0, 1, 0, 0]
[0, 0, 1, 0]
[0, 0, 0, 1]
[1, 1, 0, 0]
[1, 0, 1, 0]
[1, 0, 0, 1]
 
manquant :
[0, 1, 1, 0]
 
reprise :
[0, 1, 0, 1]
[0, 0, 1, 1]
[1, 1, 1, 0]
[1, 1, 0, 1]
[1, 0, 1, 1]
[0, 1, 1, 1]

J'ai également analysé les résultats pour n=5 :

Code:

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
38
39
40
41
42
43
44
45
46
47
 
[1, 0, 0, 0, 0]
[0, 1, 0, 0, 0]
[0, 0, 1, 0, 0]
[0, 0, 0, 1, 0]
[0, 0, 0, 0, 1]
[1, 1, 0, 0, 0]
[1, 0, 1, 0, 0]
[1, 0, 0, 1, 0]
[1, 0, 0, 0, 1]
 
manquant :
[0, 1, 1, 0, 0]
[0, 1, 0, 1, 0]
 
reprise :
[0, 1, 0, 0, 1]
 
manquant :
[0, 0, 1, 1, 0]
 
reprise :
[0, 0, 1, 0, 1]
[0, 0, 0, 1, 1]
[1, 1, 1, 0, 0]
[1, 1, 0, 1, 0]
[1, 1, 0, 0, 1]
 
manquant : 
[1, 0, 1, 1, 0]
 
reprise :
[1, 0, 1, 0, 1]
[1, 0, 0, 1, 1]
 
manquant :
[0, 1, 1, 1, 0]
[0, 1, 1, 0, 1]
 
reprise :
[0, 1, 0, 1, 1]
[0, 0, 1, 1, 1]
[1, 1, 1, 1, 0]
[1, 1, 1, 0, 1]
[1, 1, 0, 1, 1]
[1, 0, 1, 1, 1]
[0, 1, 1, 1, 1]

18/04/2012, 22h09
kwariz

Salut,

par curiosité j'ai essayé de comprendre l'ordre des combinaisons, je suis arrivé (si il n'y a que des 1 dans le tableau d'origine) à la conclusion que les combinaisons sont triées selon :

* nombre de bit à 1, ascendant
* pour un même nombre de bits, ordre lexicographique en lisant de droite à gauche ascendant avec 0<1

Mais ça ne colle pas car pour [1,1,1,1] j'ai une différence (deux éléments échangés en gras):
1000, 0100, 0010, 0001, 1100, 1010, 0110, 1001, 0101, 0011, 1110, 1101, 1011, 0111

si on note ces combinaisons c(1) à c(2^n-2), même en rajoutant c(0)=0...0 et c(2^n-1)=1...1
on a la propriété : c(i)=!c(2^n-1-i)

Quel est l'ordre ? Je donne ma langue au chat :)

Citation:

Envoyé par kwariz

Quel est l'ordre ? Je donne ma langue au chat :)

Tout simplement, à nombre de 1 égal, c'est l'ordre naturel décroissant du nombre représenté en binaire.

:ccool:

Sinon une solution assez simple pour passer d'un élément A à l'élément suivant B est :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 vars: k un entier algo: pour k=1 à n faire si 0 <> A & 1<<k alors si 1 = k alors cas particulier LAL fin. fin si B = A - (1<<k) + (1<<k-1) fin. fin si fin pour fin.
LE tout avec &, <<, + et - les opérateurs respectifs bitwise and, logiccal left bit shift, integer addition, integer soustraction tels que définis en C (précédence notamment).

Cdlt,

18/04/2012, 22h35
kwariz

pfff ... qu'avais-je devant mes yeux ... en plus si évident ^^

En fait il s'agit de générer les k-combinaisons (k variant de 1 à n-1) d'un tableau avec n un par ordre décroissant ... j'ai fait un source (en c) qui résout ce problème (générer les k-combinaisons) si ça peut aider ... http://www.developpez.com/telecharge...e-combinaisons.

Citation:

Envoyé par lovelace63

Merci pseudocode :)
Ton code fonctionne presque pour n=4.
Normalement il me faut (2^n)-2 combinaisons, où n est le nombre de bits à 1.
Pour 4 je dois donc avoir 14 combinaisons, il en manque donc une.

Citation:

Envoyé par prgasp77

Tout simplement, à nombre de 1 égal, c'est l'ordre naturel décroissant du nombre représenté en binaire.

Arf. Effectivement j'avais mal lu le PO, je croyais que c'était un décalage d'un bit a chaque fois.

Patch:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 public boolean next() { int accu=0; for(int i=array.length-1;i>0;i--) { if (array[i]==0 && array[i-1]==1) { array[i]=1; array[i-1]=0; for(int j=1;j<=accu;j++) array[i+j]=1; return true; } if (array[i]==1) { array[i]=0; accu++; } } return false; }

19/04/2012, 08h29
lovelace63

Merci à tous ceux qui participe à la résolution de mon problème.

Le code de pseudocode fonctionne parfaitement dans le cas où on a que des 1. Comment dois je faire pour des tableaux qui contiennent également des 0?

Je suis encore en train de travailler sur ce problème. :cry:
Quand je n'ai que des 1 dans mon tableau initial alors cela fonctionne mais quand j'ai un 0 je ne sais pas quoi faire. J'essaye de sauter l'étape puisque je ne dois rien générer. Pour se faire je compte le nombre de 0 qui apparaisse mais après je ne sais pas quoi faire de mon compteur.

A l'heure actuelle j'ai avec un tableau de départ [1, 1, 0, 1], j'ai :
combinaison : [1, 0, 0, 0]
combinaison : [0, 1, 0, 0]
combinaison : [1, 1, 0, 0]

Il me manque toutes les combinaisons qui font intervenir le dernier 1, puisque au moment où je rencontre le premier 0 j'ai un problème.

En espérant que quelqu'un puisse m'aider.
Bonne journée
Code:

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 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 import java.util.Arrays; public class Test2 { // tableau initial static int[] array = {1, 1, 0, 1}; // on compte le nombre de 1 public static int nbOnes(){ int nbOnes = 0; for(int i=0; i<array.length; i++) { if(array[i] == 1) { nbOnes++; } } return nbOnes; } // on fixe les premiers bits public static void setFirstBits(int[] combi, int nbOnes) { int accu=0; for(int i=0;i<array.length;i++){ if((array[i]==1)&&(accu<nbOnes)){ combi[i]=1; accu ++; } else{ combi[i]=0; } } } // on cherche les autres public static boolean next(int[] combi) { int accu=0; // compteur pour décaler int ct=0; for(int i=combi.length-1;i>0;i--) { if (array[i]==0){ ct++; } if (array[i] == 1 && combi[i]==0 && combi[i-1]==1) { combi[i]=1; combi[i-1]=0; for(int j=1;j<=accu;j++) combi[i+j]=1; return true; } if (combi[i]==1) { combi[i]=0; accu++; } } return false; } public static void main(String Args[]){ System.out.println("tableau de départ : " + Arrays.toString(array)); int n = nbOnes(); for(int numberOfOne=1; numberOfOne<n; numberOfOne++) { int[] combi = new int[array.length]; setFirstBits(combi, numberOfOne); do { System.out.println("combinaison : " + Arrays.toString(combi)); } while(next(combi)); } } }
PS: j'ai une solution post génération