Gruppeneinteilung welche Sprache?

[Skn0tt]

Hallo liebe CBler,
ich organisiere dieses Jahr eine Projektwoche an unserer Schule. Die vorigen Jahre wurde die Projekteinteilung immer von Hand (Zettel umherschieben) durchgeführt.
Da ich mir die Arbeit mit dem Abtippen hinterher ersparen will (es sind immerhin 1000 Schüler), möchte ich die Einteilung dieses Jahr automatisieren.
Meine Frage: Welche Sprache eignet sich dafür am besten? Geht das vllt sogar mit Python (Das kann ich nämlich schon )? Die Anmeldungen liegen tabellarisch vor, berücksichtigt werden sollen 3 Projektwünsche, Altersgrenzen, sowie einige Projekte, in die nur bei Wunsch eingeteilt werden darf.
OS ist Win 10, für die Tabelle benutze ich LibreOffice.

Ich danke schonmal im Voraus,
Skn0tt

 

[HominiLupus]

Natürlich geht das auch in Python, aber wichtiger ist auf welche Art das Programm mit dem Nutzer interagiert.
Also ein Programm, bzw. für welche Plattform Windows, Android, etc. oder eine Website.
Eine Tabelle ist allerdings eine schlechte Art die Daten abzuspeichern. Dafür ist eine Datenbank da (SQLite z.B. einfach und unkompliziert, verfügbar für praktisch jede Programmiersprache, auch Python)

 

[Skn0tt]

Danke Hominilupus,
ich werde mich mal mit SQL auseinandersetzen. Hoffentlich führt das zum Erfolg

 

[kuddlmuddl]

Mal ganz unabhängig von der Programmiersprache:
Wie willst du damit umgehen, dass das Problem evtl nicht lösbar ist? Also das z.B. ein Projekt 50 Schüler wollen und ein anderes nur 4?
Klar, es gibt die 3 Projektwünsche aber auch dann wird dieses Problem bestehen.
Du brauchst einen Algorithmus der so fair wie möglich alle Schüler verteilt. Das kann schwierig werden!
Dh du brauchst erstmal irgendwie sowas nur noch komplizierter:
- Sortiere alle Schüler zufällig (damit jeder die selbe Chance hat)
- Erfülle so lange alle Erstwünsche, bis die jeweilige Gruppenobergröße erreicht ist
- Erfülle für die restlichen Schüler, die nicht ihren Erstwunsch bekommen haben ihren Zweitwunsch und wenn das schon nicht mehr geht dann wenigstens ihren Drittwunsch.
Hier hast du aber ein Problem: Es kann Schüler geben die nun nicht mehr eingeteilt werden können, weil alle 3 Wunschgruppen schon voll sind.
Ob das Problem auftaucht hängt natürlich von der zufälligen Sortierung ab, von den Wahlen und von den Gruppengrößen.

Außerdem solltest du vorher erstmal deine Daten prüfen: Hat jeder wirklich genau 3 unterschiedliche(!) Gruppen genannt?
Was, wenn einer nur einen einzigen Wunsch geäußert hat - bekommt er dann automatisch seinen Erstwunsch? Das wäre unfair gegenüber anderen, die noch Alternativwünsche angegeben haben. So läufts aber an einigen Unis ;-)
Was, wenn einer mehrmals die selbe Gruppe genannt hat?
Wie gehst du damit um, wenn zB alle Jungs Fußball, Basketball und Handball wählen? Die drei Gruppen sind wahrscheinlich nicht groß genug alle aufzunehmen, egal in welcher Reihenfolge du die Schüler sortierst und egal in welcher Reihenfolge sie genannt wurden.

Python finde ich übrigens sehr gut für so etwas - vor allem wenn die Daten bereits digital in einer Tabelle vorliegen.

 

[Ichthys]

Du kannst das prinzipiell mit jeder Programmiersprache lösen. Du wirst dich allerdings meiner Meinung nach mit Rekursion und Backtracking beschäftigen müssen. Beides ist nicht ganz so trivial, wenn man eher wenig Erfahrung hat. 55
kuddlmuddl hat deine Problematik schon gut zusammengefasst.
Ich vermute mal, dass Du mit Excel vermutlich genauso, wenn nicht, sogar noch schneller ans Ziel kommen wirst.
Andererseits kann man das Ganze natürlich auch weiterverwenden.
Aber gefühlt würde ich Dir raten, jemanden zu suchen, der schon mit der Materie Erfahrung hat.

 

[Grantig]

Ihr macht das Problem komplizierter als es ist.
Imho brauchts kein Backtracking, keinen komplizierten Algorithmus und auch keine Datenbank.

