Tuer les doublons dans un tableau

[Valentin03]

Bonjour messeigneurs,
Le gueux numérique sollicite de votre bienveillant manoir, un code qui permettrait d'éliminer les doublons dans un tableau.
Le problème c'est qu'il faudrait que ce code soit en langage FCF (français de Clermont Ferrand)
Ou à défaut, snif ! en pseudo code.
L'ajout de moult commentaires serait fort apprécié.
Que le ciel m'accorde grâce, avant l'arrivée des dragons itératifs.
La main de ma fille (72ans) sera la récompense.

[XENSECP]

Un tableau de quels objets? Tu as pas un petit lien pour FCF?

[joel76]

La transformation doit s'effectuer dans le même tableau ou dans un autre tableau ?

[LeJeu]

Bonjour messeigneurs,
Le gueux numérique sollicite de votre bienveillant manoir, un code qui permettrait d'éliminer les doublons dans un tableau.
Le problème c'est qu'il faudrait que ce code soit en langage FCF (français de Clermont Ferrand)
Ou à défaut, snif ! en pseudo code.
L'ajout de moult commentaires serait fort apprécié.
Que le ciel m'accorde grâce, avant l'arrivée des dragons itératifs.
La main de ma fille (72ans) sera la récompense.

Je propose de trier le tableau de 1 ->n
puis d'une boucle de 1 -> n-1
de comparer l'elt i avec l'elt i+1
en cas d'egalité on détruit i+1 et décrémente i et n
de telle facon de comparer au prochain tour le i et le i+2 précédents

Code: Tout sélectionner

trier tableau 1->n

pour i =1 to n-1
    si  tab[i] =  tab[i+1]
        recopier  tab [i+2 - >n] en tab [i+1 -> n-1]   // on recule le reste du tableau d'une case
        i = i-1     // on repartira de tab[i] au prochain tour
        n= n-1   // le tableau est plus petit
    fin si
fin pour 


[joel76]

Voici ce que je propose (cela évite de trier le tableau)
tab : tableau de n éléments à purger
j : indice de recopie dans le tableau, on est sur que tous les éléments du tableau d'indice inférieur ou égal à j sont uniques, au départ j = 1

Code: Tout sélectionner

pour i de 2 à N faire
   t  tab[i] faire
       t  i alors          
         tab[j+1] <- tab[i]
      fin si
      j <- j+1
   fin si
fin pour

La nouvelle taille du tableau est j.

[Valentin03]

La transformation doit s'effectuer dans le même tableau ou dans un autre tableau ?

