Discussion :

[checassist]

Bonjour,
j'ai deux soucis
le premier est que j essaie d'applique la formule sur les doublons concernant sans y parvenir
et le second est que j'ai besoin d'aide pour la formule sur les triplons
merci

[tbc92]

On va commencer par le début.
Oublions les triplons dans un premier temps, comment tu fais pour enlever les doublons. Parce que, de toutes façons quand les gens parlent d'enlever les doublons, ce qu'ils cherchent à faire, c'est enlever les doublons, les triplons, les quadruplons etc etc. Ils cherchent à garder une seule ligne là où il y avait 2 ou plusieurs lignes identiques.

[wiwaxia]

... quand les gens parlent d'enlever les doublons ... Ils cherchent à garder une seule ligne là où il y avait 2 ou plusieurs lignes identiques.

C'est vrai en général, mais tu prolonges peut-être indûment l'énoncé du problème: et s'il s'agissait précisément de repérer les valeurs qui apparaissent 3 fois, et pas plus ?
Pour une liste de (N) termes, on pourrait envisager :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
FOR i:= 1 TO (N-2) DO
  BEGIN
    v:= Valeur[i];
      FOR j:= (i+1) TO (N-1) DO 
        IF (Valeur[j]=v) THEN
          BEGIN
            s:= 2;
            FOR k:= (j+1) TO N DO
              IF (Valeur[k]=v) THEN s:= s+1;
            IF (s=3) THEN <Enregistrer (v, i, j, k) dans (L1)>
                      ELSE <Enregistrer (v) dans (L2)>
          END
  END; 
<Eliminer de (L1) les termes dont la valeur (v) se retrouve dans (L2)>  // (1)

(1) La 1^re partie du code retiendra comme triplon les 3 derniers termes d'un multiplon (2) plus long.
(2) Qu'est-ce qu'on est bons niveau vocabulaire !

[tbc92]

(2) Qu'est-ce qu'on est bons niveau vocabulaire !

Oui, c'est sûr. Peut-être même qu'une recherche sur "éliminer les triplets" aurait donné quelque chose ?

Et pour cette raison, j'aurais dû a-minima utiliser le bon vocabulaire doublon/triplet/quadruplet/multiplet.

[wiwaxia]

... Et pour cette raison, j'aurais dû a-minima utiliser le bon vocabulaire doublon/triplet/quadruplet/multiplet.

Pas du tout: les termes en cause, dont j'ai moi-même allongé la liste, sont l'extension logique de "doublon" = paire de deux termes identiques, et dont l'un devient inutile. Phonétiquement, je ne les trouvais pas très heureux, rien de plus ... et rien contre ce que tu as dit.
Leur sens est confirmé par les dictionnaires: "élément présent en 2, 3 ou 4 exemplaires", et ta réponse était cohérente.

La série que tu viens de citer est d'ailleurs défectueuse, puisqu'un multiplet résulte de l'association de (m) termes qui ne sont pas forcément identiques, ni même de même nature: par exemple l'état d'un fluide est caractérisé par les données de sa pression (P), de sa masse volumique (µ) et de sa température (T) - soit donc le triplet (P, µ, T), pour lequel l'égalité de deux termes n'a aucun sens.

[tbc92]

Effectivement. Après coup, je me suis dit que triplet par exemple n'avait rien à voir avec la généralisation de doublon.

[wiwaxia]

Une condition a disparu par inadvertance du code que j'ai donné, donc je corrige:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
FOR i:= 1 TO (N-2) DO
  BEGIN
    v:= Valeur[i];
    FOR j:= (i+1) TO (N-1) DO 
      IF (Valeur[j]=v) THEN
        BEGIN
          s:= 2;
          FOR k:= (j+1) TO N DO
            IF (Valeur[k]=v) THEN s:= s+1;
          IF (s=3) THEN <Enregistrer (v, i, j, k) dans (L1)>
                   ELSE IF (s>3) THEN <Enregistrer (v) dans (L2)> // on peut avoir s = 2
        END
  END; 
<Eliminer de (L1) les termes dont la valeur (v) se retrouve dans (L2)>  //

