Forum |  HardWare.fr | News | Articles | PC | Prix | S'identifier | S'inscrire | Aide | Shop Recherche
1796 connectés 

  FORUM HardWare.fr
  Programmation
  Python

  Trier les éléments d'une liste afin de maximiser l'espacement de deux occurrence

 



 Mot :   Pseudo :  
 
Bas de page
Auteur Sujet :

Trier les éléments d'une liste afin de maximiser l'espacement de deux occurrence

n°2346242
dede_sav
Posté le 16-02-2020 à 18:56:39  profilanswer
 

Bonjour,
 
Je planche sur une petite problématique rigolote.
Je cherche à maximiser la distance au sein d’un tableau entre deux occurrences.  
Concrètement prénom le tableau suivant:
{a, a, a, b, b, b, c, c, c}  
Je souhaite trouver le tableau suivant:
{a, c, b, a, c, b, ...
Ou {b, a, c, b, a, c, ...} bref que les meme lettre se trouve espace par les 2 autres lettres.
 
Voilà, vous avez 4h le temps que mon train arrive :o  
 
Plus sérieusement, je suis parti sur une approche de bourrin.
1 - je parcours la liste et je prend un élément unique de chaque  
2 - je tris cette liste unique par ordre alphabétique  
3 - je supprime les éléments de la liste unique du tableau de départ  
4 - je stock/concat dans un nouveau tableau
Loop ...  
 
Mais je suis persuadé que l’élite HFR peut me trouver une méthode plus efficiente  
 
 
Edit: J’ai bien entendu pensé à chercher le pattern initiale issue du premier tri afin de l’appliquer au reste du tableau.  
Mais ça manque de truc intéressant à mon goût, genre des arbres, du deep learning voir même de l’ai (en ada of course)
 
Merci d’avance !  
Dd


Message édité par dede_sav le 16-02-2020 à 19:01:53
mood
Publicité
Posté le 16-02-2020 à 18:56:39  profilanswer
 

n°2346266
rufo
Pas me confondre avec Lycos!
Posté le 17-02-2020 à 09:55:27  profilanswer
 

Je ne pense pas qu'il existe une algo exact pour résoudre ce pb, en tout cas, pas dans un temps polynomial. Je te propose un algo génétique.
1) Tu génères une population de n individus. Un individu doit avoir le même nb d'instances de lettres que ton vecteur d'entrée mais les lettres sont dans un ordre aléatoire.
2) tu définies un fonction d'évaluation qui va affecter un score à chaque individu de ta population. Le score le plus faible (ou le score le plus fort) est attribué à l'individu qui a le plus d'écart entre ses lettres. Celui là, tu le garde en mémoire. Si y'a une égalité entre plusieurs individus, à toi de voir si tu veux le garder aussi en mémoire.
3) Pour générer la population suivante, tu vas définir 2 points de coupe aléatoirement (un point de coupe est un indice dans ton tableau à partir duquel tu vas couper le vecteur, y'a un point de coupe vers le haut et un autre vers le bas du vecteur) et prendre chaque individu de la population que tu viens d'évaluer pour leur appliquer les 2 points de coupe. Tu vas te retrouver avec des vecteurs de même taille qu'avant mais avec leur partie haute et basse inversées.
4) Pour cette nouvelle population, tu retournes en 2).
 
Appliquer l'algo x fois. Normalement, il va converger assez rapidement vers au moins une bonne solution. C'est une heuristique, donc t'auras jamais l'assurance d'avoir LA meilleure solution.
 
Pour un vecteur d'entrée de moins de 15 éléments, je te recommande une population de 250 individus au minimum. Pour le nombre de tours de boucle, tu peux déjà voir ce que ça donne avec 50. Ces 2 paramètres vont croître exponentiellement avec l'augmentation de la taille de ton vecteur. Autant te dire qu'au-delà de 30 éléments dans ton vecteur, ça va devenir très compliqué.
 
Cet algo a fait ses preuves pour minimiser la place perdu sur un ensemble de fichiers à graver sur x CD retenus ainsi que pour trouver les combinaisons de pizzas qui permettent d'utiliser exactement x tickets restos papier. ;)


---------------
Astres, outil de help-desk GPL : http://sourceforge.net/projects/astres, ICARE, gestion de conf : http://sourceforge.net/projects/icare, Outil Cantine Calandreta : http://sourceforge.net/projects/canteen-calandreta
n°2346272
Devil'sTig​er
Jee & Cee on the rock !
Posté le 17-02-2020 à 11:16:39  profilanswer
 

La premiere reponse de ca peut etre ?
 
https://stackoverflow.com/questions [...] m-distance
 
Ca semble etre ce que tu cherches sauf que tu es dans un environnement discret (ce qui est habituellement pas un pb dans ce sens).