Autant de tableaux temporaires que nécessaires (y sont pas chers, c'est pas des Delacroix)

[Valentin03]

Merci beaucoup à vous deux. Je vais essayer ça.
.

[Valentin03]

Le pseudo code, il est évident que pour pouvoir en tirer queque chose, il faut en connaître,
et donc en apprendre le maniement, que l'on appellerait par exemple: Syntaxe.

Et ben moi j'vous l'dis: Celui qui a inventé ça; il devait pas fumer que de la paille.
Parce que remplacer une syntaxe par une autre, fallait déjà y penser.

Heu.. je pense qu'il est inutile d'espérer trouver la traduction française?

Wikipédia dixit: "Il n'existe pas de réelle convention pour le pseudo-code."
Mayrde..ça commence mal.
...15 entrées Google plus tard: Forum des proffessionels en informatique:
Toto13 (Modérateur) dixit: "le pseudo code revient à décrire en français ce que fait_en programmation..." (oui, il manque le: "tu". C'est du pseudo français)
Un peu pus loin: Pseudocode et programmation dans le style des pièces de Chek-spire. Bon, là ça part en live.

Peut-être qu'en transférant à la petite cuillère une douzaine de tableaux les uns dans les autres, à travers une passoire à thé ?

Fatal-Error ! Help me! Tu n'aurais pas quelque chose de plus prés de la chaise que du clavier?

Accepte toutes suggestions (sauf visite des îles grecques.)

[fatal_error]

slt,

sans trier la base de la base

Code: Tout sélectionner

tableauAvecDoublon=[];
tableauSansDoublon=[];
pour chaque elem e de tableauAvecDoublon
 si e est PAS dans tableauSansDoublon
   ajouter e dans tableauSansDoublon
 finsi
finpour


tester si e est dans tableauSansDoublon est trivial.
ajouter e dans tableauSansDoublon devrait letre aussi!

[LeJeu]

Code: Tout sélectionner

trier tableau 1->n

pour i =1 to n-1
    si  tab[i] =  tab[i+1]
        // on recule le reste du tableau d'une case
        recopier  tab [i+2 - >n] en tab [i+1 -> n-1]   
        i = i-1     // on repartira de tab[i] au prochain tour
        n= n-1   // le tableau est plus petit
    fin si
fin pour 


J'avais été un peu lourdingue ci dessus en déplacant toute la partie droite du tableau, on peut faire mieux avec deux indices gauche et droite

on part toujours du tableau trié

Code: Tout sélectionner

gauche  tab[droite]
        gauche  droite
                tab[gauche] <- tab[droite]
         fin si
     finsi
      droite <-droite +1
 
fin tant que

le tableau est nettoyé entre 1 et gauche (nouvelle taille) et on fait au maximum (n-2) déplacements

@valentin03 - le pseudo code permet d'exprimer en algo sans rentrer dans la rigueur du langage final d'implémentation - tu ecris un peu comme tu veux si tu arrives à te faire comprendre

tu mets en évidence les boucles / les tests d'arrets ....

si tu arrives-à vérifier que l'algo ci dessus est correct (ou non), à voir comment le coder, le but est atteint

[joel76]

Et ben moi j'vous l'dis: Celui qui a inventé ça; il devait pas fumer que de la paille.

Il avait compris les nécessités de formalisation pour écrire un code correct.

[Valentin03]

..........ans tableauSansDoublon est trivial..

Mais hélas, ce qui est trivial pour l'un, ne l'est pas forcément pour l'autre.

@LE JEU. C'est sympa, et je te remercie de ne pas m'avoir envoyer bouler.
Avec ces quelques mots en plus, je devrais m'en sortir
Par contre:

.....à vérifier que l'algo ci dessus est correct (ou non),

Le: ..(ou non), n'est pas très rassurant.
Je sacrifierai le chat pour compenser la part d'incertitude, ça devrait le faire.

Il avait compris les nécessités de formalisation pour écrire un code correct.

Alors c'est comme pour Markx,; le temps aura galvaudé une belle idée.
Bon, je vous laisse, j'ai un retour de multibug qui me donne à penser qu'il a encore des Windows 95 qui traînent.
Bonne journée à tous....

[LeJeu]

Code: Tout sélectionner

tableauAvecDoublon=[];
tableauSansDoublon=[];
pour chaque elem e de tableauAvecDoublon
 si e est PAS dans tableauSansDoublon
   ajouter e dans tableauSansDoublon
 finsi
finpour

Mais hélas, ce qui est trivial pour l'un, ne l'est pas forcément pour l'autre.
.

Comme tu vois, le pseudo code peut donner la démarche mais pas le détail des opérations... par contre ce que donne fatal_error comme démarche est le plus simple ( par rapport à l'algo de joel76 qui travaille dans un seul tableau ...)

et d'ailleurs tu peux simplifier l'algo de joël 76 pour obtenir de façon triviale :

Code: Tout sélectionner

pour chaque elem elt de tableauAvecDoublon

   t  tableauSansDoublon [t] faire
       t =1) && ( (cmp = tab_i-tab[j]) =j; k--)
               tab[k+1] = tab[k];

            tab[j] =tab_i;
         }
         nbok++; // on a un élémnt de plus
      }
   }

   // le tableau est nettoyé - nouvelle taille : nbok
   return nbok;
}


