Salut les filles,

Ma gonzesse m'a demandé de lui pondre un algo, mais j'avoue que je sèche un peu (c'est pour son école, donc si j'ai pas de réponses, ils feront ça à la mimine comme depuis la nuit des temps).

On a ces variables :

- Niveau X (cp, ce1 etc) qui contient n élèves ( par exemple il y a 41 CP, 34 CE1 etc etc )
(j'avais matérialisé ça sous la forme d'un tableau d'objets)

-  nb d'élèves max par classe
- nb d'élèves max par classe si deux niveaux dans la meme classe ( 2 niveaux MAX par classe )
- nb de classes max

L'idée c'est que l'algo génère n classes ( 9 en fait ) avec max 2 niveaux différents par classe et avec le moins de classes à 2 niveaux possibles.

J'ai regardé du coté des algos génétiques, sac à dos etc, mais je vois plus droit là

Si quelqu'un a déjà pondu un algo ou a les compétences pour me sortir un truc de derrière les fagots ( je comptais lui faire ça en JS pour qu'elle ait une petite page html facilement transportable )

J'avais fais la base quoi

Merci

Comme c'est pas pour mon boulot et que c'est pour rendre service à ma gonzesse, si quelqu'un me file une solution qui va bien, j'lui enverrai un ptit truc pour le remercier (un ptit saucisson du terroir, une barrette de RAM hors d'age ou que je ne sais-je encore )

C'est quoi le soucis avec les métaH ? t'aime pas ?  
 
La solution rapide, faut voir pour un algo glouton ou tu vas tester toutes les solutions jusqu'à trouver une solution acceptable (remplir les classes, puis s'il reste des élèves faire une classe double etc...).
 
La solution plus propose serait une méta-heuristique.
 
La solution exacte, c'est moyen dans le cas présent.

C'est surtout que je suis rincé par ma journée de boulot et je ne me sens pas d'attaque pour lui trouver une solution.
 
Sachant qu'il faut le moins de classes de doubles niveaux ( c'est l'objectif ) mais j'imagine malgré tout qu'il vaut mieux 4 classes de doubles niveaux équilibrées que 3 dont une pourrait avoir 90% de CP et 10% de CE1.
 
Je regarde quand même en parallèle.

A mon avis, un bête algo LPT suffit. On prend le premier niveau (CP, donc), et qui mets x élèves de CP dans la première classe et la remplit jusqu'à atteindre le nb max d'élèves.  
Si la classe n'est pas remplie car nb d'élèves CP < nb élèves max, alors, il retire le nb d'élèves CP en trop pour atteindre le nb max d'élèves quand il y a 2 niveaux et ajoute des élèves de CE1.
Sinon, il passe à la classe suivante et la remplit avec les élèves de CP restants et complète avec des CE1 et ainsi de suite.
 
Un algo génétique qui calcule le score de la solution en fonction du respect des critères d'acceptation (ie respect des contraintes) fera l'affaire aussi.
 
Dans mon outil cantine (cf signature), j'ai codé un algo un peu semblable pour définir le planning des tours de goûters des familles qui tenait compte du nb d'enfants d'une même famille dans la même classe mais qui interdisait que la famille soit de goûter dans 2 classes en même temps ou 2 fois de suite dans des classes différentes.
Bref, j'ai fait un algo random : il génère une solution possible et vérifie le respect des contraintes. Si OK, c'est terminé, sinon, ça génère une nouvelle solution et vérifie... ainsi de suite jusqu'à en trouver une. J'ai mis un critère d'arrêt du nb de tests au cas où il n'existerait pas de solution.

Je vais essayer de jeter un coup d'oeil là-dessus si j'ai un peu de temps ce soir, merci

Euh je balance ça comme ça (sans partir sur un schéma connu et en ayant réfléchi au problème que quelques secondes), comme bien souvent, mais là (dans ma lecture du problème) tu n'as qu'une seule chose qui peut varier c'est le nombre de classes double-niveau et quels niveaux sont concernés.
Tu as un nombre d'élèves fixé, un nombre de classes fixé et un nombre d'élèves max par classe fixé.
 
Dans ce cas là tu calcules simplement le nombre de classes nécessaire par niveau en fonction du nombre max d'élèves par classe, si le nombre de classe est trop important alors tu prends le niveau avec la moyenne d'élèves par classe la plus basse et tu le mixes avec le niveau ayant la moyenne d'élèves par classe la plus haute. Suffit de calculer la moyenne sur le nombre de classes de chacun des niveaux choisis moins une. Si ça ne suffit pas, tu continues en reprenant le niveau avec la nouvelle moyenne la plus forte et celui avec la nouvelle la plus faible.
 
De toute façon tu ne peux te retrouver normalement qu'avec au maximum X-1 classes de double-niveaux où X est le nombre de niveaux.
 
La solution que je propose est simple, mais à moins que quelque chose m'échappe je ne vois pas ce qui fonctionnerait mieux avec les critères exposés. J'ai vraiment l'impression que quelque chose m'échappe mais je ne vois absolument pas où...

Ce qu'il faut faire au départ, et que je n'ai pas encore vu d'établi, c'est d'écrire complètement l'ensemble des contraintes du problème.
 
Par exemple je n'ai rien vu en ce qui concerne
- le nb minimal d'élève par classe en cas de dédoublement d'un niveau. je suppose que tu veux pas répartir 27 élèves en 25 d'un côté et 2 de l'autre
- en cas de classe double niveau, ceux-ci doivent ils être consécutifs (bref tu mets des CP avec des CM dans une même classe ou pas?).
 
Plus il y aura de contraintes, plus la solution sera rapide (par élimination directe des cas ne pouvant répondre a une contrainte).
 
A+,

Je n'ai pas ces contraintes (je les demanderai à ma gonzesse dans le week-end), sauf celle du contenu des doubles niveaux qui peut-être à priori non consécutifs (CP avec CM2).
 
J'essaierai de glaner plus d'infos ce soir.