Discussion :

[tania]

Soit le tableau
1- a b c d e
2- a b d f g
3- b c d e f
4- a c e f g
5- b d e f g
6- a b d f g

Je dois trouver quelle est la ou les combinaisons de 4 lettres que l'on retrouve au moins 2 fois.
exemple à vue d'oeil je vois "bdfg" à la ligne 2 et 6.

Pour le moment , j'ai pensé à créer un tableau avec toutes les combinaisons possibles à 4 lettres,
puis en parcourant ce nouveau tableau, vérifier si je trouve au moins 2 fois la combinaison.

Si vous avez une idée, un conseil.

[PRomu@ld]

L'idée parait judicieuse, sans nécessairement avoir à stocker toutes les combinaisons possibles (soit en les générants à la volée, soit en les générant à partir de ce qui t'es donné).

Sinon, en fait, le plus important dans l'algorithme va être de savoir comment tu vas faire tes tests pour savoir si oui ou non, il y a une répétition.

[pseudocode]

Une idée sympa, (si j'ai bien compris le probleme) c'est de noter ton tableau comme ca:

Code :

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

1
2
3
4
5
6
7
 
1- a b c d e . .
2- a b . d . f g
3- . b c d e f .
4- a . c . e f g
5- . b . d e f g
6- a b . d . f g

ensuite, l'algo consiste a virer 3 colonnes et regarder combien de lignes sont completes (sans trous). Par exemple, si tu retires les colonnes a,c,e il reste 3 lignes completes: la 2, la 5 et la 6

[tania]

En fait Pseudocode, tu proposes une idée diffèrente. Ton idée est intèressante.
Si je te suis bien dans ta version, il faudrait dans un premier temps trouver toutes les combinaisons possible de 3 lettres entre a et g.

A la réflexion, ton idée est l'inverse de la mienne.

[Trap D]

En repartant de l'idée de pseudocode, on code les combinaisons par a= 1, b = 2 c= 4 d = 8 ...
On fait les sommes et on regarde celles qui sont égales.

[pseudocode]

Oui. J'ai choisi l'approche inverse car c'est plus simple de verifier qu'une ligne n'a pas de trou, plutot que de verifier qu'une sequence de symbole est présente dans une ligne.

Sinon ca fait le meme nombre d'iteration (C(3,7)=C(4,7)=35)

Mon approche est juste plus couteuse en mémoire car on doit construire le tableau 7x6 (avec les trous).

[Trap D]

Euh, le problème c'est de trouver des combinaisons identiques ou des combinaisons sans trous ???

[tania]

Des combinaisons identiques, mais pour répondre au problème Pseudocode recherche les combinaisons sans trous.

[Trap D]

Il me semble que c'est inutilie car avec mon codage on trouve les combinaisons identiques tout de suite
1- a b c d e => 1 + 2 + 4 + 8 + 16 = 21
2- a b d f g => 1 + 2 + 8 + 16 + 32 = 59
3- b c d e f => 2 + 4 + 8 + 16 + 32 = 62
4- a c e f g => 1 + 4 + 16 + 32 + 64 = 117
5- b d e f g => 2 + 8 + 16 + 32 + 64 = 122
6- a b d f g => 1 + 2 + 8 + 16 + 32 = 59

[pseudocode]

on cherche des combinaisons de seulement 4 lettres.

[tania]

hmm, je viens de faire justement le tableau, j'ai obtenu
1- 1 2 4 8 16 . . = 31
2- 1 2 . 8 . 32 64 = 107
3- . 2 4 8 16 32 . = 62
4- 1 . 4 . 16 32 64 = 117
5- . 2 . 8 32 64 = 106
6- 1 2 . 8 . 32 64 = 107

1 + 2 + 4 + 8 + 16 + 32 + 64 = 127

f chez toi est égale à 16 et 32, es normal ?
Sinon, ce n'est pas inutile, (à moins d'avoir mal compris ta logique) car il faut trouver tous ceux qui ont au moins 4 lettres identiques et non les 5.

[tania]

J'ai fait le tableau dans l'idée qu'il y avait peut être une nouvelle idée à trouver à partir de lui ou une combinaison de 2 idées

[Trap D]

J'ai lu en travers le problème
Pour le f erreur de calcul c'est 32 effectivement.