Bien sûr c'est algo peut aussi dégénéré en n² si le tableau est trié "à l'envers" au départ, mais souvent dans "la vrai vie" on est plutot dans le cas de nouveaux éléments ajoutés en queue d'un tableau plus ou moins déjà trié, ( fusion de deux annuaire par exemple) l'algo ci dessus est alors plutot efficace

[Valentin03]

Bon ben j'ai pu qu'à me mettre au C. Ce dernier code a l'air plus charnu.
Celui de LE JEU ( je peux me f...tre dedans) mais j'ai l'impression qu'il ne tue que les doublons consécutifs.
Si quelqu'un a un lien, qui ne soit pas le BA ba,
Mais où je trouverais rapidement une bonne grosse liste des significations de ces trucs:
La syntaxe quoi.

ça-->++ et ça-->&& et--> != et--> _ (ça:_ en python c'est dans les noms de variables.)

Et merci d'avoir pris la peine d'essayer de vous (me) faire comprendre.

[LeJeu]

Bon ben j'ai pu qu'à me mettre au C. Ce dernier code a l'air plus charnu.
Celui de LE JEU ( je peux me f...tre dedans) mais j'ai l'impression qu'il ne tue que les doublons consécutifs.
Si quelqu'un a un lien, qui ne soit pas le BA ba,
Mais où je trouverais rapidement une bonne grosse liste des significations de ces trucs:
La syntaxe quoi.

ça-->++ et ça-->&& et--> != et--> _ (ça:_ en python c'est dans les noms de variables.)

Et merci d'avoir pris la peine d'essayer de vous (me) faire comprendre.

pardon,

c'est pour ça que le pseudo langage existe ...
je n'ai pas eu le courage de te traduire mon code ( désolé j'ai pseudo codé dans ma tête - et codé direct)

sinon pour info
for ( i = 2; i 0

Sinon, oui le pgm ne tue que les doublons consécutifs.... mais les rend consécutifs justement....
testé avec

123451

111222
121212

12345
54321

1234512345
1234554321

[Benjamin]

Bonsoir,

Ca dépend de beaucoup du langage final utilisé en fait. Typiquement, la technique en Perl c'est d'utiliser un hachage "elem_deja_vu" et de faire

Code: Tout sélectionner

for $i in @tab {
    if !$elem_deja_vu{$i}++ {
        push $i, @$tab_sans_doublon;
    }
}

La technique ici est de tester un élément qui lui même va s'incrémenter lors du test. Au départ, tout le monde vaut 0, donc le if est positif, mais dès que le test est fait sur un élément, ça incrémente la valeur du hachage pour cet élément là, et le test suivant sera alors nécessaire négatif.

De plus, la valeur dans le hachage permet alors de connaitre le nombre de doublons qu'il y avait.

[joel76]

Maintenant, si ce sont des nombres entiers positifs à trier (on peut adapter pour des nombres relatifs), il y a un algo en 3n si n est la taille du tableau initial, il est inspiré du tri du "facteur" :
passe 1 : on repère le plus grand entier N du tableau.
On crée un tableau de taille N+1 (allant de 0 à N) initialisé à 0
passe 2 : on parcourt le tableau initial, et on incrémente la case du second tableau d'indice l'element courant du premier tableau
passe 3 : on remplit le premier tableau en parcourant le second tableau, chaque fois qu'on rencontre une case non nulle, on inscrit son indice dans le premier tableau.

[Valentin03]

Bon sang, je n'ai pas précisé que c'étaient des chaînes.

La technique ici est de tester un élément qui lui même va s'incrémenter lors du test. Au départ, tout le monde vaut 0, donc le if est positif, mais dès que le test est fait sur un élément, ça incrémente la valeur du hachage pour cet élément là, et le test suivant sera alors nécessaire négatif.

C'est bien autour de ça que je tourne depuis une semaine.
Que je caresse l'animal, sans parvenir à m'en saisir.
Dur..dur..De n'être qu'un "amateur". Mais scrogneugneu!, je ne lâcherai pas le morceau !
Merci ..LeJeu.. pour les infos.