Frage von Goleb04, 69

Gibt es ein Computerprogramm oder hat einer eine Programmieridee zur Verteilung von Schülern auf Schulklassen gemäß Wunschlisten von bis zu 5 Schülern?

Wenn es möglich wäre hätten ich gerne gerne den Quellcode eurer Programme.

PS: Meine Lehrerin hat mich gebeten so ein Programm zu programmieren.

Hilfreichste Antwort - ausgezeichnet vom Fragesteller
von ceevee, 39

PS: Meine Lehrerin hat mich gebeten so ein Programm zu programmieren.

Deine Lehrerin hat mich aber nicht gebeten, so ein Programm zu programmieren. Deswegen brauchst du meinen Quellcode (den ich eh nicht habe) nicht. ;)

Ich würde bei der Auswertung schauen, wieviele Schüler es gibt, bei denen A mit B und B mit A in einer Klasse sein will. Dann würde ich auf diese Weise versuchen, Gruppen zu bilden, die auf alle Fälle in einer Klasse sein wollen. Diese Gruppen kann man vielleicht schon von Hand analysieren und die Klassenaufteilung vornehmen. Dabei kann es vorkommen, dass Gruppen (an einer zufälligen Stelle) aufgeteilt werden müssen und dass die Klassen dann mit Schülern vollgestopft werden müssen, bei denen A mit B, aber nicht B mit A in einer Klasse sein will.

Eine Alternative (die vielleicht sogar programmiertechnisch einfacher umzusetzen ist), wäre es, jedesmal zufällige Klassen zu bilden und danach bei diesen zufälligen Klassen zu analysieren, wie gut die Wunschzettel erfüllt werden. Die Zusammenstellung, bei der die Wunschzettel am besten erfüllt sind, wird dann genommen. Das Programm muss dann halt nur lange genug laufen, um eine gute Lösung zu finden. Das Ganze nennt sich "Monte-Carlo-Algorithmus". https://de.wikipedia.org/wiki/Monte-Carlo-Algorithmus

Wie auch immer, das zu programmieren, ist etwas aufwändiger, deswegen glaube ich nicht, dass jemand deine Arbeit macht und dir den Quelltext hier reinstellt. Also: schmeiß deine Programmierumgebung an und los geht's, selbst ist der Mann! :)

Kommentar von procoder42 ,

ch würde bei der Auswertung schauen, wieviele Schüler es gibt, bei denen A mit B und B mit A in einer Klasse sein will

Das ist total irrelevant. Es gibt keine Spezifikation, dass die Klassenwahl die best mögliche sein soll. Theoretisch könnte man alle 20 Schüler nen Cut machen und so eine Klasse abschließen.

Da das Problem sehr offen gestellt ist, könnte man sich auch überlegen, aus den Schülern einen Graphen erstellen und die Wahl durch eine Adjazenzmatrix repräsentieren. Um dann die bestmöglichen Klassen zusammen zu stellen, würde man CLIQUE anwenden (Und so Gruppen heraussuchen, in denen sich alle Schüler gegenseitig mögen, was ja eine gute Voraussetzung für eine Klasse ist. Damit hat man sich dann ein NP vollständiges Problem geschaffen, welches der Fragensteller mit seinem umfangreichen Wissen selbstverständlich in polynomialer Zeit lösen kann ;).

Kommentar von ceevee ,

Damit hat man sich dann ein NP vollständiges Problem geschaffen, welches der Fragensteller mit seinem umfangreichen Wissen selbstverständlich in polynomialer Zeit lösen kann ;).

Ich glaub, die "04" am Ende des Nutzernamens ist sein Geburtsjahr. ;)

Den CLIQUE-Algorithmus habe ich mal überflogen, damit könnte man das wohl machen. Allerdings läuft man auch dann wohl ziemlich schnell in das Ruchsackproblem, wenn es darum geht, die Gruppen in Klassen einzuteilen. Die Aufgabe ist nicht ganz ohne, wenn man versucht, es systematisch zu lösen. Monte-Carlo ist ja eher "rumprobieren". ;)

Kommentar von procoder42 ,