[tania]

J'essaye d'aller plus loin.
j'imagine le tableau suivant :
2 4 8 16 32 = 62
2 4 8 32 64 = 110
1 4 16 32 64 = 117
4 8 16 32 64 = 124

Je me demande si en connaissant le total des lignes, on peut arriver à connaitre les combinaisons identiques de 4 lettres.

[pseudocode]

J'essaye d'aller plus loin.
j'imagine le tableau suivant :
2 4 8 16 32 = 62
2 4 8 32 64 = 110
1 4 16 32 64 = 117
4 8 16 32 64 = 124

Je me demande si en connaissant le total des lignes, on peut arriver à connaitre les combinaisons identiques de 4 lettres.

Hum... oui, en passant par leur représentation binaire, en faisant un AND et en comptant le nombre de bits restant. Ce qui revient a calculer la taille de l'intersection des deux groupes de lettres.

Code :

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

1
2
3
4
5
 
5- . b . d e f g = 0101111
6- a b . d . f g = 1101011
__________________________
L5 AND L6        = 0101011  -> 4 bits a 1 => match !

[tania]

ok, mais du coup on en reviens à comparer ligne après ligne, je ne crois pas que ca soit tres interessant.
Je pensais plus à essayer de trouver un calcul fait à partir de la somme du genre :
127-x...
à la réflexion, c'est comme ta 1er idée, celle de virer des colonnes.



ps2 : merci beaucoup en tout cas de suivre ma réflexion.

[pseudocode]

ok, mais du coup on en reviens à comparer ligne après ligne, je ne crois pas que ca soit tres interessant.
Je pensais plus à essayer de trouver un calcul fait à partir de la somme du genre :
127-x...
à la réflexion, c'est comme ta 1er idée, celle de virer des colonnes.
ps : en mode réfléchir

ps2 : merci beaucoup en tout cas de suivre ma réflexion.

Il faut choisir la meilleure approche en fonction de tes contraintes...
-est-ce que tu as beaucoups de lignes ?
-est-ce que tu as beaucoups de sous-groupe de 4 possibles ?
-est-ce que tu cherches toutes les solutions, une seule solution ou juste savoir s'il y a des solutions ?
...

[Trap D]

Plutôt que de rechercher les élélments communs, pourquoi ne pas rechercher les éléments qu'ils n'ont pas.
je m'explique, si on s'en tient à l'exemple donné, on codera les combinaisons
1- a b c d e => 32 + 64 = 96 car il manque f (32) et g (64)
2- a b d f g => 4 + 16 = 20 car il manque c (4) et e (16)

Ensuite il ne suffit plus qu'à faire des AND entre les nombres, si le résultat est 0 les nombres n'ont pas 4 éléments communs sinon, ils en ont 4.
Pour s'en convaincre, il suffit de regarder le tableau

Code :

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

1
2
3
4
5
6
7
8
 
   a b c d e f g
1: 0 0 0 0 0 1 1
2: 0 0 1 0 1 0 0
3: 1 0 0 0 0 0 1
4: 0 0 1 0 1 1 1
5: 1 0 1 0 0 0 0 
6: 0 0 1 0 1 0 0

[tania]

@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 ?



@Pseudocode, y a deux résultats qui m'intéressent en particulier
peu de ligne, peu de sous-groupe de 4 possibles, toutes les solutions
ET
beaucoup de lignes, beaucoup de sous-groupe de 4 possibles, toutes les solutions

[pseudocode]

@Pseudocode, y a deux résultats qui m'intéressent en particulier
peu de ligne, peu de sous-groupe de 4 possibles, toutes les solutions

Pour ce genre de cas, ta 1ere approche est tres bien. Creer une liste de toutes les combinaisons possibles, parcourir chaque ligne et incrementer les compteurs correspondant aux combinaisons trouvées.

beaucoup de lignes, beaucoup de sous-groupe de 4 possibles, toutes les solutions

Dans ce cas, je conseille l'approche "codage binaire" de chaque ligne, puis de comparer les lignes 2 a 2 et compter si le nombre d'elements communs est >= 4. Si c'est la cas, on extrait les combinaisons communes et on crée/incrémente les compteurs.

Le gros avantage c'est que, dans ces 2 approches, une grande partie de l'algorithme est parallelisable.