Il y a d'ailleurs moyen de se passer de la seconde liste (L2), où s'accumulent les valeurs rencontrées plus de 3 fois en partant d'une liste de doublets (j'y tiens )

Code :

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

1
2
3
4
 
TYPE Doublet = RECORD  Valeur: TypeValeur; 
                       z: Word  END;
VAR Liste: ARRAY[1..N] OF Doublet;

dont le second terme est initialisé à zéro. On récupère la liste des triplons au terme de l'exécution des 3 boucles imbriquées:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
 
FOR i:= 1 TO (N-2) DO
  BEGIN
    v:= Liste[i].Valeur;
    FOR j:= (i+1) TO (N-1) DO 
      IF (Liste[j].Valeur=v) THEN     // Test1
        FOR k:= (j+1) TO N DO
          IF (Liste[k].Valeur=v) THEN BEGIN     // Test2
                                        Inc(Liste[i].z ); Inc(Liste[j].z ); 
                                        Inc(Liste[k].z );          // Inc(u) équivaut à u:= u + 1
                                      END;
  END;

Il suffit en effet de récupérer les valeurs associées à (z=1), puisque les égalités (1) et (2) ne sont observées qu'une seule fois pour un triplet donné (i < j < k); on les rencontre 3 fois dans la liste initiale, aux rangs (i, j, k) justement.

[wiwaxia]

Étant donné un ensemble de (m) termes de même valeur, (Liste[h].z) représente le nombre de triplets réalisables avec le terme de rang donné (h); il est probablement donné (à vue d'oeil, vous vérifiez) par l'expression:
z = (m - 1)!/(2!*(m - 3)!) = (m - 1)*(m - 2)/2 et prend les valeurs:

Code :

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

1
2
3
 
m = 3     4     5     6     ...     < 3
z = 1     3     6    10     ...     0   // pas d'incrémentation en l'absence de 3 valeurs identiques

La collecte des valeurs répétées 3 fois s'effectuera par le remplissage progressif d'une liste d'enregistrements:

Code :

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

1
2
3
4
 
TYPE Lst4E = ARRAY[0..3] OF Word;
     Tripl = RECORD  ValT: TypeValeur; Le: Lst4E  END;
ListeT: ARRAY[1..Nt] OF Tripl;

initialisée à zéro (tout au moins pour les entiers).
Le remplissage commencera à la première valeur détectée (V1) correspondant à (z=1), le terme initial étant alors:

Code :

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

ListeT[1] = (V1, (1, i, 0, 0))

PS: Au fait, un inventaire détaillé des triplons est-il nécessaire, une fois qu'ils ont été repérés ? Sur ce point, le contenu de la question est moins précis que son titre ...

Bonjour,
j'ai deux soucis
le premier est que j essaie d'applique la formule sur les doublons concernant sans y parvenir
et le second est que j'ai besoin d'aide pour la formule sur les triplons
merci

[anapurna]

salut

pourquoi passer par un tableau de record alors qu'un tableau d'entier suffit la seul contrainte est la taille de ce tableau

Code :

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

1
2
3
 
  FOR i:= 1 TO (N-2) DO
      Tab[Valeur[i]]:= Tab[Valeur[i]]+1;

il suffit de relire le tableau tab et d’éliminer tout les indice ne correspondant pas au résultat attendu

[wiwaxia]

Bonjour,

... Pourquoi passer par un tableau de record alors qu'un tableau d'entier suffit ...

Parce que le type des valeurs consignées dans le tableau initial:

Code :

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

1
2
3
TYPE Doublet = RECORD  Valeur: TypeValeur; 
                       z: Word  END;
VAR Liste: ARRAY[1..N] OF Doublet;

n'est pas donné: s'agit-il d'entiers, de réels, de chaînes de caractères, de vecteurs ... ? Tout est possible, à moins qu'une donnée m'ait échappé.

... il suffit de relire le tableau tab et d’éliminer tout les indices ne correspondant pas au résultat attendu.

Je ne vois pas bien l'idée de la solution proposée, et je crains que ce soit plus compliqué: il s'agit en effet de se débarrasser des faux triplons récupérés à l'issue de la 1^re partie de l'algorithme, d'où la nécessité d'une nouvelle énumération.
Si par exemple la liste contient des valeurs identiques (V₁, V₂) répétées 4 ou 5 fois, aux positions:
(V₁): 4 17 52 83
(V₂): 9 29 31 66 99
on retrouvera dans ListeT les réponses (V₁, 17, 52, 83) et (V₂, 31, 66, 99), qu'il faudra bien repérer par la suite.

Il m'est venu tout à l'heure l'idée d'une autre variante, qui conduirait directement à la liste cherchée; mais, faute de temps, j'y reviendrai plus tard.

[picodev]

Bonjour,

je vais peut-être dire une bêtise, mais le plus simple serait encore d'utiliser une hashtable.

[anapurna]

je suis partit effectivement du postulat que les valeurs étaient des entiers positif
ma logique est simple je fais une sorte de trie par dénombrement c'est a dire que j'utilise la valeur trouvé comme indice de tableau que j’incrémente de 1
il suffit de relire tout les indices de mon tableau résultant et si la valeur à l'indice est égale ou supérieur, à 3 nous somme en présence d'un "triplons" ou plus

il faut effectivement que le périmètre de la question soit un peu plus explicite afin de pouvoir fournir une solution approprié

[wiwaxia]

Bonsoir,

Puisqu'il faut parcourir une autre liste pour filtrer les réponses obtenues, autant insérer une boucle supplémentaire dans les trois précédentes:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
 
TYPE LstE = ARRAY[0..3] OF Word;
     Triplet = Record  Val: Type_Valeur ; Tr: LstE  END;
VAR ListeV: ARRAY[1..N] OF Type_Valeur;
    ListeT: ARRAY[1..Nt] OF Triplet;
    i, j, k, l, m, w: Word; v: Type_Valeur;
 
BEGIN
  FOR i:= 1 TO Nt DO
    FOR j:= 0 TO 3 DO ListeT[i].Tr[j]:= 0;
  m:= 0;
 
  FOR i:= 1 TO (N-2) DO
    BEGIN
      v:= ListeV[i];
      FOR j:= (i+1) TO (N-1) DO
        IF (ListeV[j]=v) THEN 
          FOR k:= (j+1) TO N DO
            IF (ListeV[k]=v) THEN                      // On vient de repérer 3 termes identiques aux rangs (i, j, k) 
              BEGIN
                w:= 3;
                FOR ll:= 1 TO N DO
                  IF (((l<>i) AND (l<>j)) AND (l<>k)) THEN          // à une nouvelle position différente des 3 précédentes ...
                    IF (ListeV[l]=v) THEN Inc(w);                   // ... on trouve un terme de même valeur
                IF (w=3) THEN BEGIN                    // Il n'y a que 3 termes de même valeur (v)
                                Inc(m); WITH ListeT[m] DO BEGIN
                                                            Val:= v; Tr[0]:= m; Tr[1]:= i; Tr[2]:= j; Tr[3]:= k 
                                                          END
                              END
              END     
    END;
END.

Si les valeurs sont d'un type complexe (tableau, enregistrement ou fichier) le test d'égalité (ListeV[.]=v) doit être remplacé par une fonction booléenne appropriée (Test(V1, V2: Type_Valeur)).

Il existe sûrement des variantes permettant d'augmenter la rapidité d'exécution au niveau de la dernière boucle.

[anapurna]

salut

en regardant ton code je me pose quelque question

1°) pourquoi dans le triplet tu enregistre la position m qui ne sert à rien ici

Code :

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

1
2
3
4
5
6
7
8
WITH ListeT[m] DO 
		     BEGIN
               Val:= v; 
		       Tr[0]:= m; //??? je ne comprend pas l'interet
		       Tr[1]:= i; 
		       Tr[2]:= j; 
		       Tr[3]:= k 
             END

2°) pourquoi pour la dernière boucle celle qui sert a savoir si c'est un vrai triplet tu repart de l'indice 1
de plus il ne faut pas écrire

Code :

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

1
2
3
4
 
FOR ll:= 1 TO N DO
   IF (((l<>i) AND (l<>j)) AND (l<>k)) THEN      // à une nouvelle position différente des 3 précédentes ...
               IF (ListeV[l]=v) THEN

mais

