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  
 
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

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.

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).

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

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.

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)

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 :  
 

 
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