fusion de deux nombres entiers...

[Jean-Francois Ortolo]

Bonjour

Soient $n1 et $n2 deux nombres entiers, dont on sait que $n1 < $n2

Le problème, est de restituer la théorique bonne valeur de ces deux
nombres, sachant que s'ils sont différents, c'est que des chiffres
parasites se sont glissés dans l'un des deux nombres ( ou les deux ).

Je commence avec deux nombres, je continuerai avec plus que deux
nombres, car je dispose d'un certain nombre de nombres ( sic ) qui
devraient être égaux, mais le parasitage fait que, parfois, il ne le
sont pas.

Il est sûr que le parasitage ne consiste que dans l'ajout de chiffres
supplémentaires dans certains nombres, sans altération de l'ordre des
chiffres composant le nombre de départ ( non parasité ). Il n'y a jamais
de retrait de chiffres à cause du parasitage.

Donc, l'algorithme pour restituer le nombre réel, est évident: fusion
dans l'ordre de tous les nombres, pour ne retenir que les chiffres
appartenant à tous les nombres sans exception, tout en respectant
l'ordre. C'est donc un algorithme de fusion.

Pour se limiter à simplement deux nombres au départ, et sachant que
si $n1 == $n2, on retient $n1, on suppose donc, que $n1 < $n2.

Ma question est: Y a-t-il moyen d'opérer cete fusion, avec une
expression régulière ( Posix de préférence ), et une instruction de type
str_replace() ou, plus probablement: ereg_replace() ?

Comme $n1 < $n2, je pense que l'expression régulière pourrait être
déduite de $n1 ?

Merci beaucoup à vous pour vos réponses à ce problème, probablement
classique en PHP.

Bien à vous.

Amicalement.

Jean-François Ortolo


