retouver toute les combinaison

Version imprimable

22/03/2006, 13h15
sami_c

retouver toute les combinaison

J'ai une suite de 7 bits
Je voudrais avoir la combinaison complete de cette suite
Exp :
1101100
Combinaions :
1101101
1101111
1101011
...
Je pense que le nbr de résultat sera 7!
22/03/2006, 13h39
pcaboche
D'après ce que je comprends, à chaque fois tu changes un bit du résultat précédent.

La suite au complet serait donc:
1101100
_______
1101101
1101111
1101011
1100011
1110011
1010011
0010011

Pour cela, rien de plus simple:
Code:

1 2 3 4 5 6 7 8 bit = 1 ; pour i de 1 à 7 faire valeur := valeur ^ bit ; écrire(valeur) ; bit := bit << 1 ; fpour
Ici, les opérateurs utilisés sont ceux du C:
a ^ b => a XOR b (XOR bit à bit)
a << 1 => décalage de 1 bit vers la gauche (multiplication par 2 pour des entiers)
22/03/2006, 13h57
yoshï

Citation:

J'ai une suite de 7 bits
Je voudrais avoir la combinaison complete de cette suite
Exp :
1101100
Combinaions :
1101101
1101111
1101011
...
Je pense que le nbr de résultat sera 7!

bonjour,
je ne comprends pas bien la question...
S'agit il du nombre de combinaison (et donc de nombres représentables)
à l'aide de 7bits := 2^7=128 combinaisons.

ou bien s'agit il comme le dit pcaboche
du nombre de combinaison en changeant à chaque fois un bit du résultat précédent.Auquel cas le nombre de combinaison est simplement égal à 7

7!= nb de combinaison possible pour ordonner 7 entités
exemple
bit1 bit2 bit3 bit4 bit5 bit6 bit7
bit2 bit1 bit3 bit4 bit5 bit6 bit7
....
22/03/2006, 14h49
FrancisSourd

Pour plus d'info, tu peux regarder les codes de Gray.
22/03/2006, 15h00
pcaboche

Encore faut-il savoir exactement ce qu'il cherche à faire et quel résultat il attend. :koi:
22/03/2006, 15h12
sami_c

Citation:

Envoyé par yoshï

Citation:

J'ai une suite de 7 bits
Je voudrais avoir la combinaison complete de cette suite
Exp :
1101100
Combinaions :
1101101
1101111
1101011
...
Je pense que le nbr de résultat sera 7!

bonjour,
je ne comprends pas bien la question...
S'agit il du nombre de combinaison (et donc de nombres représentables)
à l'aide de 7bits := 2^7=128 combinaisons.

ou bien s'agit il comme le dit pcaboche
du nombre de combinaison en changeant à chaque fois un bit du résultat précédent.Auquel cas le nombre de combinaison est simplement égal à 7

7!= nb de combinaison possible pour ordonner 7 entités
exemple
bit1 bit2 bit3 bit4 bit5 bit6 bit7
bit2 bit1 bit3 bit4 bit5 bit6 bit7
....

j'aurais du ne pas sécher mes cours de proba :) en effet je cherche le nombre de combinaison à l'aide de 7 bits !

Citation:

Envoyé par yoshï

7! = nb de combinaison possible pour ordonner 7 entités
exemple
bit1 bit2 bit3 bit4 bit5 bit6 bit7
bit2 bit1 bit3 bit4 bit5 bit6 bit7
....

Pas forcément. Si on prend par exemple 1111111, quelle que soient les perfutations effectuées, on obtiendra toujours 1111111, donc on n'a qu'une seule solution.

Faire la liste de toutes les permutations possibles à partir d'une liste de bits revient en fait à faire la liste de tous les entiers ayant la même parité que l'entier de départ.

La parité, c'est le nombre de bits à '1' que compte l'entier.
ex: parite(1101100) = 4

Si l'ordre des combinaisons n'a pas d'importance, on peut procéder ainsi:

1) On génère un nombre avec tous les 1 d'un coté et tous les 0 de l'autre. On y arrive facilement en faisant 2^(par+1)-1 :
Code:

1 2 par := parite(nombre) valeur := (1<<(par+1))-1
En principe, pour nombre=01101100, on obtient valeur=00001111

2) On prend un bit dans les 0, un bit dans les 1 et on fait un XOR dessus (le 0 devient 1 et le 1 devient 0: c'est comme une permutation !)

On devrait obtenir quelque chose du genre:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 écrire(nombre) ; si (nombre <> 0) alors par := parite(nombre) ; valeur := (1<<(par+1))-1 ; pour i de par à 7 faire b := 1<<i + 1 ; pour j de i à 7 faire valeur := valeur ^ b ; écrire(valeur) valeur := valeur ^ b ; b := b<<1 ; fpour fpour fsi

bonsoir,

essayons de donner une solution à la question du début !

pour afficher toute les combinaison, une simple récursivitée suffit :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
Solution[1..7] // Un tableau qui contiendra servira à afifcher la solution
 
fonction(profondeur)
debut
 
     Solution[Profondeur] = 0 ;
     si profondeur < 7 alors fonction(profondeur+1) ;
     sinon Afficher Solution
 
     Solution[Profondeur] = 1 ;
     si profondeur < 7 alors fonction(profondeur+1) ;
     sinon Afficher Solution
fin
 
Et on appelle avec fonction(1) ;
 
Voilà pour ce qui est de la question d'origine.
 
En revanche, en binaire pour lister toutes les possibilités de combinaison, il y a 2^7 combinaisons.
[/quote]

Citation:

Envoyé par ToTo13

bonsoir,

essayons de donner une solution à la question du début !

pour afficher toute les combinaison, une simple récursivitée suffit :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
Solution[1..7] // Un tableau qui contiendra servira à afifcher la solution
 
fonction(profondeur)
debut
 
     Solution[Profondeur] = 0 ;
     si profondeur < 7 alors fonction(profondeur+1) ;
     sinon Afficher Solution
 
     Solution[Profondeur] = 1 ;
     si profondeur < 7 alors fonction(profondeur+1) ;
     sinon Afficher Solution
fin
 
Et on appelle avec fonction(1) ;
 
Voilà pour ce qui est de la question d'origine.
 
En revanche, en binaire pour lister toutes les possibilités de combinaison, il y a 2^7 combinaisons.

Plus simple:

Code:

1
2
3
pour i de 0 à 255
  afficher i
fpour

:lol:

22/03/2006, 21h09
ToTo13
Bonsoir,

petite modification à :

Citation:

pour i de 0 à 255
afficher i
fpour

peut etre plutot :
Code:

1 2 3 4 pour i=0 à i<2^7 faire afficher( ConvertionBinaire(i) ) ; fpour
C'est un peu plus générique et ca évitera d'avoir comme affichage :
0 1 2 3 .... 255 :wink: