kontrollierte Zufallsgenerierung

[A.Malethan]

Hallo.
Ich habe eine Aufgabe, an der ich schon einige Zeit herumgrübel und nicht weiter komme.
Vielleicht finde ich hier jemanden, der mir eine Richtung zeigen kann.

Die Aufgabe:
27 Personen sollen an 20 Tagen in zwei Gruppen aufgeteilt werden, deren Mitglieder von Tag zu Tag wechseln sollen.
Jedes Gruppenmitglied soll an 10 Tagen der Gruppe 1 und an 10 Tagen der Gruppe 2 zugehören.
An jedem Tag darf die Gruppenstärke von Gruppe 1 die Mitgliederzahl von 13 nicht unterschreiten und/oder von 14 nicht übersteigen.

Das gewünschte Ergebnis ist in etwa so:
name1 1 0 1 1 0 0 ... 0 1 1 0  |maximal 10x0, 10x1
name2 1 1 1 0 0 1 ... 0 0 0 1  | -"-
name3 0 1 0 0 1 0 ... 0 1 1 1
.. . . . . . . ... . . . .
.. . . . . . . . . . .
.. . . . . . . . . . .
name27 0 0 0 1 1 1 ... 0 0 1 1
________________________________________
 1Tag|2Tag|..
 13x0|14x0|..
 14x1|13x1|..

Ich bin in der Lage, Zeile für Zeile per Zufallsfunktion zu ermitteln.
Doch in der senkrechten Anforderung der Aufgabe - täglich zwei Gruppen von 13 bzw. 14 Mitgliedern, deren Mitglieder in 20 Tagen gleichmäßig der Gruppe 1 und/oder 2 angehören -  fehlt mir die Idee.

Für jede Anregung bin ich dankbar.

MFG
A.Malethan

[Sven Rautenberg]

Moin!

Die Aufgabe:
27 Personen sollen an 20 Tagen in zwei Gruppen aufgeteilt werden, deren Mitglieder von Tag zu Tag wechseln sollen.
Jedes Gruppenmitglied soll an 10 Tagen der Gruppe 1 und an 10 Tagen der Gruppe 2 zugehören.
An jedem Tag darf die Gruppenstärke von Gruppe 1 die Mitgliederzahl von 13 nicht unterschreiten und/oder von 14 nicht übersteigen.

Klingt als (langweilige) Ausgangslage beispielsweise nach so einem Bitfeld:

1111111111 0000000000
 1111111111 0000000000
 1111111111 0000000000
 1111111111 0000000000
 1111111111 0000000000
 0000000000 1111111111
 0000000000 1111111111
 0000000000 1111111111
 0000000000 1111111111
 0000000000 1111111111
 0000000000 1111111111