PS Je sais bien comment faire une fusion de deux chaînes de
caractères ( c'est cet algorithme-là que je veux implémenter ), mais je
cherche essentiellement à réduire le coût en durée d'exécution, donc à
utiliser une expression régulière et une instruction de remplacement, au
lieu de traiter chaque caractère ( chiffres ) les uns après les autres.

Les chiffres parasites peuvent être situés n'importe où dans les
nombres de départ.

[Jean-Francois Ortolo]

Post by Jean-Francois Ortolo
Bonjour

<...>

Post by Jean-Francois Ortolo
PS Je sais bien comment faire une fusion de deux chaînes de
caractères ( c'est cet algorithme-là que je veux implémenter ), mais je
cherche essentiellement à réduire le coût en durée d'exécution, donc à
utiliser une expression régulière et une instruction de remplacement, au
lieu de traiter chaque caractère ( chiffres ) les uns après les autres.
Les chiffres parasites peuvent être situés n'importe où dans les
nombres de départ.

Attention

Il s'agit bien d'un algorithme de fusion - dans l'ordre - mais en ne
retenant que les chiffres rencontrés dans tous les nombres analysés.

[Olivier Miakinen]

Post by Jean-Francois Ortolo
Soient $n1 et $n2 deux nombres entiers, dont on sait que $n1 < $n2
Le problème, est de restituer la théorique bonne valeur de ces deux
nombres, sachant que s'ils sont différents, c'est que des chiffres
parasites se sont glissés dans l'un des deux nombres ( ou les deux ).

Je crois avoir fini par comprendre (en lisant la suite) ce que tu
cherches à faire. Mais avoue que ce n'est pas très facile avec ce début
puisque tu commences par dire qu'ils sont différents avant d'expliquer
que s'ils sont différents c'est une erreur...

Note que donner quelques exemples bien choisis aurait pu aider, aussi.

Post by Jean-Francois Ortolo
Je commence avec deux nombres, je continuerai avec plus que deux
nombres, car je dispose d'un certain nombre de nombres ( sic ) qui
devraient être égaux, mais le parasitage fait que, parfois, il ne le
sont pas.
Il est sûr que le parasitage ne consiste que dans l'ajout de chiffres
supplémentaires dans certains nombres, sans altération de l'ordre des
chiffres composant le nombre de départ ( non parasité ). Il n'y a jamais
de retrait de chiffres à cause du parasitage.
Donc, l'algorithme pour restituer le nombre réel, est évident: fusion
dans l'ordre de tous les nombres, pour ne retenir que les chiffres
appartenant à tous les nombres sans exception, tout en respectant
l'ordre. C'est donc un algorithme de fusion.

Euh... évident ?

$n1 = 11145999
$n2 = 11154999
résultat = 1114999 ? 1115999 ? 111999 ?

Post by Jean-Francois Ortolo
Pour se limiter à simplement deux nombres au départ, et sachant que
si $n1 == $n2, on retient $n1, on suppose donc, que $n1 < $n2.
Ma question est: Y a-t-il moyen d'opérer cete fusion, avec une
expression régulière ( Posix de préférence ), et une instruction de type
str_replace() ou, plus probablement: ereg_replace() ?

Je pense que ça doit pouvoir se faire avec un unique preg_replace(), je
vais y réfléchir. En revanche je ne vois pas comment on pourrait le
faire avec les expressions régulières de type Posix vu qu'il faudra
utiliser des références internes à la recherche, ce qui ne doit pas
exister dans les ereg Posix.

Post by Jean-Francois Ortolo
Comme $n1 < $n2, je pense que l'expression régulière pourrait être
déduite de $n1 ?

Ah, tu veux dire créer une regexp à partir de $n1, à appliquer sur $n2 ?
Moi j'aurais pensé utiliser une expression fixe sur "$n1|$n2" ("|" étant
un caractère quelconque autre qu'un chiffre).

Post by Jean-Francois Ortolo
Merci beaucoup à vous pour vos réponses à ce problème, probablement
classique en PHP.

:-D

Le « probablement » me semble excessivement optimiste.

Post by Jean-Francois Ortolo
PS Je sais bien comment faire une fusion de deux chaînes de
caractères ( c'est cet algorithme-là que je veux implémenter ), mais je
cherche essentiellement à réduire le coût en durée d'exécution, donc à
utiliser une expression régulière et une instruction de remplacement, au
lieu de traiter chaque caractère ( chiffres ) les uns après les autres.

Si tu veux améliorer les performances, c'est une raison supplémentaire
pour utiliser preg_xxx plutôt que ereg_xxx (fût-ce avec une expression
identique).

Post by Jean-Francois Ortolo
Les chiffres parasites peuvent être situés n'importe où dans les
nombres de départ.

D'où ma question à propos de 11145999 et 11154999. À la limite,
qu'est-ce qui nous empêche de penser que le nombre de départ était
1199 auquel a été ajouté 1459 dans un cas et 1549 dans l'autres ?

[Jean-Francois Ortolo]

Post by Olivier Miakinen

Post by Jean-Francois Ortolo
Donc, l'algorithme pour restituer le nombre réel, est évident: fusion
dans l'ordre de tous les nombres, pour ne retenir que les chiffres
appartenant à tous les nombres sans exception, tout en respectant
l'ordre. C'est donc un algorithme de fusion.

Euh... évident ?
$n1 = 11145999
$n2 = 11154999
résultat = 1114999 ? 1115999 ? 111999 ?

Compte tenu du fait que le parasitage est très aléatoire, et ne
concerne que 83 lignes sur un total de plus de 100000 lignes non
parasitées, et que les nombres à comparer sont situés à des lignes
contigûes les unes des autres, on considère qu'il y a une probabilité
nulle, pour que ce type de parasitage double ( très peu probable deux
fois contigüe, et de manière aussi directionnelle... pour appeler les
choses comme ça ), se passe réellement.

En fait, il y a déjà une faible probabilité, pour que sur les deux
nombres, les deux soient parasités, mais je suis quand même obligé de
tenir compte de cette très faible probabilité. Autrement, il suffirait
de prendre le nombre le plus petit.

Post by Olivier Miakinen
Je pense que ça doit pouvoir se faire avec un unique preg_replace(), je
vais y réfléchir. En revanche je ne vois pas comment on pourrait le
faire avec les expressions régulières de type Posix vu qu'il faudra
utiliser des références internes à la recherche, ce qui ne doit pas
exister dans les ereg Posix.

Post by Jean-Francois Ortolo
Comme $n1 < $n2, je pense que l'expression régulière pourrait être
déduite de $n1 ?

Ah, tu veux dire créer une regexp à partir de $n1, à appliquer sur $n2 ?
Moi j'aurais pensé utiliser une expression fixe sur "$n1|$n2" ("|" étant
un caractère quelconque autre qu'un chiffre).

Oui, effectivement.

Histoire, si $n1 = 123 et $n2 = 81426834 on a $n1 < $n2

$expr = "^[^1]*1[^2]*2[^3]*3[0-9]*$"; // Expression déduite de $n1
$n = ereg_replace($expr, $n1, $n2);
if($n == $n1)
$nombre = $n; // résultat trouvé


Je reconnais que c'est stupide, celà ne marche que si $n1 est le
nombre à chercher, et si donc l'un des deux nombres n'est pas parasité.

Si les deux nombres sont parasités, j'ai besoin de quelque chose de
plus compliqué.

Post by Olivier Miakinen
D'où ma question à propos de 11145999 et 11154999. À la limite,
qu'est-ce qui nous empêche de penser que le nombre de départ était
1199 auquel a été ajouté 1459 dans un cas et 1549 dans l'autres ?

Non, parce que le faible pourcentage de lignes parasitées, et le
caractère très très aléatoire du parasitage, font qu'il est certain que
le même parasitage, ne se reproduira pas deux fois de suite.

Les chiffres ajoutés par le parasitage, peuvent être n'importe quels
chiffres, en relativement faible nombre ( moins de 8 chiffres en plus
admettons ), il est possible de rencontrer relativement souvent les
quatres chiffres parasites 2000 à la suite, ou le chiffre 8 répété ou
non. Sinon, tout autre chiffre peut participer à un parasitage.

Attention: Il y a un plus, c'est que les nombres à trouver, sont
nécessairement inférieurs à 100, c'est à dire à un ou deux chiffres.

Merci beaucoup pour votre aide.

Jean-François Ortolo

[Olivier Miakinen]

Post by Jean-Francois Ortolo
Compte tenu du fait que le parasitage est très aléatoire, et ne
concerne que 83 lignes sur un total de plus de 100000 lignes non
parasitées, [...]
Les chiffres ajoutés par le parasitage, peuvent être n'importe quels
chiffres, en relativement faible nombre ( moins de 8 chiffres en plus
admettons ), il est possible de rencontrer relativement souvent les
quatres chiffres parasites 2000 à la suite, ou le chiffre 8 répété ou
non. Sinon, tout autre chiffre peut participer à un parasitage.
Attention: Il y a un plus, c'est que les nombres à trouver, sont
nécessairement inférieurs à 100, c'est à dire à un ou deux chiffres.

Moi y en a rien comprendre du tout. Tu as 100 000 lignes contenant un
nombre d'un ou deux chiffres, ce nombre devant être identique partout
sauf sur 83 lignes, où ce nombre de deux chiffres peut être parasité par
un nombre de plus de 4 chiffres ? C'est bien ça ?

Si ce n'est pas ça, donne-nous un exemple *concret*. Par exemple, si
c'est bien ce que j'ai compris :

<début des 100 000 lignes>
37
37
37
...
37
320007 (1re erreur)
37
...
37
8838887888 (2e erreur)
37
...
37
37
37
337 (83e erreur)
<fin des 100 000 lignes>

[Jean-Francois Ortolo]

Post by Olivier Miakinen
Moi y en a rien comprendre du tout. Tu as 100 000 lignes contenant un
nombre d'un ou deux chiffres, ce nombre devant être identique partout
sauf sur 83 lignes, où ce nombre de deux chiffres peut être parasité par
un nombre de plus de 4 chiffres ? C'est bien ça ?
Si ce n'est pas ça, donne-nous un exemple *concret*. Par exemple, si
<début des 100 000 lignes>
37
37
37
...
37
320007 (1re erreur)
37
...
37
8838887888 (2e erreur)
37
...
37
37
37
337 (83e erreur)
<fin des 100 000 lignes>

Bonjour Monsieur

Il y a en gros, plusieurs occurences du même nombre ( deux ou un
chiffre théoriquement ), sur plusieurs lignes contigües.

Mais sur plus de, mettons 6 ou 7 lignes contigües, le numéro change,
n'est plus le même ( même sans parasitage ).

On suppose, pour la clarté de l'énoncé du problème, qu'il n'y a qu'un
seul nombre disponible par ligne.

Les groupes de lignes correspondant aux théoriques mêmes nombres,
comportent le même code de début de ligne ( $an$mois$jour$reunion$course
), ou chacune des variables sont sur deux chiffres. Je peux donc savoir,
quels sont les nombres devant être égaux, d'après ce code, qui est
identique pour les différentes lignes où ces nombres devraient être les
mêmes.

Je passe sur les problèmes de formattage du fichier, je suis censé
savoir identifier chaque nombre d'après son rang ( rang d'arrivée du
cheval, 1, 2, 3, etc... ). Les nombres sont les numéros de partants des
chevaux.

Donc, il n'y a pas de problème pour la collecte et l'identification
des ensembles de nombres devant être égaux.

Pour chaque ensemble de nombres, le nombre de nombres ( égaux ) de
l'ensemble, peut aller de 2 à environ une dizaine.

Pour le cas des samples contenant seulement deux nombres ( et pour le
reste aussi ), je suppose que le cas dont vous avez parlé ( 11145999 et
11154999 ) ne peut pas se produire. De plus, le nombre à trouver doit
comporter un ou deux chiffres.

Dans un premier temps, je me limite à la comparaison de deux nombres.

Ultérieurement, ce serait plus intéressant, de pouvoir directement
déduire le nombre cherché, à parti d'une expression prenant en compte,
tous les nombres disponibles, censés être égaux.

Merci beaucoup de votre aide.

Je vous avoue, que je n'ai jamais approfondi les joies des
expressions rationnelle Perl, ni la logique des instructions
preg_replace() , qui, je le reconnais, sont beaucoup plus puissantes que
les simples ereg_replace()


Bien à vous.

Amicalement.

Jean-François Ortolo


PS Pour donner un exemple concret, voici ce à quoi pourrait ressembler
le fichier, nonbstant le problème du formattage:

0709010101 57 nombre à trouver: 57
0709010101 578
0709010101 957
0709010102 98 nombre à trouver: 98
0709010102 986
0709020101 5462 nombre à trouver: 56
0709020101 65361
0709020102 etc....

Ce ne sont que des exemples, ces nombres sont des numéros de partants
de chevaux, donc devrient nécessairement être inférieur à 30.

Donc, soit c'est un nombre à un chiffre ( différent de 0 ), soit
c'est un nombre à 2 chiffres, dont le premier chiffre est, soit 1, soit 2.

Evidemment, les nombres ne commencent jamais pas un 0.

Le nombre de lignes parasitées ( 83 ), correspond au nombre de
lignes, où figurent des numéros de chevaux > 27

Le nombre de lignes total, où figurent des nombres, est de l'ordre de
100000 lignes, ce qui donne une idée sur la faible probabilité de
parasitage.

Il est vrai, qu'il est peu probable qu'un parasitage, consiste
seulement en l'ajout du chiffre 1 ou 2, avant un nombre à un chiffre.

Celà fait que le critère "nombre <= 27" me paraît suffisamment
significatif, d'absence de parasitage.

Ceci dit, je ne peux pas prendre n'importe quel nombre < 28, comme un
nombre non parasité avec certitude. Je suis obligé de vérifier par
comparaisons avec d'autres nombres devant être égaux, pour en déduire le
nombre exact.

[Mickael Wolff]

Post by Jean-Francois Ortolo
Bonjour
Soient $n1 et $n2 deux nombres entiers, dont on sait que $n1 < $n2

Ton histoire « confusionne » mon esprit. Comment sont représentés tes
chiffres ? Est-ce que tu travaille sur des entiers ou flottants
processeurs, ou sur leur représentation sous forme de chaine ?

Qu'est-ce qu'un parasitage dans ce cas précis ? Comment l'obtiens-tu ?

Si c'est un problème algorithmique connu, désolé pour la pollution,
j'ai beaucoup trop de lacunes en algorithmie. Sinon, bah, qu'on
m'explique :)

Bonne journée !

PS.: Et si vous êtes en France, voir en Alsace, faites comme moi :
sortez, fait beau ! Alors bonne balades ;)

Note au modérateur : je suis désolé pour l'encodage, mon client st
pourtant bien configuré. J'essaierai d'être vigilant à ce propos.

[Jean-Francois Ortolo]

Post by Mickael Wolff
Ton histoire « confusionne » mon esprit. Comment sont représentés tes
chiffres ? Est-ce que tu travaille sur des entiers ou flottants
processeurs, ou sur leur représentation sous forme de chaine ?

Evidemment, les entiers sont sous forme de chaînes de caractères.

Post by Mickael Wolff
Qu'est-ce qu'un parasitage dans ce cas précis ? Comment l'obtiens-tu ?

J'ai déjà décrit ce type de parasitage dans des précédents messages.

En gros: Parasitage == ajout de n'importe quels chiffres à n'importe
quel endroit de la chaîne de caractères composant le nombre entier. Le
nombre de chiffres ajoutés, dans le cas de parasitage, peut aller,
mettons, de 1 chiffre ajouté à 8 chiffres ajoutés.

Un parasitage ne peut pas consister dans le retrait d'un ni de
plusieurs chiffres, du nombre initial. Seuls des ajouts de chiffres sont
possibles ( à l'exclusion d'autre chose que des chiffres ).

Les codes de début de ligne $an$mois$jour$reunion$course avec chacune
des variables sur 2 chiffres, ne sont jamais parasités. Les nombres
entiers ( dont on suppose, pour la clarté de l'exposé du problème,
qu'ils sont situés après un caractère \t ( tabulation ) situé lui-même
après le code, à raison d'un nombre entier par ligne, ces nombres
entiers donc, sont les seuls tokens, susceptibles d'être parasités.

Se reporter à mon précédent message juste au dessus à droite, pour
plus de détails.

Post by Mickael Wolff
Si c'est un problème algorithmique connu, désolé pour la pollution,
j'ai beaucoup trop de lacunes en algorithmie. Sinon, bah, qu'on
m'explique :)

Apparemment, d'après Monsieur Miakinen, ce n'est pas un problème
algorithmique courant en PHP.

Post by Mickael Wolff
Bonne journée !

Merci beaucoup.

Bien à vous.

Amicalement.

Jean-François Ortolo

[Olivier Miakinen]

Post by Jean-Francois Ortolo
Se reporter à mon précédent message juste au dessus à droite, pour
plus de détails.

« Juste au dessus à droite » ? :-D

Pour que cette indication serve à quelque chose, il faudrait que Mickael
utilise le même nouvelleur que toi, configuré de la même manière, et
avec les mêmes articles téléchargés et affichés ! Cela fait beaucoup
trop de « si ».

Post by Jean-Francois Ortolo
Apparemment, d'après Monsieur Miakinen, ce n'est pas un problème
algorithmique courant en PHP.

Disons plus modestement que je n'ai encore jamais rencontré ce problème,
pas plus en PHP qu'ailleurs.

Post by Jean-Francois Ortolo
PS Pour donner un exemple concret, voici ce à quoi pourrait ressembler
0709010101 57 nombre à trouver: 57
0709010101 578
0709010101 957
0709010102 98 nombre à trouver: 98
0709010102 986
0709020101 5462 nombre à trouver: 56
0709020101 65361
0709020102 etc....
[...]
Le nombre de lignes parasitées ( 83 ), correspond au nombre de
lignes, où figurent des numéros de chevaux > 27

Les numéros 57, 98 et 56 de ton exemple sont tous supérieurs à 27.
Alors ? Parasités ou pas ?

[Matthieu Moy]

Post by Olivier Miakinen

Post by Jean-Francois Ortolo
Se reporter à mon précédent message juste au dessus à droite, pour
plus de détails.

« Juste au dessus à droite » ? :-D
Pour que cette indication serve à quelque chose, il faudrait que Mickael
utilise le même nouvelleur que toi, configuré de la même manière, et
avec les mêmes articles téléchargés et affichés ! Cela fait beaucoup
trop de « si ».

Il « faudrait », ou il « suffirait » ?

[Etienne SOBOLE]

Y a t-il une longeure maximale pour les chaine de chiffre???

Je serais interessé deja par voir l'algo po rapide que tu as mis au point,
car ce n'est pas trivial comme problèmatique..
Peut etre faut-il rechercher dans les algo de traitement du signal...

Ce qui est sur c'est que c'est pas ininteressant :)

Je vais chercher. A+
Etienne

[Jean-Francois Ortolo]

Post by Etienne SOBOLE
Y a t-il une longeure maximale pour les chaine de chiffre???

Il n'y a pas de longueur maximale pour les chaînes de chiffres, on
suppose simplement, que comme les nombres non parasités doivent être
inférieurs à 28 ( 2 chiffres ), et que l'on suppose qu'un vingtaine de
chiffres parasites est bien un maximum, je pense que la chaîne de
chiffres, ne dépassera pas 20 chiffres.

Post by Etienne SOBOLE
Je serais interessé deja par voir l'algo po rapide que tu as mis au point,
car ce n'est pas trivial comme problèmatique..
Peut etre faut-il rechercher dans les algo de traitement du signal...
Ce qui est sur c'est que c'est pas ininteressant :)
Je vais chercher. A+
Etienne

Ben...

C'est un algorithme de fusion avec sélection de tous les chiffres
appartenant à la fois aux deux nombres, dans l'ordre rencontré.

Attention, c'est important de dire, que c'est dans l'ordre rencontré,
puisque le parasitage ne va pas changer l'ordre relatif des chiffres
initiaux, entre eux.

Donc, mettons $n1 et $n2, on accède à chaque chiffre avec un indice:

$n1[0] est le premier chiffre de $n1 et $n1[strlen("$n1") - 1] est
le dernier chiffre de $n1.

Voici un algorithme que j'ai concocté, merci de m'indiquer les
erreurs qu'il contient, ou des contre-exemples qu'il ne pourrait pas
traiter.



// $n3 ou $n4 doivent contenir le résultat.
$n3 = "";
$n4 = "";

$k = 0;
$l = 0;
$o = 0;
$p = 0;
if($n1 == $n2)
$n = $n1;
else {
while(true) {
$o = $k;
$p = $l;
$trouve1 = false;
for(; $k < strlen($n1); $k++) {
if($n1[$k] == $n2[$l]) {
$n3 .= $n1[$k];
$n4 .= $n2[$l];
$trouve1 = true;
break;
}
}

if(!$trouve1)
$k = $o;

$trouve2 = false;
for(; $l < strlen($n2); $l++) {
if($n2[$l] == $n1[$k]) {
$n4 .= $n2[$l];
$n3 .= $n1[$k];
$trouve2 = true;
break;
}
}

if(!$trouve2)
$l = $p;

if((!$trouve1)&&(!$trouve2))
break;

$k++;
$l++;

} // fin de la boucle while(true)

// résultat
// théoriquement $n3 et $n4 sont égaux.
if(strlen($n3) > 0)
$n = 0 + $n3;
else
$n = -1; // les nombres $n1 et $n2 sont incompatibles
}


