Discussion :

[tania]

Si je te suis tes étapes :
1/ "codage binaire" de chaque ligne
a b d e f devient 1 1 0 1 1 1 0

2/puis de comparer les lignes 2 a 2 (c'est pas 1 à 1 ?)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
1 1 0 1 1 1 0
1 1 1 0 1 1 0
-------------
1 1 0 0 1 1 0

3/suite ok

C'est bien ce que tu veux dire ?
Si c'est ça, on devra faire une comparaison de chaque codage binaire, non ?

[pseudocode]

Si je te suis tes étapes :
1/ "codage binaire" de chaque ligne
a b d e f devient 1 1 0 1 1 1 0

oui. tu peux faire un codage binaire "pur" si ca tient sur un int/long (32/64 bits = 32/64 symboles)

2/puis de comparer les lignes 2 a 2 (c'est pas 1 à 1 ?)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
1 1 0 1 1 1 0
1 1 1 0 1 1 0
-------------
1 1 0 0 1 1 0

oui. ca fait C(2,nl) operations, avec "nl" le nombre de lignes. Cette partie de l'algo est parallelisable.

(on dit bien 2 a 2 dans ce cas... non ?)

3/suite ok

C'est bien ce que tu veux dire ?
Si c'est ça, on devra faire une comparaison de chaque codage binaire, non ?

Dans un langage digne de ce nom, tu as des operateurs qui manimulent les champs de bits, et qui te diront combien de bits sont a 1 dans un int/long.

Après, il faut extraire les combinaisons possibles: C(4,nb) groupes de 4, avec "nb" le nombre de bit a 1.

[Trap D]

@Trap, je ne comprend pas ton rapprochement entre la somme des combinaisons manquantes, le resultat d'un AND et le tableau (0 pour ce présent, 1 manquant).

Peut-tu faire un exemple avec un AND ?

Je reprends mon exemple

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
   a b c d e f g
1: 0 0 0 0 0 1 1	=> codage 32 + 64 = 96	en hexa 1 100 000
2: 0 0 1 0 1 0 0	=> codage 4 + 16 = 20	en hexa 0 010 100
3: 1 0 0 0 0 0 1	=> codage 1+ 64 = 65	en hexa 1 000 001   
4: 0 1 0 1 0 0 0	=> codage 2 + 8 = 9	en hexa 0 001 010  
5: 1 0 1 0 0 0 0 	=> codage 1 + 4 = 5	en hexa 0 000 101
6: 0 0 1 0 1 0 0	=> codage 4 + 16 = 20	en hexa 0 010 100

maintenat si tu fais un AND bit à bit des codage de 1 et 2 =
1: en hexa 1 100 000
2: en hexa 0 010 100
on obtient 0 000 000, donc un résultat nul et pas d'élément commun en effet abcde et abdfg n'ont pas quatre lettres communes

Si maintenant on fait la même chose pour 1 et 3
1: en hexa 1 100 000
3: en hexa 1 000 001
on obtient 1 000 000 donc un résultat non nul et au moins 4 lettres communes
abcde et bcdef on bien les 4 lettres bcde communes

Idem pour 2 et 5:
2: en hexa 0 010 100
5: en hexa 0 000 101
on obtient 0 000 100
Résultat non nul, abdfg et bdefg ont bien 4 lettres communes.

[pseudocode]

@Trap D: ca marche car tu es dans un cas particulier: un alphabet de 7 elements et toutes les lignes ont 4 valeurs (+ 2 trous).

A partir du moment ou 2 lignes ont 1 trou en commun, elles ont forcement soit 4, soit 5 valeurs communes.

[tania]

En fait Trap, ta méthode est simple et bonne dans le contexte actuel.
Quoi qu'il y a n'a pas besoin de faire de somme et calcul en hexa, le 1er tableau suffit à trouver.

Il suffit de chercher le chiffre manquant sur les 2 chiffres qui manque sur 2 lignes différentes.
Ainsi le c ou 4 apparait à la fois en ligne 2, 5 et 6.


Par contre, que devient cette méthode si les lettres vont de A à H ?

[pseudocode]

Par contre, que devient cette méthode si les lettres vont de A à H ?

Elle marche s'il y a au maximum 2 vides par ligne:

ligne A = 6 symboles parmi 8 + 2 vides
ligne B = 6 symboles parmi 8 + 2 vides

si 1 vide en commun, ca revient a avoir un alphabet de 7 symboles (au lieu de 8) et un seul vide par ligne:

ligne A = 6 symboles parmi 7 + 1 vide
ligne B = 6 symboles parmi 7 + 1 vide

Intersection A/B possibles:
5 symboles ( si le vide restant est commun )
4 symboles ( si les 2 lignes n'ont pas le meme vide )

[Trap D]

Comme l'a très bien dit pseudocode, ma méthode fonctionne dans les conditions de l'exemple, a savoir

ca marche car tu es dans un cas particulier: un alphabet de 7 elements et toutes les lignes ont 4 valeurs (+ 2 trous).

C'est pour celà que j'ai écrit

si on s'en tient à l'exemple donné