Version imprimable
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.
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.
Une idée sympa, (si j'ai bien compris le probleme) c'est de noter ton tableau comme ca:
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 6Code:
2
3
4
5
6
7
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.
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.
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).
Euh, le problème c'est de trouver des combinaisons identiques ou des combinaisons sans trous ???
Des combinaisons identiques, mais pour répondre au problème Pseudocode recherche les combinaisons sans trous.
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
on cherche des combinaisons de seulement 4 lettres. ;)
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.
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 :roll:
J'ai lu en travers le problème :oops::oops:
Pour le f erreur de calcul c'est 32 effectivement. :oops:
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.Citation:
Envoyé par tania
Code:
2
3
4
5
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.
Il faut choisir la meilleure approche en fonction de tes contraintes...Citation:
Envoyé par tania
-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 ?
...
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:
2
3
4
5
6
7
8
@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
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.Citation:
Envoyé par tania
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.Citation:
beaucoup de lignes, beaucoup de sous-groupe de 4 possibles, toutes les solutions
Le gros avantage c'est que, dans ces 2 approches, une grande partie de l'algorithme est parallelisable.
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 ?)
3/suite okCode:
2
3
4
5
C'est bien ce que tu veux dire ?
Si c'est ça, on devra faire une comparaison de chaque codage binaire, non ?
oui. tu peux faire un codage binaire "pur" si ca tient sur un int/long (32/64 bits = 32/64 symboles)Citation:
Envoyé par tania
oui. ca fait C(2,nl) operations, avec "nl" le nombre de lignes. Cette partie de l'algo est parallelisable.Citation:
2/puis de comparer les lignes 2 a 2 (c'est pas 1 à 1 ?)
Code:
2
3
4
5
(on dit bien 2 a 2 dans ce cas... 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.Citation:
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 ?
Après, il faut extraire les combinaisons possibles: C(4,nb) groupes de 4, avec "nb" le nombre de bit a 1.
Je reprends mon exempleCitation:
Envoyé par tania
maintenat si tu fais un AND bit à bit des codage de 1 et 2 =Code:
2
3
4
5
6
7
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.
@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.
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 ?
Elle marche s'il y a au maximum 2 vides par ligne:Citation:
Envoyé par tania
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 )
Comme l'a très bien dit pseudocode, ma méthode fonctionne dans les conditions de l'exemple, a savoirC'est pour celà que j'ai écritCitation:
Envoyé par pseudocode
Citation:
Envoyé par Trap D