Qu'est-ce que vous pensez de cet algorithmme ?

Le problème, serait de le faire tourner dans autant de nombres $n1 et
$n2 que possible, pour en détecter les erreurs, s'il en contient.

Merci beaucoup de votre aide.

Bien à vous.

Amicalement.

Jean-François Ortolo

[Olivier Miakinen]

Post by Jean-Francois Ortolo
$n1[0] est le premier chiffre de $n1 et $n1[strlen("$n1") - 1] est
le dernier chiffre de $n1.
Voici un algorithme que j'ai concocté, merci de m'indiquer les
erreurs qu'il contient, ou des contre-exemples qu'il ne pourrait pas
traiter.
[ snip algo ]
Qu'est-ce que vous pensez de cet algorithmme ?

Je ne recopie pas tout, mais voici quelques remarques. Tout d'abord, la
variable $n4 ne sert strictement à rien puisqu'elle ne peut en aucune
façon être différente de $n3. Par ailleurs, j'ai essayé de suivre à la
main l'algorithme avec un exemple donné dans la page¹ que t'a signalée
Michel Olagnon dans un autre groupe, où $n1 vaut "XMJYAUZ" et $n2 vaut
"MZJAWXU". En principe, le résultat devrait être "MJAU". Or :

1) Ton programme tel qu'il est semble retourner "MMZZ".

