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

[prgasp77]

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.




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

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

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

[pseudocode]

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.

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 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
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;
}

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

[lovelace63]

Je suis encore en train de travailler sur ce problème.
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 :

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