Kennt jemand einen Sitzplangenerator mit bestimmten Einstellungsmöglichkeiten?

Hallo, meine Lehrerin sucht einen Sitzplangenerator, um das Sitzplatzproblem endlich zu lösen.

Am Besten wäre ein Genator, wo man zu dem jeweilgen Schüler drei Personen eingeben könnte, neben dem man gerne sitzen würde und drei, neben denen man auf keinen Fall sitzen will.

Und wenn es geht, verschiedene Sitzreihen, etc. Einstellungen.

Und dann denkt das Programm und findet halt Lösungen.

Kennt ihr ein Programm, welches das kann?

Ich bin leider nicht so sehr im Programmierthema drinnen, um sowas selbst zu können.

Answer 1

[Ecaflip]

Das ist ein rein kombinatorisches Problem.

Eine Lösungsmöglichkeit ist also immer, alle Sitzordnungen, die es gibt, durchzuprobieren und bei jeder zu schauen, ob alle Wünsche erfüllt sind.

Besonders effizient kann man das bspw. mit einem Entscheidungsbaum oder ganzzahliger linearer Optimierung lösen. Denn wenn mich nicht alles täuscht, müsste das ein NP-vollständiges Problem sein.

Man muss natürlich im Kopf behalten, dass es auch manchmal keine Lösungen geben kann. Dann müsste man noch angeben, wie schlimm es wäre, nicht neben dem Wunschnachbarn zu sitzen, oder sogar jemanden neben sich zu haben, den man auf keinen Fall will.

Sehr gut vorstellen kann man sich das als Graphen, wo jeder ein Schüler ein Knoten ist und die Kanten die Sitznachbarn verbinden. Je nach Struktur des Klassenzimmers, sind dann auch die Grade der Knoten vorgegeben. So würde ich das auch programmieren. Kantengewichte für die Nachbarvorlieben könnten dann z.B. 1, 0, und -1 sein und man maximiert also als Ziel das Gewicht.

Woher ich das weiß: Berufserfahrung – Programmierer

Comments

[Ecaflip]

Alle durchprobieren geht bei einer Reihe so:

<script>
var students = ["Adam", "Bert", "Conrad", "David", "Emil"]
var likes = new Map()
var hates = new Map()

likes.set("Adam", ["Bert", "David"]) // Adam will neben Bert und David
likes.set("David", ["Conrad"]) // David will neben Conrad
hates.set("Emil", ["Bert"]) // Emil will nicht neben Bert

for(permutation of permute(students)){
	var valid = true
	for(student of students){
		var index = permutation.indexOf(student)
		var fulfilled = true
		if(likes.get(student)){
			for (preference of likes.get(student)){
				if((!permutation[index-1] || permutation[index-1] !== preference) && (!permutation[index+1] || permutation[index+1] !== preference)){
					fulfilled = false
				}
			}
		}
		if(hates.get(student)){
			for (aversion of hates.get(student)){
				if(permutation[index-1] === aversion || permutation[index+1] === aversion){
					fulfilled = false
				}
			}
		}
		if(!fulfilled)
			valid = false
	}
	if(valid)
		console.log(permutation)
}

function permute(permutation) {
  var length = permutation.length,
      result = [permutation.slice()],
      c = new Array(length).fill(0),
      i = 1, k, p;

  while (i < length) {
    if (c[i] < i) {
      k = i % 2 && c[i]
      p = permutation[i]
      permutation[i] = permutation[k]
      permutation[k] = p
      ++c[i]
      i = 1
      result.push(permutation.slice())
    } else {
      c[i] = 0
      ++i
    }
  }
  return result
}
</script>

Answer 2

[regex9]

Nein. Man kann zwar recht schnell einen Generator finden (siehe http://www.sitzplangenerator.de/), doch der bietet nicht die von dir beschriebenen Features, sondern findet lediglich (wenn man möchte) eine zufällige Verteilung.

Ich muss auch ehrlich sagen, dass ich es nicht für sinnvoll erachten würde, so ein Tool zu nutzen, wenn es denn ein solches gäbe.

1) Die Wünsche der Schüler stehen oft konträr zu denen des Lehrers. Das von dir erwähnte Problem ist doch sicherlich erst dadurch entstanden, dass ihr eine freie Wahl bei der Sitzverteilung hattet.

Im klassischen Fall sitzen die Problemfälle zusammen (seien es Klassenclowns, Labertaschen, Personen die sich gegenseitig herunterziehen, ...) und werden bei Nachfrage auch dazu tendieren, weiter zusammensitzen zu dürfen.

Die, die keine Probleme in de Sitzordnung verursachen, werden hingegen vermutlich eher dagegen sein, neben einen Problemfall gesetzt zu werden (und wenn nicht sie, dann zumindest ihre Helikoptereltern). Eine gute Lösung wertet die Schüler-/Elternwünsche besser nicht zu hoch (bzw. nur als Teilfaktor).

2) So ein Programm würde viele Eingaben und somit auch einigen Bedienungsaufwand benötigen. Geh nur einmal davon aus, du hast zwanzig Schüler in einer Klasse. Jeder gibt seine sechs Namen an, was bereits 120 Eingaben (in welcher Form auch immer) erfordert. Möglicherweise kommen dann je Person noch weitere Faktoren hinzu (Gewichtungen, u.ä.), denn ein Programm kann nur mathematisch denken.

3) Der niedrigste Aufwand dürfte darin liegen, lediglich die Problemfälle umzusetzen. Die Beurteilung, wer wohin muss, wird besser auf soziologischer Basis getroffen, nicht auf mathematischer.

Eure Lehrerin kennt euch doch und kann euch wenigstens etwas einschätzen (das ist ein wesentlicher Vorteil zum Computer). Wenn ihr das tatsächlich als zu schwierig erscheint, gibt es auch noch die klassischen Verteilmuster wie: Junge - Mädchen, Junge - Mädchen (bei dieser Beispielmethode muss man einfach schauen, ob das bei eurem Alter Sinn macht). Den Jahrespreis der herzlichsten Lehrkraft wird sie letzten Endes so und so nicht von jedem erhalten. Die Entscheidung an einen (Zufalls-)Generator übergeben zu wollen, macht es da auch nicht besser, zumal der nicht bewerten kann, ob er mit seinem Vorschlag nicht gerade neue Brandherde öffnet.