2) En rajoutant « $k++; $l++; » à chaque fois qu'un caractère est
trouvé, ça semble marcher avec ce jeu de tests ("MJAU"), mais...

3) En échangeant les rôles de $n1 et $n2, le résultat devrait toujours
être "MJAU" mais j'ai l'impression que ton code va retourner "XU".

Bref, pas terrible...

Post by Jean-Francois Ortolo
Le problème, serait de le faire tourner dans autant de nombres $n1 et
$n2 que possible, pour en détecter les erreurs, s'il en contient.

Essaye avec les chaînes données ci-dessus, dans un sens et dans l'autre,
quitte à remplacer les lettres par des chiffres si tu veux (mais ça ne
changera rien, bien sûr).


¹ http://en.wikipedia.org/wiki/Longest_common_subsequence_problem

[Etienne SOBOLE]

Post by Olivier Miakinen
¹ http://en.wikipedia.org/wiki/Longest_common_subsequence_problem

Ouai trop fort wikipedia...
bon d'accord c'est pile poil ce que JF recherchait, mais la piste de
Levenshtein etait bonne aussi :)

Bon ben voila. l'ffaire est classée.
Merci pour ce lien fort interessant.

a+
Etienne

[Jean-Francois Ortolo]

Olivier Miakinen wrote:=