Wenn die Anmeldungen eh schon als Libre Office Tabelle vorliegen, dann liegt es doch nahe sie einfach als .csv zu exportieren.
Vorteil: kann einfach von nem Python Script verarbeitet werden, ist menschenlesbar und leicht verständlich.

Dann macht man folgendes:

1. eine zufällige Liste aller Schüler (+ Gruppenwünsche) erzeugen
2. Liste durch laufen und den 1. Wunsch prüfen. Ist noch Platz in der Gruppe wird der Schüler dieser zugeordnet und aus der Liste entfernt. Ist kein Platz mehr wird er erstmal ignoriert.
3. Schritt 2 für alle weiteren Wünsche wiederholen
4. alle Schüler die übrig bleiben nachdem alle Wünsche betrachtet wurden werden zufällig auf die noch freien Plätze verteilt
5. die Zuordnungen nach dem Schema Nachname;Vorname;Gruppe als .csv speichern

Das Ergenbis .csv kann dann in Libre Office geöffnet und weiter verarbeitet werden.

Auf diese Weise werden nicht genutzte Wünsche (z.B. nur 1. Wunsch angegeben oder 3 mal die selbe Gruppe angegeben) als "mir egal" interpretiert und der Schüler wird irgendwo reingeworfen (ist schliesslich sein Pech wenn er nicht alle seine Möglichkeiten ausnutzt Wünsche anzugeben).
Schüler die 3 sehr beliebte Gruppen angeben müssen halt damit rechnen, dass sie Pech haben - man kanns nicht Allen Recht machen.


Backtracking wäre nur nötig wenn die Schüler noch Freunde angeben könnten mit denen sie gerne in einer Gruppe wären.
Ne Datenbank wäre imho erst dann sinnvoll, wenn die Wünsche der Schüler auch elektronisch abgegeben werden (z.B. über ne kleine Website).
Für so ne kleine Aufgabe halte ich selbst SQLite für overkill, vor allem wenn der TE noch keine Ahnung von Datenbanken hat.

 

[Kanibal]

Das ist ein klassisches Optimierungsproblem. Du stellst eine Kostenfunktion pro Schüler in Anhängigkeit der Zuteilung auf (Beispielsweise quadratische Kosten - wenn jemand 2 Drittwünsche bekommt, kostet das 9 [Einheiten]) und versuchst dann, diese über die Menge der Wünsche zu minimieren.
Stichwort dazu: Ungarische Methode.

 

[titanskin]

MaxMatching, PerfectMatching.

Entscheide dich für ein Problem.

Der Ansatz von Grantig habe ich dahingehend schon mal gesehen. Es ist glaube ich der Standartansatz für so etwas.

Die Lösung von Kanibal führt auch zu einer Lösung.

Eine dritte wäre das Matching durch einen Graph auszudrücken und mithilfe vom MinCostFlow zu lösen.

Source -> Schüler -(Projektwünsche)-> Projekte -(Capa)-> Sink.

Kanten Projektwünsche: (capacity=1, weight=3-projektreverenz),
Kanten Capa: Projektkapazität; Kosten 0.

Suche minimale Kosten zum Flusswert F=#Anzahl Schüler. Fluss ist korrekt, wenn er ganzzahlig ist.

Algorithmen gibt's auf google-code. Oder lass es in Excel lösen. (Stichwort: LP)

 

[kuddlmuddl]

Ihr macht das Problem komplizierter als es ist.
Imho brauchts kein Backtracking, keinen komplizierten Algorithmus und auch keine Datenbank.

Der Ansatz von Grantig habe ich dahingehend schon mal gesehen. Es ist glaube ich der Standartansatz für so etwas.

Ist dein (Grantigs) Verfahren nicht exakt das selbe was ich oben schon beschrieben habe? Komplizierter ist meins auch nicht. Ich hab nur auf einige Probleme hingewiesen, die entstehen.. hier haben nämlich sehr viele Schüler einfach 'Pech'.

Die Problematik dieses Ansatzes ist, dass man sehr gute Lösungen übersehen kann. Es ist zB je nach Wahl möglich, allen SchülerInnen ihren 2t Wunsch zu erfüllen aber sobald man einigen ihren Erstwunsch wahr macht werden weitere erfüllte zweit oder drittwünsche unmöglich.
Da stellt sich dann die Frage ob es gut verteilt ist, wenn zwar einige ihren ersten Wunsch bekommen aber anderen garnix.
Ist es wirklich besser, wenn zB bei gleicher Wahl:
20% ihren Erstwunsch, 5% ihren Zweitwunsch und 10% ihren Drittwunsch bekommen
als wenn
10% ihren Erstwunsch bekommen, 45% ihren Zweitwunsch und 35% ihren Drittwunsch?