(stell' dir entsprechend 27 Zeilen vor, die Hälfte wie im oberen Bereich, die andere Hälfte wie unten.)

Dieses Bitfeld erfüllt zwei deiner Bedingungen:
1. Jeder ist an 10 Tagen in Gruppe 1 und an den anderen 10 Tagen in Gruppe 2.
2. Jede Gruppe ist minimal 13 und maximal 14 Personen stark (dargestellt: minimum 5 Personen, Maximum 6 Personen).

Fehlt nur noch "unterschiedliche Zusammensetzung jeden Tag". Da würde ich im Zweifel einfach die 1-Bits mit 0-Bits vertauschen und gucken, was dann passiert. Ich vermute, ein Tausch in diesem Feld führt dazu, dass zur Erreichung der zwei oben genannten Bedingungen ein Gegentausch durchgeführt werden muß. Tauscht man beispielsweise eine 1 von unten rechts nach unten links, wird im oberen Feldbereich in der gleichen Spalte von links nach rechts getauscht werden. Im Prinzip wird also immer ein positionsmäßiger Vierertausch durchgeführt - und das eben so lange, bis das Feld hinreichend ungeordnet ist.

Du hast nicht geschrieben, dass die Teilnehmer an jedem Tag mit einer unterschiedlichen Gruppenzusammensetzung zusammensein sollen, Dopplungen wären also theoretisch möglich. Das wäre aber wiederum ein Ansatzpunkt für Vertauschungen, denn eine Zeile, die doppelt vorkommt, erfordert eben für eine der zwei Zeilen noch einen weiteren Umtausch.

So im Sinne von "Solange Zeilen doppelt sind, tausche einmal vier Bitplätze und prüfe erneut".

Für jede Anregung bin ich dankbar.

Wer stellt denn solche Aufgaben?

- Sven Rautenberg

[Cruz]

Hallo Malethan,

also ich finde die Aufgabe sehr interessant und würde auch gerne einen halben Tag damit verbringen sie durch und durch zu ergründen und alle möglichen Lösungen zu ermitteln. Leider muss ich aber arbeiten, daher kann ich eher nur einen quick and dirty Beitrag leisten.

Also verfolgen wir doch weiter deinen Ansatz, denn du hast ja schon ein verwendbares Zwischenergebnis erzielt:

Das gewünschte Ergebnis ist in etwa so:
name1 1 0 1 1 0 0 ... 0 1 1 0  |maximal 10x0, 10x1
name2 1 1 1 0 0 1 ... 0 0 0 1  | -"-
name3 0 1 0 0 1 0 ... 0 1 1 1
.. . . . . . . ... . . . .
.. . . . . . . . . . .
.. . . . . . . . . . .
name27 0 0 0 1 1 1 ... 0 0 1 1
________________________________________
1Tag|2Tag|..
13x0|14x0|..
14x1|13x1|..

Ich bin in der Lage, Zeile für Zeile per Zufallsfunktion zu ermitteln.

Du hast also eine 20x27 Matrix aufgestellt, dessen Zeilen du zufällig generierst, sodass die Zeilensumme immer genau 10 ist. Die Zeilensumme ist hier einfach die Anzahl der einsen. Sollten identische Zeilen auftreten, dann würde das bedeuten, dass 2 Personen die selbe Gruppeneinteilung für die 20 Tage haben und da spricht laut deiner Aufgabenstellung nichts dagegen oder? Hauptsache die gesamte Gruppenzusammensetzung ist nie die selbe.

Doch in der senkrechten Anforderung der Aufgabe - täglich zwei Gruppen von 13 bzw. 14 Mitgliedern, deren Mitglieder in 20 Tagen gleichmäßig der Gruppe 1 und/oder 2 angehören -  fehlt mir die Idee.

Dann rechne doc einfach die Spaltensummen aus. Sie dürfen genau 13 oder 14 sein. Wenn du einmal eine falsche Spaltensumme erhältst, dann fang einfach nochmal von Vorne an. Irgendwann wird das Programm schon eine gültige Lösung ausgeben.

Das ist natürlich keine so tolle Lösung, dein Rechner wird ganz schon lange zu tun haben und theoretisch könnte das Programm eine unendliche Laufzeit haben. Um sicher zu gehen, dass das Programm überhaupt eine Chance hat irgendwann mal anzuhalten, sollte man beweisen, dass es überhaupt eine Lösung gibt. Das kann man z.B. machen, indem man per Hand mit Stift und Papier schnell mal eine Lösung ausgrübelt.

Dann kannst du das Programm schon mal laufen lassen und mal sehen wer zuerst fertig ist, das Programm oder du mit einer besseren Lösung. :)

Die Optimale Vorgehensweise wäre aber so:

• Finde zuerst alle möglichen Variationen, wie du 27 Personen in zwei Gruppen der Stärke 13 und 14 verteilen kannst. Das sind z.B. alle 27 Bit lange Zahlen, die genau 13 oder 14 Bits auf 1 gesetzt haben.

• Aus all den Variationen bilde alle möglichen Mengen der Mächtigkeit  20, die die Bedingung erfüllen, dass jedes Bit genau 10 mal 1 und genau 10 mal 0 ist. (das ist wohl die Schwierigste Aufgabe)

• Wähle aus den berechneten Menge zufällig eine aus, diese ist dann deine gesuchte Lösung.

Lass es mich wissen wie es gelaufen ist, ich bin sehr gespannt.

Viele Grüße,
Cruz

Für jede Anregung bin ich dankbar.

MFG
A.Malethan

[A.Malethan]

Hallo Cruz, Hallo Sven Rautenberg,

vorweg vielen Dank für die Mühe die ihr euch mit meiner Frage gemacht habt.

Ich bin auf meine Lösung durch diesen Tipp von Cruz gekommen:

Dann kannst du das Programm schon mal laufen lassen und mal sehen wer zuerst fertig ist, das Programm oder du mit einer besseren Lösung. :)

Ich habe natürlich kein Programm jedoch nur ca. 10 Minuten Zeit gebraucht um zu überprüfen ob es überhaupt eine Lösung geben kann.
Die nun vorliegenden Variationen der Gruppenzusammenstellungen reichen für meinen Zweck vollkommen aus, sodass ich nunmehr die Namen per Zufall mische und vor die Zeilen setze, die Zeilen  in ein Array packe und dieses dann den Namen nach sortiere, formatiere und ausdrucke.
Fertig! :)

Auf diese Frage möchte ich noch antworten:

Wer stellt denn solche Aufgaben?

Die Gerechtigkeit.
Ich spiele und gehe essen   oder   Ich esse und räume auf.
Genauso oft wie meine Kolleginnen auch.

Noch einmal Danke und einen netten Abend noch.
Andreas Malethan