---------------
JunZZi | Jee & Cee
n°2346313
dede_sav
Posté le 18-02-2020 à 08:54:55  profilanswer
 

Merci pour vos réponses. J'apprécie beaucoup celle de rufo ! Un peu de RO ne m'a fait pas de mal.

n°2346314
rufo
Pas me confondre avec Lycos!
Posté le 18-02-2020 à 09:04:52  profilanswer
 

Les algos génétiques sont plus dans la cat biomimétique que la recherche opérationnelle (algo du simplex, programmation dynamique, LPT, Johnson...).
 
Edit : le gros avantage des algos génétiques, c'est qu'ils sont très faciles à implémenter (pas de gestion complexe ou lourde de structures de données, pas de calculs compliqués en général, juste une fonction d'éval) et ont un bon ratio nb de lignes de code/efficacité de la solution trouvée/temps d'exécution :) En fait, tout tient à la qualité de la fonction d'éval et à la façon de générer la population suivante pour que la convergence vers une bonne solution voire la meilleure se fasse le plus vite possible.


Message édité par rufo le 18-02-2020 à 09:08:14

---------------
Astres, outil de help-desk GPL : http://sourceforge.net/projects/astres, ICARE, gestion de conf : http://sourceforge.net/projects/icare, Outil Cantine Calandreta : http://sourceforge.net/projects/canteen-calandreta
n°2346665
mathieuu
Posté le 25-02-2020 à 15:33:47  profilanswer
 

Salut,
 
Je n'ai pas tester donc je me trompe peut être, mais en solution naïve j'ai l'impression qu'en parcourant le tableau tu dois pouvoir très facilement compter combien il y a d'occurrence de chaque élément, et il ne reste plus qu'a trier par nombre d’occurrence pour obtenir le pattern voulu (et si on veut reconstruire le tableau il suffit de diminuer le nombre d'occurrence de chaque et de ne prendre en compte que ceux qui ont encore des occurrences à mettre en place)

n°2346685
mathieuu
Posté le 25-02-2020 à 16:58:33  profilanswer
 

Bon bah finalement j'ai trouvé 5 minutes pour faire un petit bout de code en javascript dans la console de firefox (par contre j'ai tester vraiment très à la va vite en augmentant diminuant le nombre de a de b et de c).
J'ai l'impression que cela fonctionne :  
 

Code :
  1. var tab_init=["a", "a", "a", "b", "b", "b","b", "c", "c"];
  2. var compteur=new Object;
  3. //On fait une "table associative" pour compter combien de fois il y a chacun des elements
  4. tab_init.forEach( valeur => compteur[valeur]>0 ? (compteur[valeur]+=1) : compteur[valeur]=1);
  5. //on passe en tableau "tuple" ordonné par valeur decroissante, pompé globalement ici : https://stackoverflow.com/questions [...] javascript
  6. var tuples = []; for (var key in compteur) tuples.push([key, compteur[key]]); tuples.sort(function(a, b) {a = a[1];b = b[1];return a > b ? -1 : (a < b ? 1 : 0);});
  7. //a priori le tableau de tubles correspond au "pattern principale", maintenant on construit le tableau resultat en tenant compte du nombre d'element si certains sont moins nombreux que d'autres.
  8. var tab_final=[];
  9. while(tuples[0][1]>0)
  10. {
  11. for (var i = 0; i < tuples.length; i++) {
  12.  if(tuples[i][1]>0)
  13.     {
  14.   tab_final.push(tuples[i][0]); tuples[i][1]--;
  15.     }
  16.   }
  17. }
  18. tab_final;


 
PS : j'ai fait ça vite fait, je ne suis pas convaincu que passé par un object puis un par  tableau de tuples soit la meilleur façon d'obtenir le tableau de fin  :whistle:


Aller à :
Ajouter une réponse
  FORUM HardWare.fr
  Programmation
  Python

  Trier les éléments d'une liste afin de maximiser l'espacement de deux occurrence

 

Sujets relatifs
mousover java sur plusieurs éléments en même temps[latex] Création de liste dans un template
Afficher / masquer div en fonction d'une liste déroulante (jQuery/JS)Dans une liste de mails exclure les gmail
XSLT 1.0 - Grouper par liste de noeuds identiquesPHP Trier un fichier csv volumineux
Trier un fichier traceactualiser donnée database via liste deroulante ajax
[résolu] liste A dans B, modifier A modifie B ?Aide vba word choix dans une liste
Plus de sujets relatifs à : Trier les éléments d'une liste afin de maximiser l'espacement de deux occurrence


Copyright © 1997-2018 Hardware.fr SARL (Signaler un contenu illicite) / Groupe LDLC / Shop HFR