Grantigs und mein Ansatz wählt die erste Verteilung denn er maximiert die Zahl der erfüllten Erstwünsche ohne dabei den Verlust (Kosten) der erfüllten Zweit- und Drittwünsche zu beachten. Allerdings erhalten nur 35% überhaupt einen Wunsch erfüllt während bei der zweiten Lösung sogar 90% immerhin irgendeinen Wunsch erfüllt bekommen. Diese Lösung ignoriert das Verfahren aber.

 

[Grantig]

@kuddlmuddl
Du hast Recht die Ansätze sind die gleichen.

Ich wollte einfach zeigen, dass es ne wirklich einfache (und trotzdem gute) Lösung für das Problem gibt, weil das Ganze in diesem Thread imho komplizierter dargestellt wurde als es eingentlich ist.

Etwas konkreter: dieser Satz hat mich z.B. gestört (versteh das bitte nicht als Angriff):

du brauchst erstmal irgendwie sowas nur noch komplizierter

Deswegen dacht ich mir ich schreib auf wie das "irgendwie sowas" konkret aussehen sollte und dass es nicht unbedingt "noch komplizierter" sein muss
(und vor allem dass man keine DB und kein Backtracking braucht, was ja hier im Thread auch noch genannt wurde)


Zur Problematik dieses Ansatzes hast du ja schon alles gesagt und dem stimme ich zu.
Ich bin davon ausgegangen, dass die Priorität der Wünsche wichtiger ist, als die Gesamtzahl der erfüllten Wünsche weil ich persönlich bei solchen Verfahren alles ausser meinen 1. Wunsch als Notlösung erachte.

Wäre interessant zu wissen welcher Ansatz besser für die allgemeine Zufriedenheit der Schüler ist.

Da könnte Skn0tt ja evtl. beide Ansätze ausprobieren und den Schülern auch beide Lösungen/Gruppeneinteilungen präsentieren und sie einfach abstimmen lassen was besser ist (wäre wirklich interessant)

Die Anzahl aller erfüllten Wünsche zu maximieren dürfte auch mit dem Excel/LO Calc Solver recht einfach umsetzbar sein (also könnte man auf das Python Script verzichten).

 

[Mangoone]

Hi @skn0tt und @all

Hast du/ habt ihr bereits eine Lösung für das Zuteilungsproblem gefunden? Ich stehe demnächst vor einer ähnlichen Aufgabe allerdings mit weniger Variablen, denn ich habe nur die Zuteilung von 1.-4. Wunsch und würde dabei ggf noch gerne berücksichtigen, dass eher ein Zweitwunsch erfüllt wird als ein Drittwunsch (wenn also beispielsweise bei einer Person weder erst noch Zweitwunsch erfüllt werden kann, dann soll gecheckt werden, ob bei einer anderen Person in einer der Gruppen ein Zweitwunsch erfüllt werden kann usw) um die Zufriedenheit zu maximieren....
Ich würde mich darüber freuen wenn bereits vorhandene Ergebnisse oder Erfahrungen geteilt würden ☺️

Ergänzung (2. September 2016)

Bzw falls du wirklich beides implementiert hast weißt du ja vielleicht womit deine Schüler zufriedener waren...?
Ich habe ziemlich wenig programmiererfahrung (Java, Prolog, c#) und freue mich auch über Hinweise bzgl der Vorgehensweise

 

[Skn0tt]

Also generell lässt sich sagen: Die Schüler sind nie zufrieden xD
Egal wie du einteilst, es werden Beschwerden kommen.
Ich habe im Endeffekt das ganze von Hand gelöst:
Datensätze mit Name, Klasse und den Wünschen einfach zwischen Tabellenseiten hin und her schieben.
Ein Skript wäre vermutlich genausoviel Aufwand gewesen, nur hatte ich nicht wirklich Bock mir die nötigen Skripte zu schreiben.
Mein Tipp: Wenn es abzusehen ist, dass du öfters sowas organisierst, schreib dir ein Skript. Wenn das eine einmalige Sache ist, mach ne Tabelle. Bei uns wird die Projektwoche von Schülern organisiert, meistens jedes Jahr ein anderer. Ich weiß nicht wie das bei euch ist, vielleicht kannst du ja auch einen Informatikkurs mal bitten, so ein Skript zu schreiben (passt gut in den Lehrplan der EF)

LG,
Skn0tt

 

[nullPtr]

Nur nochmal um im allgemeinen Hinweisgetummel für noch mehr Verwirrung zu sorgen: Deterministische Algorithmen für sowas sind nicht unbedingt das Optimum. Für Zuweisung von Personen zu irgendwas wobei eine Präferenzrelation gegeben ist, zählen auch Dinge wie Fairness und Neidfreiheit. Random Assignment ist hier das passende Stichwort.