Code :

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

1
2
3
4
 
FOR ll:= k+1 TO N DO
   IF (((ll<>i) AND (ll<>j)) AND (ll<>k)) THEN      // à une nouvelle position différente des 3 précédentes ...
               IF (ListeV[ll]=v) THEN

une autre alternative si la liste est trié serais de parcourir les éléments et de "bondir" ce qui nous permet de réduire le nombre de boucle

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
i:=0
While i < N do
begin
   if (ListeV[i]=ListeV[i+1]) and (ListeV[i+1]=ListeV[i+2]) Then 
   BEGIN
     if (ListeV[i+2]<>ListeV[i+3]) Then  // on en a que 3 identique
     BEGIN
	  WITH ListeT[m] DO 
	  BEGIN
              Val:= ListeV[i]; 
	      Tr[1]:= i; 
	      Tr[2]:= i+1; 
	      Tr[3]:= i+2; 
          END 
	  I := I+2;
     END
     ELSE //Plus de 3
     BEGIN
        j:=i+3  // On sais que les premier element sont identique donc pas besoin de faire le test sur eux 
        Egale :=True;
        While (j < N) and Egale do
        BEGIN  
	   Egale := False; 
           if (ListeV[i]=ListeV[j])  Then 
           BEGIN
 	      j := j+1
              Egale :=True;
           end;
        end;
        i:=j;// On déplace l'index a la fin des éléments identique 	
   END;
   Inc(I);// on passe au suivan
end;

je n'ai pas vérifier mon code mais l'esprit de ce que je veux faire est là

[wiwaxia]

Salut,

1°) pourquoi dans le triplet tu enregistre la position m qui ne sert à rien ici

Parce que la dernière valeur de (m) enregistrée représente de nombre total de triplons. Cependant, j'aurais pu effectivement m'en passer et me contenter d'une liste de 3 entiers, ce qui réduit l'espace mémoire occupé par la variable ListeT.
Je poursuivais sans doute une vague idée, perdue en cours de route.
Bonne remarque donc, qui conduit à une version allégée du programme:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
TYPE LstE = ARRAY[1..3] OF Word;
     Triplet = Record  Val: Type_Valeur ; Tr: LstE  END;
VAR ListeV: ARRAY[1..N] OF Type_Valeur;
    ListeT: ARRAY[1..Nt] OF Triplet;
    i, j, k, l, m, w: Word; v: Type_Valeur;

BEGIN
  FOR i:= 1 TO Nt DO
    FOR j:= 1 TO 3 DO ListeT[i].Tr[j]:= 0;
  m:= 0;

  FOR i:= 1 TO (N-2) DO
    BEGIN
      v:= ListeV[i];
      FOR j:= (i+1) TO (N-1) DO
        IF (ListeV[j]=v) THEN 
          FOR k:= (j+1) TO N DO
            IF (ListeV[k]=v) THEN                      // On vient de repérer 3 termes identiques aux rangs (i, j, k) 
              BEGIN
                w:= 3;
                FOR l:= 1 TO N DO
                  IF (((l<>i) AND (l<>j)) AND (l<>k)) THEN          // à une nouvelle position différente des 3 précédentes ...
                    IF (ListeV[l]=v) THEN Inc(w);                   // ... on trouve un terme de même valeur
                IF (w=3) THEN BEGIN                    // Il n'y a que 3 termes de même valeur (v)
                                Inc(m); WITH ListeT[m] DO BEGIN
                                                            Val:= v; Tr[1]:= i; Tr[2]:= j; Tr[3]:= k 
                                                          END
                              END
              END     
    END;
END.

2°) pourquoi pour la dernière boucle celle qui sert a savoir si c'est un vrai triplet tu repart de l'indice 1

a) Une faute de frappe m'a échappé (c'est un doublon !)

Code :

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

FOR ll:= 1 TO N DO

... que tout le monde aura corrigée, je pense.
b) Parce que si l'on veut éliminer tout faux positif, il faut, pour chaque triplet (i, j, k) détecté, s'assurer que la valeur observée ne se rencontre ni avant (l < i), ni au-delà (k < l), ni à l'intérieur (i < l < k) du créneau correspondant.

