combinaisons de 0et 1?

Version imprimable

01/04/2008, 22h56
cdoctora

combinaisons de 0et 1?

salut

je cherche une idée d'un algorithme qui génére les combinaisons des vecteurs de tailles données à partir de 0 et 1.
par exemple pour la longueur 2 je dois avoir les vecteurs suivants: 00,01,10,11
pour la longueur 3 je dois avoir les vecteurs suivants: 000,001,010,100,011,101,110,111
.....etc
merci d'avance
01/04/2008, 23h01
Alp

Une méthode possible mais assez lourde peut-être :
Tu fixes le premier à 0. Tu fixes le second à 0. Etc... jusqu'à N (la taille du vecteur).
Et en gros, tu vas choisir un ordre (soit en partant du premier, soit du dernier), et tu vas faire varier celui que tu as choisi. Et ainsi de suite jusqu'à tous les avoir fait varier. Mais dès que tu en modifies un, tu recalcules les combinaisons.

Pour ton problème il doit y avoir des algorithmes connus mais je ne connais pas leurs noms.
01/04/2008, 23h57
mr_samurai

Salut,
C'est pas simplement une question de base 2 ?

0 à 11..1 (n fois 1).
On connais deja la taille, base 10 de 11..1 + 1 .
02/04/2008, 09h41
ToTo13

Bonjour,

étant donné que tu veux toutes les combinaisons, tu peux faire une recherche récursive exhaustive.
Tu génères toutes les combinaisons.

Citation:

Envoyé par ToTo13

Bonjour,

étant donné que tu veux toutes les combinaisons, tu peux faire une recherche récursive exhaustive.
Tu génères toutes les combinaisons.

C'est meme possible en itératif:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
// compute next binary number
public static boolean next(int[] number) {
	int i=0;
	while(i<number.length && number[i]==1) number[i++]=0;
	if (i>=number.length) return false;
	number[i]=1;
	return true;	
}
 
// display all binary numbers of a given length
public static void main(String[] args) {
	int[] number = new int[]{0,0,0,0};  // 4 bits
	do {
		System.out.println( Arrays.toString(number) );
	} while(next(number));
}

Une version pour n'importe quelle base:

Code:

1
2
3
4
5
6
7
8
 
public static boolean next(int[] number, int base) {
	int i=0;
	while(i<number.length && number[i]==(base-1)) number[i++]=0;
	if (i>=number.length) return false;
	number[i]++;
	return true;	
}

Salut !

Tu peux commencer par générer une suite de nombres entiers de 0 à 2^N-1, puis les décortiquer. En Fortran, c'est assez simple grâce à l'instruction Equivalence et à la fonction BTest. L'exemple ci-dessous devrait t'inspirer.

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
C
C **********************************************************************
C
      Subroutine AS0112
C
C     Représentation d'une variable de type Integer*2
C
C **********************************************************************
C
C     Déclarations
C
      Implicit None
C
      Character*80 S
      Integer*2 I
      Integer*1 I1(2),K
      Equivalence (I1,I)
C
C **********************************************************************
C
C     Instructions exécutables
C
      Open (4,File='AS0112.txt')
   10 Write (*,*) ' '
      S='Tapez un entier entre -32768 et +32767'
	Call U003(S,Len_Trim(S))
	S='(Ctrl-Z pour quitter)'
	Call U003(S,Len_Trim(S))
	Read (*,*,End=99,Err=20) I
	Go To 30
C
   20	S='Donnée incorrecte'
      Call U003(S,Len_Trim(S))
	Go To 10
C
   30 Write (*,'(/11X,A)') 'Adr+1    Adr'
      Write (*,'(I7,3X,2(1X,8I1))') I,
     *  (-BTest(I1(2),K),K=7,0,-1),(-BTest(I1(1),K),K=7,0,-1)
      Write (4,'(/11X,A)') 'Adr+1    Adr'
      Write (4,'(I7,3X,2(1X,8I1))') I,
     *  (-BTest(I1(2),K),K=7,0,-1),(-BTest(I1(1),K),K=7,0,-1)
	Go To 10
C
   99 Close (4)
      Return
      End

Jean-Marc Blanc

02/04/2008, 22h16
cdoctora

salut
grace a vous réponse j'ai écrit mon programme qui répond a mes besoin
merci mes amis :zoubi:

Ceci n'est qu'un cas très particulier de l'ensemble des applications de E dans F où F={0;1} et E ensemble à un deux, trois ou n éléments.
Voici donc un tout petit pgm Python qui génère TOUTES les applications d'un ensemble dans un autre:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 # -*- coding: cp1252 -*- #générer toutes les applications de E dans F def power(n,F): G=[[x] for x in F] for i in range (0,n-1): G= [y+[x] for y in G for x in F] return G def main(): E=[1,2,3] F=['a','b'] print power(len(E),F) if __name__ == '__main__': main()
Ici il suffirait de prendre F=[0,1] dans main pour avoir tous les nombres binaires à 3 chiffres.

03/04/2008, 10h04
millie

C'était pas plus simple de faire une boucle sur 0 2^n, de convertir le nombre en binaire en le complétant pas des 0 pour que sa taille soit n ?

Ca tient en 3 lignes.