Post by Olivier Miakinen
¹ http://en.wikipedia.org/wiki/Longest_common_subsequence_problem

Bonjour Monsieur

Je sais bien que mon algorithme ne marche pas, je l'ai dit dans un
message à part ( mon client de messagerie ne veut pas suivre les threads
quand je fais un forward ).

Donc, voici l'algorithme de wikipedia, non optimisé, en entier:

// $C[0..$m][0..$n] contient les distances.

// X[1..$m] contient les chiffres du 1er nombre, <=> $m = strlen($n1)
// Y[1..$n] contient les chiffres du 2ème nombre, <=> $n = strlen($n2)

// initialisation
// des variables
$C = array();
$X = array();
$Y = array();

$m = strlen($n1);
$n = strlen[$n2);
for($i = 1; $i <= $m; $i++)
$X[$i] = $n1[$i - 1];
for($j = 1; $j <= $n; $j++)
$Y[$j] = $n2[$j - 1];

// calcul des distances
for($i = 0; $i <= $m; $i++)
$C[$i][0] = 0;
for($j = 0; $j <= $n; $j++)
$C[0][$j] = 0;

for($i = 1; $i <= $m; $i++)
for($j = 1; $j <= $n; $j++)
if($X[$i] == $Y[$j])
$C[$i][$j] = $C[$i - 1][$j - 1] + 1;
else
$C[$i][$j] = max($C[$i][$j - 1], $C[$i - 1][$j]);

