Discussion :

[rtg57]

Bonjour,

Attention ceci n'est pas un devoir scolaire, j'ai passé l'âge

Quelqu'un aurait-il une idée pour réaliser un algorithme qui opère un balayage de bits comme dans de l'illustration ci-dessous ?


Ou comme dans celle-ci:


Remarque importante: l'ordre de déplacement des bits n'a pas d'importance.
L'objectif est de garantir que toutes les combinaisons possibles sont réalisées.
J'ai dessiné ce tableau pour avoir une idée visuelle des combinaisons possibles.
Sauf que la réalisation des combinaisons dans cet ordre n'est pas facile...

Il y a peut être une autre progression à imaginer...
Cet algorithme doit pouvoir fonctionner en partant de différentes configurations ayant plus ou moins de bits 'forts' allumés, pour les descendre vers leur position faible.
Par exemple:
0000 0000 0011 1111 0000 0000 0000 0000

deviendra:
0000 0000 0000 0000 0000 0000 0011 1111

Merci de votre attention.

[mathieu]

dans la 1re image vous cherchez les nombres avec 2 bits à 1. et dans la 2e image, il s'agit de 3 bits à 1.
est ce que ça fait partie du même traitement qui continue jusqu'à 8 bits à 1 ou alors il s'agit de 2 traitements différents ?

[WhiteCrow]

Bonjour,

il y a différentes manières d'approcher le problème.

On peut dans un premier temps voir le problème comme déplacer 1 bit pour avoir la configuration suivante. Ici un algorithme possible est relativement simple et consiste schématiquement à scanner les bits de droite à gauche, compter ceux qu'on ne peut déplacer d'une position à droite. Si on tombe sur un bit déplaçable on le déplace, on ajoute à sa suite le nombre de bits indéplaçables on fait ce qu'on veut et on recommence. Si on ne trouve aucun bit déplaçable c'est que toutes les combinaisons ont été scannées. Le premier mot étant celui ayant tous les bits calés à gauche.

Exemple : si on part de 1100 on aboutit successivement à 1010, 1001, 0110, 0101 et 0011 qui ne comporte plus de bits déplaçables.

On peut également approcher ce problème sous l'angle des indices des bits positionnés. Par exemple 11100 correspond à (5,4,3). On utilisera un algorithme similaire au précédent.

Une source très intéressante est le TAOCP de Knuth, Volume 4 Fascicule 3a Generating all combination.

[rtg57]

Bonjour,

merci à vous deux pour l'intérêt que vous portez à mon problème.

Pour Mathieu: Les 2 tableaux représentent des traitements différents, j'aurai pu le préciser.
Dès que tous les bits ont atteint 'le bord droit', le traitement est terminé.

Pour WhiteCrow: Merci pour le lien, je ne connaissais pas et je sens que cet ouvrage va me passionner.

Je laisse ouvert la discussion, au cas où il y aurait d'autres suggestions...

@ bientôt...

[tbc92]

Apparemment, tu veux quelque chose qui fonctionne sur un tableur. Et en première colonne, tu as les nombres de 1 à ... disons 1000.
Tu peux ajouter une colonne, avec cette formule : =base(A1,2;32) et tu reproduis sur les lignes suivantes. Le 2 veut dire qu'on veut compter en base 2, donc uniquement avec des 0 et des 1, et le 32 veut dire qu'on veut 32 chiffres, donc on complète avec plein de 0 à gauche.
J'ai testé sur OpenOffice, j'imagine que ça marche aussi sur Excel.
Et ensuite, c'est visuel, tu constates qu'on n'a plus qu'à faire un substr().

Si tu n'as pas la 1ère colonne avec les n° de 1 à 1000, et si tu ne veux pas l'ajouter, si tu ne veux ajouter de colonne avec cette formule =base(...), ça se gère, c'est juste un peu plus compliqué.

[mathieu]

si on regarde les lignes 8 à 28 du traitements à 2 bits, on voit que ces les lignes se répètent dans le traitement à 3 bits avec un bit en plus dans la colonne 7 et ensuite un bit dans la colonne 6, etc.
donc je pense que vous pouvez faire cela avec une fonction récursive.
est ce que le langage de programmation donne la possibilité d'utiliser un cache ? ça permettrai d'avoir un algorithme simple et rapide en même temps.

[rtg57]

Bonjour à tous,

