Matrice binaire et itérateur

[fatal_error]

hi all,

un problème surement classique?

Soit une matrice mxm (binaire)
pour simplifier, disons m=4.

posons la distance d avec M1 et M2 deux matrices mxm
d(M1,M2) = sum(|M1-M2|)
avec sum qui fait juste la somme de tous les coeffs
idem,
si M1==M2, d(M1,M2)=0
si M1(i,j)!=M2(i,j) alors on compte 1

e.g
M1 M2
101 100
001 010
000 001
d(M1,M2) = 0+0+1+0+1+1+0+0+1=4

Ce que je cherche:
On peut générer 2^16 matrices différentes.
Soit M_i, i=0 à N=2^16-1 la ième matrice générée
je veux construire la suite des M_i tq
sum_(i=0 à N-1) d(M_i, M_(i+1)) soit minimale

assez intuitivement, on veut minimiser le nombres de bits changés à chaque nouvelle matrice

[fatal_error]

Voilà ce que j'ai à proposer:

J'aurais tendance à considérer un set V où je stocke mes matrices visitées.
Puis une liste L où je stocke mes matrices "à visiter". Pour une position donnée j'ajoute mes 16 candidats pas dans V, ni déjà dans L, je dépile L et rebelotte. (ce qui me fait normalement et de proche en proche tout parcourir).

Je pense (à vérifier) avoir la distance minimale, mais la manière est pas très élégante... (à chaque fois vérifier dans un set de plus en plus grand

Peut être y a t-il une construction plus "astucieuse"

[fatal_error]

bon, une solution avec le https://en.wikipedia.org/wiki/Gray_code

[Ben314]

Salut,
Déjà, vu la distance que tu considère, que tes éléments soient des "matrices" n'apporte rien : ça serait de bêtes vecteur (ou tableaux) de 16 cases, ça serait exactement le même problème (*).
Et sinon, je suis quasi-certain d'avoir déjà rencontré le problème et qu'il y a une solution (relativement simple) où tu énumère tout les éléments en ayant une différence que de 1 bit d'un élément au suivant. Je regarde si je retrouve "le truc".

(*) Dit de façon théorique, si tu regarde uniquement comme un espace vectoriel, alors c'est exactement la même chose que . LA différence, c'est que le premier est aussi muni (naturellement) d'une structure multiplicative alors que le second non.

[Ben314]

C'est O.K. sur le principe (mais il faut réfléchir un peu pour une mise en place informatique...)

Mettons que, pour 3 bits, tu ait une énumération complète (et circulaire) par exemple celle là :
000 -> 010 -> 011 -> 001 -> 101 -> 111 -> 110 -> 100 (-> 000)
Alors, pour passer à 4 bits, tu écrit la même chose en rajoutant des 0 partout au début :
0000 -> 0010 -> 0011 -> 0001 -> 0101 -> 0111 -> 0110 -> 0100 -> . . .
puis tu change le 0 de début en 1 : et tu reprend la liste dans l'autre sens
. . . -> 1100 -> 1110 -> 1111 -> 1101 ->1 001 -> 1011 -> 1010 -> 1000
qui est de nouveau "circulaire" vu que 1000 -> 0000

EDIT : Et en fait, pour avoir "direct" une liste correcte, tu écrit les nombres 0,1,2,3,4,... (dans cet ordre) écrit en base 2 puis, pour chaque nombre, en partant de la gauche, à chaque fois que tu tombe sur une série de 1, tu garde le premier 1, tu change tout les (éventuels) 1 suivants de la série en 0 et tu change le (éventuel) 0 qui suit la série de 1 en 1.
0 = 0000 -> 0000
1 = 0001 -> 0001
2 = 0010 -> 0011
3 = 0011 -> 0010
4 = 0100 -> 0110
5 = 0101 -> 0111
6 = 0110 -> 0101
7 = 0111 -> 0100
8 = 1000 -> 1100
9 = 1001 -> 1101
. . .
010111000110111 -> 011100100101100

[fatal_error]

hi ben,

top!
la première approche capito

par contre la deuxième je n'arrive pas à montrer "comment" ca marche.
je me doute que la suite de 1 consécutifs addresse
11110 => 11111 (non encodé)
10001 => 10000 (seulement un bit modifié)
et
11111 => 100000
10000 => 110000 (seulement un bit modifié)

mais j'ai plus de mal à comprendre/montrer d'où sort le fait que le nombre encodé, ne répète pas un nombre déjà encodé (pour une autre valeur)