// En ce point, les valeurs
// $C[0..$m][0..$n] sont fixées.

// Fonction de lecture
// de la LCS ( longer common subsequence ),
// ou plus longue commune sous-séquence.
// Il faut appeler cette fonction
// avec les paramètres $i = $m et
// $j = $n.
// Cette fonction backTrack construit
// la chaîne LCS à rebourg,
// d'où le nom backTrack()

function backTrack($C, $X, $Y, $i, $j) {

if(($i == 0)||($j == 0))
return("");
else if($X[$i] == $Y[$j])
return(backTrack($C, $X, $Y, ($i - 1), ($j - 1)) . $X[$i]);
else {
if($C[$i][$j - 1] > $C[$i - 1][$j])
return(backTrack($C, $X, $Y, $i, ($j - 1));
else
return(backTrack($C, $X, $Y, ($i - 1), $j);
}
}


Et voilà.

J'espère que mon message, ne sera pas considéré par monsieur le
modérateur, comme relatif aux algorithmes plus qu'au PHP, mais comme
vous étiez intéressés par le dénouement de cette aventure... ;)

Merci beaucoup à Monsieur Miakinen de son aide.

Bien à vous.

Amicalement.

Jean-François Ortolo

[Jean-Francois Ortolo]

Bonjour

J'ai testé l'algorithme de wikipedia ci-dessus ( voir précédent
message ), il fonctionne très bien.

Le problème est résolu en ce qui me concerne, j'ai ainsi une boîte
noire pour calculer les numéros de chevaux corrects, à partir de
plusieurs numéros parasités ou non.

Merci beaucoup de votre aide, particulièrement Monsieur Miakinen,
dont j'ai suivi le lien vers wikipedia.

Bien à vous.

Amicalement.

Jean-François Ortolo

[Olivier Miakinen]

Post by Jean-Francois Ortolo
Merci beaucoup de votre aide, particulièrement Monsieur Miakinen,
dont j'ai suivi le lien vers wikipedia.

C'est trop d'honneur que tu me fais car, encore une fois, le premier à
donner ce lien était Michel Olagnon en réponse à ta question dans le
groupe fr.comp.algorithmes.

[Etienne SOBOLE]

Bon une petite recherche et j'ai trouvé...

cela s'apparente aux algorithmes qui recherchent les différences entre deux
chaines de caractères.
En gros ca te dit tous les changements à réaliser pour passer d'une chaine à
l'autre.
Dans ton cas il suffit d'ignorer les changements puisque si tu enleves les
caractères insérés, supprimés, ou deplacés il devrait te rester les
caractère en commun.

Donc faut aller voir du cote de la Distance de Levenshtein
Le tres excellent Wikipédia te donnera ca.
http://fr.wikipedia.org/wiki/Distance_de_Levenshtein

puis cap sur les implémentations
http://en.wikibooks.org/wiki/Algorithm_implementation/Strings/Levenshtein_distance

ou tu trouvera celle du PHP
qui au passage te dis que Levenshtein existe nativement en PHP
http://fr3.php.net/manual/fr/function.levenshtein.php

enfin tu recherches le post de dinesh AT dinsoft DOT net sur la meme page et
tu trouves à peu de chose prêt ton bonheur... Il y a sans doute une tite
adaptation à faire pour ton cas précis, mais c'est sans doute par là qu'il
faut chercher....

Tiens nous au courrant.

A+
Etienne