j'ai oublié de dire que cela ne se passe pas dans un tableur.
C'est juste une illustration 'visuelle' de ce que je cherche à obtenir avec un traitement de bits dans une variable informatique.

@mathieu:
Effectivement, on voit que les trames se répètent.
C'est d'ailleurs la raison pour laquelle je me suis fait une représentation visuelle dans un tableau...
C'était pour essayer de 'voir' s'il y a quelque chose de récurrent qui apparaît...

Mais bon... la constatation étant faite... quel algorithme permettrait d'atteindre ce fonctionnement ?
J'ai aussi pensé à une fonction récursive... mais la question ci-dessus reste d'actualité.

J'ai pensé aussi à faire des superpositions d'entier 32 bits indépendants genre:

................. 0010 0000
OU LOGIQUE 0001 0000
OU LOGIQUE 0000 1000
ce qui donne 0011 1000

et à gérer le décalage vers la droite selon une synchronisation finement opérée...
Mais cela reste complexe à traiter, surtout si l'on doit s'occuper d'un cas où il y a 16 bits à traiter du genre
0000 1111 1111 1111 1111 0000 0000 0000

pour arriver à
0000 0000 0000 0000 1111 1111 1111 1111

en passant par toutes les combinaisons

J'ai aussi traduit les valeurs binaires en valeurs décimale afin de chercher une suite logique dans la progression des nombres... Aucune logique apparente !




Merci

[mathieu]

j'ai l'impression que WhiteCrow tient quelque chose qui consomme moins de ressources que ma fonction mais je n'ai pas tout compris.

on ajoute à sa suite le nombre de bits indéplaçables on fait ce qu'on veut et on recommence.

quand j'ai lu "on fait ce qu'on veut", j'ai compris que je pouvais me lever et préparer le repas de ce soir mais ça ne fait pas avancer la question

Exemple : si on part de 1100 on aboutit successivement à 1010, 1001, 0110, 0101 et 0011 qui ne comporte plus de bits déplaçables.

là je n'ai pas compris le passage de "1001" à "0110".

[AbsoluteLogic]

Ce problème est un cas particulier du problème suivant:
>>> Lister tous les tuples de N valeurs entre xMin et xMax tel que la somme des valeurs fasse S.
Dans le cas des bits, on a xMin=0 et xMax=1. Et pour l'exemple demandé initialement, on a N=8 et S=2 ou 3.

Je présente l'algorithme récursive pour le problème général, pour être plus "pédagogique" (mais quand même en Python pour permettre aux gens, dont moi, de tester rapidement si ils veulent):

Code python :

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
def iterate_on_sequences_with_sum(xMin, xMax, N, S, X=[]):
    """
    :param xMin: valeur minimale d'un élément de la séquence
    :param xMax: valeur maximale d'un élément de la séquence
    :param N: nb de valeurs à rajouter dans la séquence
    :param S: somme voulue des valeurs qui restent à rajouter
    :param X: séquence qu'on a construit jusque là, à laquelle il manque N valeurs
    """
    if N == 0: # Terminaison de la récursivité
        yield X # On a rajouté tous les éléments pour atteindre notre somme, on s'arrête.
        return
    # On appelle récursivement avec un nouvel élément.
    # Le nouvel élément à rajouter doit être entre xMin et xMax, mais doit être cohérent avec ce qu'il restera à rajouter
    xStart = max(xMin, S - (N - 1) * xMax) # On ne veut pas rajouter une valeur trop petite, qu'on ne pourrait pas conpenser même en rajoutant que xMax après
    xEnd = min(xMax, S - (N - 1) * xMin) # On ne veut pas rajouter une valeur trop grande, qu'on ne pourrait pas conpenser même en rajoutant que xMin après
    for x in range(xStart, xEnd + 1): # Pour toutes les valeurs possibles de l'élément à rajouter (entre xStart en xEnd inclus)
        # On ajoute l'élément et on actualise les paramètres pour l'appel récursif
        for Xresult in iterate_on_sequences_with_sum(xMin, xMax, N - 1, S - x, X + [x]):
            # On liste les séquences obtenues par appels récursifs
            yield Xresult

A noter que j'ai utilisé la notion d'itérateur parce que c'est ce qui est le plus approprié en Python, mais de manière générale, on peut directement "traiter" chaque séquence trouvée, ou les enregistrer dans une liste.

