Bonjour,
Je n'y connais rien en algorithme, je souhaiterais créer un arrangement avec une liste départ et une liste résultat arrangée, de telle façon qu'un maximum de nombres identiques (allant de 1 à 70) soient dans une même colonne.
Est-ce possible?
j'ai essayé avec excel mais je n'y arrive pas.
je joins un bout d'exemple en fichier image joint. (le vrai fichier comporte une 30 de lignes)
merci
C'est un peu petit
Rien ne sert de penser, il faut réfléchir avant - Pierre Dac
Bonjour, est-ce mieux?
Pour ce qui me concerne, j'ai mal compris la question.
Tu dis que ton fichier d'origine comporte une trentaine de lignes.
Mais combien de colonnes ?
Et puis que signifie : un maximum de nombres identiques soient dans une meme colonne ?
Rien n'interdit donc que la plus longue des colonnes de ta liste arrangée, ait plus de lignes que ton fichier d'origine.
Bonjour, il y a 5 colonnes avec nombres (sans doublon en ligne) avec 30 lignes environ.
La restitution doit se faire de la même façon que le fichier départ mais " nombres arrangés, permutés" dans chaque ligne pour avoir le maximum de nombres identiques dans les mêmes colonnes (voir mon fichier joint) mais bien sûr il y aura des cas (lignes) avec impossibilité (mon fichier joint est du monde des bisounours...)
merci
Y'a pas de raison, mais tel qu'il est posé je ne pense pas qu'on puisse faire mieux qu'une approche en force brute (à moins d'ajouter des contraintes sur le contenu des cellules). Avec 5 colonnes cela fait 5x4x3x2=120 permutations possibles par ligne, 30 lignes donc 4600 possibilités. C'est tout-à-fait faisable. Il suffit de programmer une boucle qui génère chaque possibilité, mesure le nombre de maximum de nombres identiques dans chaque colonne pour chaque possibilité, et à la fin te renvoi les permutations pour le ou les gagnants.Envoyé par Roger788
A moins d'avoir mal compris la solution me semble assez simple.
Vous comptez le nombre de 1, le nombre de 2, le nombre de 3 etc, jusqu'à 70
Si vous avez plus de 30 (nb de lignes) fois un même nombre, le remplissage est impossible, sinon vous commencez à remplir la première colonne depuis le haut vers le bas avec, admettons les 1 (s'il y en a) jusqu'à ce qu'il n'y ait plus de 1 (ne stockez pas ces nombre, comptez combien il en reste à placer) et vous continuez de la sorte avec les 2 etc.
Si une colonne est remplie, vous passez à la suivante.
En tout cas on ne comprend pas la même chose. Je crois que tu n'as pas vu que les cellules ne peuvent changer de lignes, et de mon coté je me suis planté sur le nombre de possibilités... 120^30 et non 120x30... une paille...
D'accord, donc l'indication suivante
n'était pas une simple suggestion sur la méthode à employer.
(je préférais le vérifier, on ne sait jamais...)
Donc du coup, ca va faire beaucoup pour de la brut force.
Je viens de tester une méthode (en Pascal) qui a l'air de donner des résultats à peu près corrects avec un bon compromis pour le résultat et les performances.
je l'ai testé en réel, avec un tableau 5*30 initialisé au hasard avec des nombres allant de 1 à 70.
L'algorithme de base :
On évalue le tableau.
On prend deux colonnes au hasard.
On permute ces deux colonnes
On évalue le tableau.
Si l'évaluation après permutation est moins bonne qu'avant (en pourrait moduler ici pour permettre un "recuit"), on permute à nouveau les deux colonnes pour revenir à la meilleur configuration.
L'évaluation du tableau (on donne une note à la configuration) se fait de la manière suivante :
On met la note à 0
On parcours les nombres avec k allant de 1 à 70
On parcours les colonnes
On met P à 0 (à chaque nouvelle colonne)
On parcours les lignes
Si la cellule (ligne/colonne) contient la valeur k alors on incrémente le nombre P, puis Si P est plus grand que 1 alors on augmente la note de 1
Résultat :
Après 10000 essais on atteint un résultat pas trop mauvais, qui peut s'améliorer un tout petit peu en relançant.
Durée environ 1 minute sur mon PC, sachant que le programme n'est pas super optimisé et affiche les permutations "en live".
A mon sens, il y plus simple, à moins que je ne saisisse pas bien l'énoncé.
-On permute les colonnes comme on veux ?
-On optimise UNE colonne !?
-Nb maximise le nb de chiffres identiques de cette colonne.?
si c'est cela , il faut commencer par lister les nb les plus fréquents et la colonne y afférant.
puis effectuer ligne par ligne le cgt nécessaire.
j'ai du louper un épisode tellement cela parait simple.
puis
y'a quelque chose qui cloche là dedans, j'y retourne immédiatement !
Je me suis posé la même question, mais apparemment la contrainte c'est que les nombres ne peuvent pas être replacés ailleurs que sur la même ligne, d'où le terme "permutation" qui n'est pas une option mais un prérequis.
cela ne change rien à ma proposition, mais je doit compléter mon premier point.
si le but n'est que d'optimiser UNE seule colonne.
je compte le nb de colonnes diff ou chaque chiffre apparaît ( c'est plus explicite )
je choisi le "vainqueur".
je n'ai plus qu'à permuter ligne à ligne en prenant par exemple la ligne 1 comme objectif.
j'espère être plus clair.
y'a quelque chose qui cloche là dedans, j'y retourne immédiatement !
reste un non dit :
est ce qu'une colonne (6;6;6;6;1) est "meilleure" qu'une colonne (6;6;6;2;2) ?
comment les classifier ?
ce n'est pas explicite.
Dernière modification par ansset ; 20/11/2016 à 12h41.
y'a quelque chose qui cloche là dedans, j'y retourne immédiatement !
Voici le code correspondant à l'algorithme proposé :
(En Pascal, programmé avec l'editeur/compilateur Lazarus)
Code:unit Principal; {$mode objfpc}{$H+} interface uses Classes, SysUtils, Forms, Controls, Graphics, Dialogs, Grids, StdCtrls; type { TMain } TMain = class(TForm) bt1: TButton; // Bouton de lancement du tri lb1: TLabel; // Permet l'affichage de la note dévaluation sg: TStringGrid; // Contient le tableau en visuel procedure bt1Click(Sender: TObject); procedure FormShow(Sender: TObject); private { private declarations } public { public declarations } procedure Initialisation(); procedure RempliTableau(); procedure TriTableau(); procedure PermuteTableau(x1,x2,y: integer); function EvalueTableau(): integer; end; // Variables globales var Main : TMain; // Fenetre de type TMain NbCol : integer; // Nombre de colonnes du tableau NbLig : integer; // Nombre de lignes du tableau NbNum : integer; // Nombre de "Nombres" implementation {$R *.lfm} { TMain } //****************************************************************************// //** Fonction d'évaluation du tableau **// //** Retourne la note du tableau **// //****************************************************************************// function TMain.EvalueTableau(): integer; var e,n : integer; k1,k2 : string; x,y : integer; nb : integer; begin e:=0; for n:=1 to NbNum do begin k1:=inttostr(n); for x:=0 to NbCol-1 do begin nb:=0; for y:=0 to NbLig-1 do begin k2:=sg.Cells[x,y]; if k1=k2 then begin nb:=nb+1; if nb>1 then e:=e+1; end; end; end; end; EvalueTableau:=e; end; //****************************************************************************// //** Permutation du tableau colonnes x1 avec x2 sur le ligne y **// //** (peut être optimisé) **// //****************************************************************************// procedure TMain.PermuteTableau(x1,x2,y: integer); var k1,k2 : string; begin k1:=sg.Cells[x1,y]; k2:=sg.Cells[x2,y]; sg.Cells[x1,y]:=k2; sg.Cells[x2,y]:=k1; end; //****************************************************************************// //** Tentative de tri du tableau par permutation/évaluation **// //****************************************************************************// procedure TMain.TriTableau(); var fin : boolean; x1,x2,y : integer; nbe,nbem : integer; ev1,ev2 : integer; begin fin:=false; nbem:=10000; // Nombre d'essais max nbe:=0; // Compteur du nombre d'essais repeat x1:=random(NbCol); repeat x2:=random(NbCol); until x1<>x2; y:=random(NbLig); ev1:=EvalueTableau(); PermuteTableau(x1,x2,y); ev2:=EvalueTableau(); if ev1>ev2 then begin PermuteTableau(x2,x1,y); end else begin // En option, affiche la progression sg.Refresh; lb1.Caption:='Evaluation = '+inttostr(ev2); lb1.Refresh; end; nbe:=nbe+1; if nbe>nbem then fin:=true; until fin; // Affiche l'évaluation finale ev1:=EvalueTableau(); lb1.Caption:='Evaluation = '+inttostr(ev1); end; //****************************************************************************// //** Remplissage aléatoire du tableau **// //** (doit être remplacé par une importation des valeurs de travail réels) **// //****************************************************************************// procedure TMain.RempliTableau(); var x,y,k : integer; begin for x:=0 to NbCol-1 do for y:=0 to NbLig-1 do begin k:=random(NbNum)+1; sg.Cells[x,y]:=inttostr(k); end; end; //****************************************************************************// //** Initialisation du programme **// //****************************************************************************// procedure TMain.Initialisation(); var ev1 : integer; begin NbCol:=5; NbLig:=30; NbNum:=70; sg.ColCount:=NbCol; sg.RowCount:=NbLig; Randseed:=1; // Initialise le générateur de valeurs aléatoires (pour mise au point) RempliTableau(); ev1:=EvalueTableau(); lb1.Caption:='Evaluation = '+inttostr(ev1); end; //****************************************************************************// //** Est lancé à l'affichage initial de la fenêtre **// //****************************************************************************// procedure TMain.FormShow(Sender: TObject); begin Initialisation(); end; //****************************************************************************// //** Action lorsqu'on clique sur le bouton bt1 **// //****************************************************************************// procedure TMain.bt1Click(Sender: TObject); begin TriTableau(); end; end.
C'est ce que je comprend, mais ansset a raison qu'il reste des choses non explicites.
Effectivement
Autres questions: est-ce que c'est vraiment le nombre maximum d'éléments dans une colonne, ou le nombre maximum d'éléments consécutifs, ou le nombre total d'éléments consécutifs y compris dans plusieurs listes d'éléments (autrement dit: pourquoi la colonne 1 dans l'exemple fourni ressort-elle triée pour les 10?)
Wow pour l'effort, mais si je comprend bien ton code (vieux souvenirs le Pascal...) tu permutes uniquement des colonnes entières, alors qu'on peut en fait permuter des cellules à l'intérieurs des colonnes. En tout cas l'avantage de ton code c'est qu'il ne serait pas compliqué de changer la fonction EvalueTableau.
Je permute bien des cellules prises au hasard sur une ligne, deux à deux, entre deux colonnes.
(mais c'est vrai que le commentaire indiqué un peu vite est ambigue)
Tout à fait, par exemple il est possible de noter différemment pour choisir préférentiellement une configuration du tableau.
Par exemple, au lieu d'augmenter la "note" de 1 pour chaque nouveau nombre identique trouvé dans une colonne, on peut augmenter la note de 2 pour le deuxième trouvé, de 3 pour le troisième, de 4 pour le quatrième etc.
On peut aussi essayer un "recuit" au niveau de TriTableau(), en "désorganisant" le tableau de temps à autre au début du tri.Code:if k1=k2 then begin nb:=nb+1; if nb>1 then e:=e+nb; end;
J'ai fait quelques tests à ce niveau, mais ça n'améliore pas de beaucoup la "note". (j'ai réussi à l'améliorer de 2 points environ sur par exemple 82).
Dernière modification par LeMulet ; 20/11/2016 à 21h39.
Bonjour à tous,
Merci pour vos réponses (je ne connais pas ce langage de programmation..) je vous envoie l'image d'un exemple que j'ai fait (en rouge les 2 nombres "en erreur" dispersés) mais je n'arrive pas à faire mieux (avec seulement 15 lignes et des nombres allant uniquement à 50).
Bonne soirée.
Tu n'as pas précisé quel était le critère que tu voulais optimiser. Dans l'exemple que tu donnes si tu permutes 28 et 33 dans la première ligne, tu améliores le nombre de 28 dans la dernière colonne (il passe de 3 à 4) au détriment du nombre de 28 dans la deuxième colonne (il passe de 2 à 1). Qu'est-ce qui est mieux pour toi? C'est déjà un premier point à régler. Ensuite il faut voir comment tu veux prendre en compte les différents nombres, tu peux définir un critère "qualité moyenne" ou un critère de type "max min" par exemple.
+1, il faut vraiment que tu clarifies mieux la tâche.
Pour info, avec l'algorithme proposé (+"recuit") et avec les données du message #18, j'obtiens ça :
En relançant plusieurs fois le tri, le programme n'arrive pas à faire mieux.
Bonjour,
Quel est le nombre de "dispersés" avec ton programme "recuit"? l'idéal bien sûr serait de ne pas avoir de nombres en erreur rouges....impossible.
Alors entre:
1 nombre dispersé présent 10 fois(= 10 rouges)
et
10 nombres dispersés présent chacun une fois (=10 rouges)
je préfère la première solution.
merci à vous.
@Roger:
si je reprend tes tableaux du post #18.
On voit que tu as optimisé (en partie ) le nb de 33 ds la colonne 4. ( 5 chiffres )
Sauf que tu n'as pas été au bout sur ce point car une permutation sur la première et la dernière ligne aurait rajouté 2 chiffres 33 .
Par ailleurs une fois ceci fait , on pourrait continuer à "optimiser" cette colonne avec toutes les lignes ne contenant pas de 33 ( les 8 restantes )
il a 5 fois 41 dans ces lignes qu'on pourrait ramener dans la 4 ème colonne.
cette 4 ème colonne contiendrait au final 7 chiffres 33, 5 chiffres 41, 2 chiffres 49, et un seul chiffre unique.(*)
un algo peut tout à fait procéder de ctte manière en procédant par étape sur les chiffres les plus courant.
(*) mais je ne sais pas si cela correspond à ce que tu définis comme "meilleure" optimisation.
y'a quelque chose qui cloche là dedans, j'y retourne immédiatement !
Bonjour,
je ne comprends pas:
" une permutation sur la première et la dernière ligne aurait rajouté 2 chiffres 33 " tu voudrais permuter en ligne 1 le 33 et le 9 sauf que la 4ème colonne est la colonne où sont rangés tous les 9
et en dernière ligne le 33 avec le 10 (pour avoir les 33 en colonne 4) c'est la colonne où sont les 10 ? donc je ne peux permuter (conflits) ?
donc si je fais ce que tu dis, je range les 33 et je déclasse les 9 et les 10.
Dernière modification par Roger788 ; 22/11/2016 à 09h13.
ta reponse illustre bien que je ne comprend pas quels sont tes critères d'optimisation.
comment choisir entre moins de chiffres alignés plus souvent ( verticalement bien sur ) , ou plus de chiffres alignés moins souvent, ou encore les colonnes elles mêmes les plus optimisées......etc...
quelle est la "valeur" chiffrée que l'on peut donner à l'optimisation d'un tableau. (*)
que doit on multiplier et/ou ajouter ???
par exemple tu me dis qu'il est moins bien de rajouter deux 33 dans cette colonne parce qu'on enlèverait deux 9 alignés ailleurs !!!
Dernière modification par ansset ; 22/11/2016 à 09h28.
y'a quelque chose qui cloche là dedans, j'y retourne immédiatement !
à titre de comparaison,
ton arrangement donne pour la 4ème colonne:
- 5 chiffres 33
- 4 chiffres 10
- 3 chiffres 9
le mien donne pour cette colonne :
- 7 chiffres 33
- 5 chiffres 41
- 2 chiffres 49
quel principe de calcul te permet de décider que le tien est "meilleur" ???
d'autant que l'on peut continuer à réarranger les autres colonnes pour rassembler les 9 ailleurs par exemple.
a moins que le but ne soit de se concentrer que sur une seule colonne.
Dernière modification par ansset ; 22/11/2016 à 09h54.
y'a quelque chose qui cloche là dedans, j'y retourne immédiatement !
" d'autant que l'on peut continuer à réarranger les autres colonnes pour rassembler les 9 ailleurs par exemple" là je suis d'accord.
Ma préférence a été citée plus haut, je préfère un minimum de nombres dispersés différents (par ex: le 33 dispersés 10 fois que 10 nombres dispersés 1 fois) et si possible une ou deux colonnes sans dispersion serait un plus...
merci
que veux dire "dispersé" ??????
si c'est en fait rassemblés, alors mon arrangement est meilleur.
d'autant plus si on rassemble les 9 ailleurs.
sans formule pour évaluer la qualité d'un arrangement, on est dans le subjectif.
Dernière modification par ansset ; 22/11/2016 à 10h42.
y'a quelque chose qui cloche là dedans, j'y retourne immédiatement !
Tout dépend de la manière dont on défini la note.
Par exemple, le résultat fourni précédemment utilise cette méthode :
Ce qui favorise la quantité de nombres identiques par colonne au détriment d'un éventuel regroupement de plusieurs "types" de nombres identiques en quantité moindre.Code:if k1=k2 then begin nb:=nb+1; if nb>1 then e:=e+nb; end;
Pour favoriser la stratégie inverse, il suffit de changer cette partie de la notation.
Par exemple en faisant quelque-chose comme ça :
Code:if k1=k2 then begin nb:=nb+1; if nb>1 then e:=e+NbLig-nb+1; end;
Je vais être redondant avec ansset et LeMulet, mais encore une fois: non, ta préférence n'est pas claire. Il semble que tu souhaites d'abord minimiser "le nombre de dispersé" (mais on ne sait pas ce que c'est), mais aussi " si possible une ou deux colonnes sans dispersion serait un plus..." (ce qui peut se comprendre de bien des façons). Mais tu n'as toujours pas défini ce qu'est un "dispersé"...
Une compréhension naturelle serait "nombre dispersé: tout nombre qui est présent dans plus qu'une colonne".
Sauf que ça ne marche pas avec ton exemple en #18: si on permute le 9 et 33 dans la première ligne, puis le 10 et 33 dans la dernière ligne, alors on diminue le nombre de dispersé (trois 9 et trois 10 deviennent dispersés, mais sept 33 quittent cette catégorie). Donc soit ton exemple est mal optimisé, soit il est optimisé selon un autre critère qui reste à définir. Il faut que tu le définisses, de préférence en fournissant une formule ou un algorithme en pseudo-code permettant de la calculer.
Si tu n'arrives pas à fournir une formule, je te suggère de mettre une série d'exemples-jouets (des tableaux très petits, avec très peu de nombre différents, pour lesquels tu es certain que l'optimisation est faite).