Ich glaub, die "04" am Ende des Nutzernamens ist sein Geburtsjahr. ;)

So was in der Art hab ich mir auch gedacht, aber da der Nutzer sich in der Nachfolge von Bill Gates zu sehen scheint, wollte ich etwas trollen ^^.

Den CLIQUE-Algorithmus habe ich mal überflogen, damit könnte man das wohl machen

CLIQUE ist eigentlich mehr eine Problemstellung (Wie viele Knoten sind maximal miteinander verbunden ?) -die Problemvormulierung führt im angegebenen Problemfall sogar zu recht guten Ausgabe Werten- und zwar eine NP Vollständige.

Allerdings läuft man auch dann wohl ziemlich schnell in das
Ruchsackproblem, wenn es darum geht, die Gruppen in Klassen einzuteilen.

Könnte daran liegen, dass beide Probleme in der selben Komplexitätsklasse liegen (Wie gesagt, mein Vorschlag ist an sich sogar recht gut, aber eher als Troll-Algorithmus gemeint). Das Problem wird sich nicht unter 2^n Schritten lösen lassen.

Bei 200 Schülern wären das 1,6 * 10^60 Schritte.

Monte-Carlo ist ja eher "rumprobieren". ;)

Läuft aufs selbe hinaus. Der best Case ist halt besser, der worst Case mehr oder weniger gleich (Obwohl es natürlich mehrere optimale Lösungen für die Klassenaufteilung gibt).

Auch eine gute Lösung wäre :

- Einen Schüler zufällig auswählen (oder für jede Klasse einen).

- Die Wünsche erfüllen

- rekursiv für die anderen Schüler weiter machen

Es wär aber echt mal interessant zu wissen, ob es dafür einen gescheiten Algorithmus gibt. Wenn man einzelne Gruppen im Graph bilden kann, könnte man diese dann nach dem Heiratssatz zu Klassen zusammenfügen.

An sich sollte das Problem aber ein Entscheidungsproblem sein.

Antwort
von beroud, 46

leider ist meine kristallkugel zum hellsehen gerade beim polieren

vb, vba, vbscript, delphi, perl, java, javaScript...?

und für das programm sind mehr vorgaben nötig

wie groß sollen die klassen werden? wieviele klassen soll es geben? und was von beiden hat priorität? und bei krummer schülerzahl, soll es dann z.b. drei klassen mit 30 schülern und eine mit 10 schülern geben oder sollen es dann vier klassen mit 25 schülern werden...? oder ergeben sich zahl und größe der klassen allein aus den wunschlisten?

wie genau sollen die wunschlisten berücksichtigt werden? müssen immer alle wünsche umgesetzt sein? oder soviel wie möglich? und in absoluten werten oder anteilig? soll also einer mit vier wünschen und einer mit zwei wünschen am besten jeder zwei wünsche erfüllt kriegen oder lieber jeder 50%, also einer zwei und der andere nur einen wunsch?

gibt es nur positive wünsche oder auch negative, also ausschlusswünsche (mit dem auf keinen fall)?

wenn ich die antworten habe kriegst du auch kot

Kommentar von Goleb04 ,

Java oder Java Script die Klassen sollen da 23-30 Kinder haben und es sind 4-5 Klassen.Es sollen so viele Wünsche wie möglich berücksichtigt werden und ungefähr gleich viele Mädchen und Jungen in einer Klasse sein(Das hat aber erst mal keinen Vorrang)

PS: So ein Programm hat Bill Gates in seiner Kindheit geschrieben nur mit einem Hiddensee Feature dass ihn mit vielen Mädchen in. Eine Klasse geschickt hat( So etwas wollen wir nicht😁😅)
Es gibt keine negativen (Ausschluss) wünsche
Danke für die schnelle Antwort!!!

Antwort
von jxnass, 45

Mach es doch auf die altmodische Idee? Warum kompliziert. Mal dir ein Baumdiagramm...

Kommentar von Goleb04 ,

Ich kann nicht malen!!!😩😩😩😩😎😎😎😎😎😀

Keine passende Antwort gefunden?

Fragen Sie die Community