Discussion :

[lovelace63]

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 :

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

[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,

[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é.

[pseudocode]

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

Sélectionner tout - Visualiser dans une fenêtre à part

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

[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.

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

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

[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