Résultat dans le cas des bits:

Code python :

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
 
for X in iterate_on_sequences_with_sum(xMin=0, xMax=1, N=8, S=2):
    print(X)
 
[0, 0, 0, 0, 0, 0, 1, 1]
[0, 0, 0, 0, 0, 1, 0, 1]
[0, 0, 0, 0, 0, 1, 1, 0]
[0, 0, 0, 0, 1, 0, 0, 1]
[0, 0, 0, 0, 1, 0, 1, 0]
[0, 0, 0, 0, 1, 1, 0, 0]
[0, 0, 0, 1, 0, 0, 0, 1]
[0, 0, 0, 1, 0, 0, 1, 0]
[0, 0, 0, 1, 0, 1, 0, 0]
[0, 0, 0, 1, 1, 0, 0, 0]
[0, 0, 1, 0, 0, 0, 0, 1]
[0, 0, 1, 0, 0, 0, 1, 0]
[0, 0, 1, 0, 0, 1, 0, 0]
[0, 0, 1, 0, 1, 0, 0, 0]
[0, 0, 1, 1, 0, 0, 0, 0]
[0, 1, 0, 0, 0, 0, 0, 1]
[0, 1, 0, 0, 0, 0, 1, 0]
[0, 1, 0, 0, 0, 1, 0, 0]
[0, 1, 0, 0, 1, 0, 0, 0]
[0, 1, 0, 1, 0, 0, 0, 0]
[0, 1, 1, 0, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 0, 0, 1]
[1, 0, 0, 0, 0, 0, 1, 0]
[1, 0, 0, 0, 0, 1, 0, 0]
[1, 0, 0, 0, 1, 0, 0, 0]
[1, 0, 0, 1, 0, 0, 0, 0]
[1, 0, 1, 0, 0, 0, 0, 0]
[1, 1, 0, 0, 0, 0, 0, 0]

[Galet]

Bonjour,
Autre proposition, pour rester sur la piste de WhiteCrow :
- Compter le nombre de bits à 1, pour calculer la valeur finale ((2^(n+1))-1
- Rechercher de Droite à gauche la première séquence 10
- La partie de Droite en incluant les 2 bits sera appelée Reste, la partie de Gauche : Base
- A ajouter à Base, toute les divisions de Reste par 2 (inversion des 2 bits : 10 => 01) jusqu'à atteindre 1
Effectuer cette fonction jusqu'à ce qu'il ne reste plus de séquence 10 (le nombre est alors identique à la valeur finale)
Un fonction récursive devrait être possible...
Bien l'bonjour,

[WhiteCrow]

j'ai l'impression que WhiteCrow tient quelque chose qui consomme moins de ressources que ma fonction mais je n'ai pas tout compris.
quand j'ai lu "on fait ce qu'on veut", j'ai compris que je pouvais me lever et préparer le repas de ce soir mais ça ne fait pas avancer la question

là je n'ai pas compris le passage de "1001" à "0110".

Knuth l'expliquera bien mieux que moi mais :
«on fait ce qu'on veut» signifie simplement on fait ce qu'on a faire avec cette combinaison … peut importe le traitement qu'on a faire, on le fait.

Quand on est sur 1001, on commence à scanner à partir de la droite, le premier 1 ne peut être déplacé à droite, on continue le scan en gardant «1 bit non déplaçable», on passe le premier 0 et le second 0 avant d'arriver sur un 1 ; on le décale à droit et on rajoute 1 un à sa droite (car on a rencontré un bit non déplaçable) on arrive donc à 0110.

[mathieu]

merci pour ces précisions, j'avais mal compris "on ajoute à sa suite le nombre de bits indéplaçables". j'ajoutais les chiffres comme dans une chaine de caractères alors que vous parliez d'une addition.

j'ai réessayé cette algorithme pour 3 bits à 1 sur une longueur de 6 et je n'y arrive pas :

Code latex :

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
543210 <- numéro de bits
 
111000
110100
110010
110001
101010 <- pour écrire cette ligne, j'ai compté 1 bit indéplaçable (b0) ensuite j'ai déplacé b4 en b3 et j'ai additionné 1.
 
donc à partir de là, j'ai loupé la combinaison 101100.
 
et ensuite j'ai ça qui n'est peut être pas correct non plus
101001
100101
100011
010101
010011
001101
001011
000111