Supposons que la valeur (V₀) se retrouve identiquement aux rangs (11, 20, 33, 45, 62 et 88) - c'est un sextuplon

Le triplet (i, j, k) = (20, 45, 62) qui satisfait aux conditions ListeV[i] = ListeV[j] = ListeV[k] , ne constitue pas pour autant une triplon, parce que la même valeur en cause se retrouve aussi avant la première borne (l₁ = 11 < 20), au-delà de la troisième (l₃ = 88 > 62) et entre les deux (20 < l₂ = 33 < 62); il est donc bien nécessaire de balayer le domaine entier [1; N] .

Je comprends l'objection de la longueur de l'exécution, quoique l'amorçage de la quatrième boucle soit relativement rare ... il faudrait faire des essais.
On pourrait reprendre l'idée de partir d'une liste de doublets (voir les posts du 13/01)

Code :

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

1
2
3
TYPE Doublet = RECORD  Valeur: TypeValeur; 
                       z: Word  END;
VAR Liste: ARRAY[1..N] OF Doublet;

afin de repérer les valeurs plusieurs fois répétées; mais les 3 premiers et derniers termes d'un multiplon
- par exemple (11, 20, 33, 45, 62, 88) - amèneront toujours des difficultés.

[anapurna]

salut

dans ce cas pourquoi ne pas mettre dans la liste résultante toutes les valeur supérieur ou égale 3
ensuite on fait une recherche dans cette liste avant de lancer les diverses boucles
de cette façon on évite de rechercher une valeur déjà traité et la recherche ne se fait que sur les éléments suivant.

on peut même si le nombre de triplons est conséquent penser à trier ou indexer la liste résultante de cette manière une recherche dichotomique ou autre pourra être mises en place afin d'augmenter la vitesse de recherche de la valeur dans ce tableau

[wiwaxia]

dans ce cas pourquoi ne pas mettre dans la liste résultante toutes les valeur supérieur ou égale 3
ensuite on fait une recherche dans cette liste avant de lancer les diverses boucles

C'est justement ce que j'avais proposé au début, en codant 3 boucles imbriquées.

On vérifie facilement que la dernière version proposée détecte correctement les 20 triplons dispersés dans la liste de 800 termes ci-dessous, crée très simplement de la façon suivante:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
 CONST Imax = 7; Jmax = 100; Nmax = (Imax + 1) * Jmax; 
 
 PROCEDURE InitListe(VAR Lv: LstV);
   VAR i, j, J0, k: Word;
   BEGIN
     k:= 0;
     FOR i:= 0 TO Imax DO BEGIN
                            J0:= 10 * i;
                            FOR j:= 1 TO Jmax DO BEGIN
                                                   Inc(k); Lv[k]:= J0 + j
                                                 END
                          END
   END;

Les triplons commencent entre 21 et 30 d'une part, et 141 et 150 d'autre part. La liste contient encore des groupes plus importants, notamment des septuplons entre 61 et 110.

Il serait intéressant
a) d'observer l'évolution du temps de calcul en fonction de la longueur de la liste;
b) que picodev développe la suggestion qu'il avait exprimée, concernant le recours aux tables de hachage.

[tbc92]

Puisqu'on développe le sujet, et qu'on en arrive aux questions de performance, voici ma pierre.

Si on a des problèmes de performance, la solution passe par un tri : On trie notre liste (en mettant peut-être à côté de chaque enregistrement un identifiant, pour pouvoir reconstituer le tri initial tout à la fin du traitement.
Grâce à ce tri, on a l'assurance que tous les enregistrements contenant une même valeur seront consécutifs. Et donc aucune difficulté à compter le nombre d'occurrences pour chaque valeur de clé.

On aboutit à un algorithme en gros en n*log(n).

[wiwaxia]

... Grâce à ce tri, on a l'assurance que tous les enregistrements contenant une même valeur seront consécutifs. Et donc aucune difficulté à compter le nombre d'occurrences pour chaque valeur de clé.
On aboutit à un algorithme en gros en n*log(n).

Bonne solution !

[anapurna]

salut

la solution de la liste trié c'est ce que j'avais proposé avec ma boucle while ...
je dis ça je dis rien