Erbitte kleines Programm zu programmieren

#1
Hallo allerseits,

in nächster Zeit werden wir bei mir in der Ausbildung von insgesamt 16 Leute auf 2 Gruppen mit a 8 Leuten per Zufall (durch eine Führungsinstanz) aufgeteilt.
Jetzt haben wir als Azubis uns hingegen gedacht, dass wir das eventuell selber machen können, sodass möglichst alle weitestgehend zufrieden sind (prozentual gesehen). Sprich: Wir würden die Chance anheben, dass jeder mit Kollegen zusammen arbeitet, mit denen er/sie auch wirklich zusammen arbeiten will.

Bis jetzt hat jeder 7 Namen abgegeben, mit welchen er gerne in einer Gruppe wäre; plus der eigene Name macht ja 8.
Nun meine Frage:
Könnte bitte jemand ein Programm schreiben, bei welchem man von jeder Person die 7 Wunsch-Personen eintippt und dieses dann ein Ergebnis (oder vllt sogar mehrere) ausspuckt, bei welchem eben die errechnete Verteilung der Leute am besten ist -und nicht nach dem Handeln eines "Fremden"-?
Versteht Ihr?
Man könnte es ja vllt so machen, dass jeder (von den 15), den die Person gern bei sich in der Gruppe hätte ein ja (bzw. eine 1) und die anderen 8 ein nein (bzw. eine 0) sind.... [Anmerkung: Ich hatte in der 11. Klasse mal ein bisschen Delphi, erinnere mich aber leider nur noch an die Nullen und Einsen].
Also im Endeffekt könnte das ganze so aussehen, dass man in der obersten Zeile 16 Namen eintippt. Unter jedem Namen folgen dann 15 weitere vom welchen 7 die Wunschkandidaten sind und 8 die "Nicht"-Wunschkandidaten.
Kann ja quasi auch eine Art Tabelle sein, bei welchen man dann einfach die gewünschten 7 der jeweiligen Person ankreuzt.


Ich hoffe ich konnte mich verständlich ausdrücken. Ansonsten bei Unklarheiten einfach Nachfragen! Gar kein Problem.
Und ich würde mich wirklich wahnsinnig freuen, wenn sich jmd dieser Herausforderung annehmen würde.


Danke!
 

beepsoft

Well-Known Member
c-b Team
c-b Experte
#2
Gehört das nicht in die Jobecke?
Also, wenn es nicht in Delphie sein musst, könnte ich das machen.
Was möchtest du denn bezahlen?

LG
 

amoxys

Well-Known Member
#4
Bei 16 Leuten komme ich auf 6.435 Verteilungen. Das ist ja sehr überschaubar. Aber wie würde man diese Verteilungen bewerten? Einfach die Anzahl der Überschneidungen mit den Wünschen der Leute aufsummieren? Oder wäre es besser, vorher diejenigen Verteilungen wegzufiltern, bei denen manchen Leuten nur sehr wenige Wünsche erfüllt werden? Oder sollten Wünsche, die auf Gegenseitigkeit beruhen, besonders stark bewertet werden?

Kann man seine Wünsche auch unterschiedlich stark gewichten? Macht es beispielsweise einen Unterschied, an welcher Position ein Partner in der Wunschliste steht? Vielleicht wäre es auch sinnvoll, wenn man mehr als 7 Wünsche äußern kann, damit die Bewertungsfunktion Alternativen hat. Oder weniger als 7, weil es einem egal ist.
 
#5
grüße dich amoxys.
ich möchte dir sehr für deine äußerst aufschlussreichen gedanken danken!
ich muss eingestehen, dass ich da im leben nicht drauf gekommen wäre....
es steckt anscheinend einiges mehr dahinter als ich gedacht hatte.

man könnte das ganze eventuell so angehen:
nachdem jeder seine 7 wünschpersonen angegeben hat erstellt man zu jeder einzelnen person eine liste, mit den personen die "am liebsten"/am ehesten mit der jeweiligen zusammen arbeiten möchten. -> die gut in eine gruppe passen.
bsp:
lisa
georg (6x)
jürgen (5x)
tamara (5x)
jaqueline (2x)
evelyn (1x)
maik (1x)


d.h.: da, wo der name lisa aufgetaucht ist, ist auch 6x der name georg aufgetaucht. oder mit anderen worten: in 6 von 16 abgegebenen listen taucht der name lisa und georg in der selben liste aus.
d.h., dass diese beiden wohl sehr gut zusammen.
und das macht man dann mit jeder person und vergleicht nachher die ergebnisse untereinander, sodass höchst wahrscheinlich mehrere mögliche ergebnisse dabei sein werden.
(aber es ergibt sich wahrscheinlich manches schon direkt:
bspw. dass ungedingt lisa und georg in einer gruppe sein müssen, da dort die übereinstimmung so groß war. ebenso, dass tamara super zu georg als auch zu lisa passt und daher auch unbedingt in dieser gruppe sein muss etc.)


nein, die reihenfolge der bewertung spielt keine rolle und man kann bspw. auch nur 6 angeben, wenn einem die 7. person egal ist.
 
#6
Neugierde

Da es hier ja nicht (zumindest nicht oeffentlich) weiter gegangen ist, moechte ich fragen wie die Sache ausgegangen ist.
Hast du dein Programm bekommen? Sind alle zufrieden?
In was wurde es nun programmiert?

Gruss JNV
 
#7
leider nein

leider hat niemand etwas für mich/uns programmiert :-(
noch wurden die gruppen nicht gebildet bzw. verkündet, wobei ich mir denke, dass das in ca. 3 wochen der fall sein wird.....
von dem her, bin ich immer noch für alles offen :)
 

Xpyder

Well-Known Member
c-b Experte
#8
Mir den entsprechenden Vorgaben (in diesem Thread wird das aber schon recht deutlich) wäre es für mich kein Problem, so etwas zu programmieren.
ALLERDINGS - programmiere ich unter DOS. Meine Programme laufen bis WinXP, danach (Vista, Win7) nur noch in DOSbox. Wenn ich mich auf Textmode beschränke, würde es auch noch in Vista/Win7 laufen (wenn auch, wie ich hörte, nicht in jeder Version).
Und ich persönlich programmiere auch immer gratis - d.h. für ohne Geld.
Aber ich schätze mal, niemand hat Interesse an einem DOS-Programm zur Lösung dieses Problems.
 
#9
also ich *wink* :rolleyes: hätte sehr großes interesse an dem programm und auf meinem alten computer habe ich auch noch xp drauf, mit welchem ich es dann ja zum laufen bekommen würde; wenn ich dich richtig verstanden habe.
was für angaben bräuchtest du denn noch?
wenn was unklar ist, einfach fragen! :)

ich würd mich echt wahnsinnig über deine hilfe freuen!

vlg
 

Xpyder

Well-Known Member
c-b Experte
#10
Ja, OK, ich setz mich da morgen mal ran. Ich werd' das über so eine Stochastik machen - Wahrscheinlichkeitsrechnung. Ich hab da damals mal so einen komischen Voodoo entwickelt, mit dessen Hilfe ich die sogenannten "Amerikanischen Kreuzworträtsel" geknackt habe. Das war mal so eine Anfrage - ebenfalls in diesem Forum. Eine ähnliche Methode wird auch bei dem vorliegenden Problem helfen.
Aber heute mach ich das nicht mehr. Also bis morgen!
 

Xpyder

Well-Known Member
c-b Experte
#12
So, ich programmiere jetzt schon seit einer Weile an diesem Projekt herum. Eingaben, Speichern, Ausgaben, Matrizen erstellen etc funktioniert schon alles...

ABER

Das Ganze erschließt sich als eine komplexere Aufgabe als anfänglich vermutet. Mein derzeitiger Ansatz dazu sieht so aus, daß jeder erst einmal eine Liste erstellen kann, mit wem er alles zusammenarbeiten will. Die Position in der Liste gibt an, wie wichtig es ihm ist, gerade mit dieser Person zusammenzuarbeiten. (Ich nenne die Personen jetzt mal A bis P, für 16 Personen. Hab grad keine Lust, mit Namen zu arbeiten - obwohl ich das im Programm testweise tue - mit alphabetisch aufsteigenden Anfangsbuchstaben...)

Dabei darf jede Person beliebig viele andere Personen angeben, mit denen sie zusammenarbeiten will, in absteigenden "Bedürfnis" - es müssen jedoch nicht alle 15 restlichen (im Beispiel ausgehend von 16 Personen) Personen angegeben werden, man kann auch nur 2 oder 3 oder keine angeben, wenn einem der Rest egal ist.

Dabei ergibt sich natürlich folgendes interessantes Problem 1:
Nehmen wir an, Person B schreibt Person G in seine seine Liste, aber Person G nicht Person B? Wie soll das behandelt werden? Im Moment wird es so behandelt, daß davon ausgegangen wird, daß es Person G egal ist. Stehen jedoch beide in ihren jeweiligen Listen, so erhöht das natürlich die Wahrscheinlichkeit - und je höher sie stehen, umso höher wird diese "Paarung" gewertet.

Problem 2 ist dann, daß sich natürlich weitere Verkettungen ergeben, nämlich, daß sowohl Person B noch weitere Personen genannt haben kann, ebenso wie Person G. Diese weiteren Personen haben aber untereinander auch noch entsprechende Beziehungen.

Würde man nun einen Ansatz nehmen, daß man immer die stärksten Paarungen welchselseitig auf die Gruppen aufteilen würde, würde das nicht funktionieren, da so auch Gruppierungen entstehen würden, die nicht zusammenpassen.

Beispiel B+G wäre die stärkste Paarung, F und J wäre die zweitstärkste Paarung - dann würde es trotzdem keine Möglichkeit geben, diese auf eine Gruppe aufzuteilen, da auch die restlichen Paarungen nicht unberücksichtigt bleiben dürfen.

Ich schätze, man müßte jede Paarung mit weiteren Attributen versehen - nämlich, wie sehr diese Paarung anderen Paarungen entgegensteht. Würde man alleine nach der stärksten Paarung zuerst gehen und diese gleich einer Gruppe zuordnnen, würde die Meinung von 2 Leuten stärker gewertet werden als die der restlichen 14 Leute. Ziel ist jedoch, die Meinungen aller Leute möglichst gleich zu bewerten - AUßERDEM wäre jedoch auch eine Meinungswertung jeder einzelnen Person zusätzlich noch nützlich - und zwar: Je weniger andere Personen UNBEDINGT von einer Person gewünscht werden, um so "WERTVOLLER" ist deren Meinung - denn eine Person, die sich darauf beschränkt, nur einen oder zwei Wunschpartner zu nennen, macht die Gruppenbildung für alle ja leichter als eine, die z,B. darauf besteht, 7 Personen zu nennen (also die ganze eigene Gruppe vordefinieren zu wollen).

Ich erhebe jetzt schon Werte für:
- Wieviele andere Personen hat jede Person genannt?
- Von wievielen anderen Personen WURDE eine Person genannt/gewollt (hier zusätzlich auch noch ein Wert, der aufaddiert, an welcher Position sie genannt wurde - je höher die Position, umso höher der Endwert)
- Welche Wunschpaare ergeben sich? Und zu jedem Paar die Summe der Positionen (auch wieder: Je höher die "Paarung", umso größer der Wert).

Problem 3 ist natürlich auch sehr interessant:
Werden zu viele Paarungen gewünscht, müssen bestimmte Paarungen unberücksichtigt werden - aber wonach wählt man das aus? Eine Paarung ist ja auch für andere Personen evtl wichtig, d.h. nehmen wir an, die Paarung A+E wäre gegeben, aber es gäbe noch VIER Arten der restlichen Personen:
- Person hat weder A noch E genannt
- Person hat A genannt
- Person hat E genannt
- Person hat A und E genannt.
Das bedeutet: Je mehr ANDERE Personen A UND E in derselben Gruppe wollen, umso wichtiger wird die Paarung A+E. ABER: Personen, die A ODERE nennen, kann es entweder egal sein, ob die jeweils andere Person in ihrer Gruppe ist oder nicht - d.h. hier kann man dann keine weitere Wertung dieser Paarung vorgenommen werden - und zwar, weil zu diesem Zeitpunkt ja noch nicht feststelt, ob eine eventuelle Person K, die A oder E (oder beide) genannt hat, am Ende WIRKLICH in deren Gruppe landet oder nicht.

Problem 4 wäre, wenn zu wenige Paarungen vorgeschlagen werden, würden eventuell Leute übrigbleiben - wie sind diese zu verteilen?

Im Prinzip wirkt das ganze so wie eine Matrix, wo jedes mit jedem anderen Element verbunden ist und diese Verbindung dann ebenfalls von jeder anderen möglichen Verbindung beinflußt wird. Das wird ein riesengroßes Konstrukt.

Wahrscheinlich würde ein "Brute-Force" Verfahren an dieser Stelle mehr bringen - und zwar folgendermaßen (ist mir gerade eingefallen):

Es gibt 2 Gruppen. Man legt 8 Personen in Gruppe 1 - die restlichen 8 sind demzufolge in Gruppe 2.
Da die "Reihenfolge", wie die Personen in einer Gruppe liegen, egal ist, geht man so vor: (Personen werden jetzt mal numeriert)

Schritt 0:
Man legt in Gruppe A die Personen 1,2,3,4,5,6,7,8 und in Gruppe B die Personen 9,10,11,12,13,14,15,16). Dies sind "Pseudo-Gruppen".
Außerdem legt man eine "binäre" Pseudo Gruppe C an, die setzt man auf 0,0,0,0,0,0,0,0. (Man kann auch ein Byte nehmen mit Bits).
Außerdem legt man ein Array D von 256 Werten (Word, Long oder so an). 256, weil 2^8 = 256. Und setzt den Index DIX dafür auf 0.

Schritt 1:
Für alle "Bits", die in Gruppe C=0 sind, setzt man die Personen in GRUPPE 1 auf die aus PSEUDOGRUPPE A, für alle "Bits", die in Gruppe C=1 sind, setzt man die Personen in GRUPPE 1 auf die aus PSEUDOGRUPPE B. Für Gruppe 2 macht man es genau umgekehrt - klar, denn da kommen die restlichen Personen hin.
(Und ja, ich weiß, zuerst sind in Gruppe 1 alle aus Pseudogruppe A und in Gruppe 2 alle aus Pseudogruppe B.)

Schritt 2:
DANN testet man, wie gut die Zusammengehörigkeiten ausgeglichen sind mit Hilfe von Formeln, die die Zufriedenheit der einzelnen Personen ausdrückt für beide Gruppen plus Meinungen/Meinungswichtigkeit, etc.... D.h. man testet für beide Gruppen die Paarungen etc...
Diesen Zufriedenheitswert legt man in Array D[DIX] ab und erhöht DIX um 1.

Schritt 3:
Man erhöht die Pseudo-Gruppe C um 1. Das wäre dann als erstes 0,0,0,0,0,0,0,1. Die Werte werden binär erhöht, wäre danach dann 00000010, dann 00000011, dann 00000100 usw... Warum ich das mit einer Pseudo-Gruppe und nicht mit einer Binärzahl mache? Nun, nehmen wir an, wir wollen das Programm mal auf 3 oder 4 Gruppen oder so erweitern. Dann wird der "Überlauf" ja nicht bei 1 wieder zu 0, sondern bei 2 oder 3...
Dann prüft man, ob DIX schon den Maximalwert erreicht hat ODER ob das Pseudo-Array C = 1,1,1,1,1,1,1,1 ist. Wenn NEIN, geht man wieder zu Schritt 1.

Schritt 4:
Man hat nun ein Array D, das die verschiedenen Zufriedenheitswerte listet und die Kombination mit dem höchsten Zufriedenheitswert wird genommen. Mir ist natürlich klar, daß man so ein Array D nicht bräuchte, da man auch zu Anfang einen Zufriedenheitswert=0 definieren kann und wenn in Schritt 2 ein größerer Wert erscheint, dann diesen auf Zufriedenheitswert setzen, sowie sich diesen Index (bzw den Zustand von PseudoArray C) merken.
ABER: Legt man ein Array an, so kann man nachträglich alle Kombinationen je nach Zufriedenheitswert absteigend auflisten - außerdem kann man auf diese Weise dann auch noch darauf reagieren, wenn zwei Kombinationen den gleichen Zufriedenheitswert liefern - quasi manuell die Kombination aussuchen.

Ich baue das jetzt erstmal so in mein Programm ein.
ABER: Es wäre wahrscheinlich eine gute Idee, wenn man jetzt noch Parameter hätte, wonach die Zufriedenheit der Personen eingestuft wird.
Zum Beispiel: Zufriedenheit von Person A wird um den "Stellenwert" (in der Liste der gewünschten Personen) erhöht, wenn die Person in der Liste enthalten ist und um den "Stellenwert" der gewünschten Person VERRINGERT, wenn NICHT enthalten. Man könnte die Zufriedenheit bei ENTHALTEN aber ach z.B. mit 1,5 oder 2 (oder anderen Wert) multiplizieren, so daß wenn eine gewünschte Person enthalten immer noch zufriedener als wenn eine andere gewünschte nicht enthalten (damit könnte man es ausgleichen, daß 2 nicht enthaltene Personen eine "höhere" enthaltene aus-subtrahieren).
Und ja, der Zufriedenheitswert kann auch negativ werden. Der Zufriedenheitswert einer Person wird dann noch mit dem Reziproken der Anzahl eigener Wünsche oder direkt mit der Anzahl der Wünsche durch andere multipliziert oder so etwas - um die Wichtigkeit der Zufriedenheit dieser Person in umgekehrte Relation zur Menge ihrer Ansprüche zu setzen (wer mehr Ansprüche hat, ist schlechter für die Allgemeinheit) und in direkter Relation dazu, wie oft sie von anderen gewünscht wird (wertvoller für die Allgemeinheit).
Es klingt vielleicht komisch, aber es ist auch nicht gerade einfach, so emotionale Dinge wie "ich will mit dieser Person gern zusammenarbeiten und mit jener nicht" in Zahlen und Formeln darzustellen, da Ratio und Emotio sich eigentlich gegenseitig widerspreichen.

Der GESAMTE Zufriedenheitswert aller Personen muß dabei übrigens nicht einfach die SUMME aller Zufriedenheiten sein, sondern der DURCHSCHNITT - oder NOCH BESSER:
Man bildet den Durchschnitt aller Zufriedenheiten. Und dann addiert man alle ABSOLUTEN Abstände der einzelnen Personen-Zufriedenheiten von diesem Durchschnitt. Je geringer dieser Wert ist, umso "GLEICH ZUFRIEDEN" sind die Personen (es geht also nicht um die maximale Zufriedenheit, sondern darum, alle Personen gleichwertig zufriedenzustellen).
Würde man NUR nach der absoluten Zufriedenheit suchen, würde man damit Außenseiter ausschließen.

WICHTIGE ANMERKUNG
Bedingt durch die Besonderheit dieser Aufgabe ergibt sich noch ein kleines Problem:
Die Werte (zum Beispiel!) für das C-Array 01001011 und 10110100 ergeben natürlich dasselbe Ergebnis - dnn hier werden die Personen Gruppe 1 und 2 zugeordnet und dann nachher noch einmal derselbe Test gemacht, mit vertauschten Gruppen! Dies ist ein Sonderfall, da ja hier (in dem vorliegenden Fall) keine Rolle spielt, ob man in Gruppe 1 oder 2 ist (bzw Gruppe 0 oder 1, wenn man so will), sondern nur, mit welchen Personen man zusammen in dieser Gruppe ist.
Die Lösung (zumindest für 2 Gruppen) ist ganz einfach: Man testet nur 128 Durchgänge, (also 00000000 bis 01111111) was bedeutet, daß Person 1 immer in Gruppe 1 bleibt, d.h. Gruppe 1 die ist, in der es Person 1 gibt (da am Ende sowieso egal ist, in welcher Gruppe man ist).

Noch eine Anmerkung:
Es wäre auch nicht zwingend erforderlich, die Personen, die man in seine "Wunschliste" einträgt, zu "werten" - es könnte auch so sein, daß alle eingetragenen Personen den gleichen "Wunsch-Wert zugewiesen bekommen - allerdings wird das Ergebnis dann "allgemeiner" ausfallen. Und im Normalfall weiß ja jeder, daß bei so einer Personenverteilung auf Gruppen nicht jeder Wunsch berücksichtigt werden kann - außer im Idealfall, der aber in der Realität selten eintritt. (Im Falle dieses Idealfalls wäre auch kein Programm nötig, um die Gruppierungen zu berechnen.) Und weil man weiß, daß es keinen Idealfall gibt, muß man sich mit dem "kleinsten Übel" zufriedengeben und wird daher schon von sich aus selbst ein "Ranking" seiner Wunschpersonen anlegen.

Das ist also mein derzeitiger Ansatz dazu. Ich würde mich freuen, dazu noch eine Meinung zu hören - also ob mit der "Zufriedenheitswertung" auf diese Art vorgegangen werden kann.
 
#13
hallo xpyder,

wie ich sehe hast du dir schon sehr viele gedanken gemacht!
zuerst einmal:
wir hatten es so gehandhabt, dass die reihenfolge der angegebenen personen keine rolle spielt. es ist einfach so, dass diejenigen, die man angibt (max. 7) man gerne in seiner gruppe haben würde.
die restlichen (mind.) 8 leute, entspricht es der wahrheit oder nicht, als nein gewertet werden.

was du in problem 2 beschreibst mit den paarungen klingt sehr interessant.
wenn ich dich richtig verstanden habe, ansonsten ist es als vorschlag gemeint, so schaut man in allen 16 listen, wie häufig die jeweilige paarung vorkommt. bsp.:
13 leute geben in ihrer liste die paarung B+G an
11 leute geben in ihrer liste die paarung C+F an
9 leute geben in ihrer liste die paarung B+D an
...
d.h. die paarung B+G würde nach meinung aller sehr gut zusammen passen.
jetzt muss man nur noch schauen, wie das ins gesamtkonzept passt.
kann man also B+G in eine gruppe stecken, oder hebt es sich durch die anderen paarungen wiederum auf, da bspw. ingesamt gesehen ubedingt B und D und F und C in eine gruppe gehören?

hm, jedoch, je mehr ich mir deine problemstellungen durchlese, desto komplizierter scheint es mir. man kann ja nicht jede einzelne paarung von jeder angegeben liste als mögliche paarung betrachten. da würden wir ja anhand einer liste schon auf 2^7 möglichkeiten kommen, wenn ich richtig gerechnet habe; sprich: 128

da scheint mir folgendes sinnvoller:
"brute-force"
ich muss ganz ehrlich sagen, dass ich maximal 40% verstanden habe, jedoch kann ich folgendem absolut zustimmen:
"Der GESAMTE Zufriedenheitswert aller Personen muß dabei übrigens nicht einfach die SUMME aller Zufriedenheiten sein, sondern der DURCHSCHNITT - oder NOCH BESSER:
Man bildet den Durchschnitt aller Zufriedenheiten. Und dann addiert man alle ABSOLUTEN Abstände der einzelnen Personen-Zufriedenheiten von diesem Durchschnitt. Je geringer dieser Wert ist, umso "GLEICH ZUFRIEDEN" sind die Personen (es geht also nicht um die maximale Zufriedenheit, sondern darum, alle Personen gleichwertig zufriedenzustellen).
Würde man NUR nach der absoluten Zufriedenheit suchen, würde man damit Außenseiter ausschließen."
und habe ich es richtig aufgefasst, dass man dann in diesem verfahren auch wirklich einen wert angeben muss, wie gerne man mit der jeweiligen person in einer gruppe wäre?

und ja es ist egal, in welcher gruppe man nachher ist. es geht ja nur darum, mit welchen leuten man in der gruppe.
daher könnte man sagen person C ist auf jeden fall in gruppe 1 und der rest der leute orientiert sich danach. beim festlegen einer person für gruppe 2 geht dies aber nicht, da es ja sein könnte, dass diese person unbedingt in gruppe 1 (bei person C) sein sollte - ermittelt anhand der listen.

ich freue mich schon auf deine antwort
lg
 

Xpyder

Well-Known Member
c-b Experte
#14
Ja, Du hast es genau richtig erfaßt.
* Es gibt 128 Möglichkeiten.
* Man testet alle durch und erstellt dafür Zufriedenheitswerte/ Durchschnitte/ Abstände und nimmt die Kombination mit dem geringsten Abstand und/oder höchsten Zufriedenheitslevel - je nachdem, wie man es gerne möchte.
* Ja, eine Person kann man für eine Gruppe festlegen. Es ist ja egal, ob dies rechnerisch für Gruppe 1 oder 2 gemacht wird - wie man die Gruppen nachher nennt, ist einem ja selbst überlassen und Tauschen der Gruppen führt ja zum selben Ergebnis. (Denn es ist ja nicht gefragt, in welcher GRUPPE man sein will, sondern nur, mit welchen PERSONEN man ZUSAMMEN in irgendeiner der Gruppen sein will.)

ABER:
Nein, es ist NICHT erforderlich, daß man die Personen "staffelt", d.h. ihnen eine Wertigkeit zuordnet, mit wem man am liebsten zusammen sein will, mit absteigender Wertigkeit. Es ist ebenfalls möglich, alle gleichwertig zu behandeln (intern erhalten diese Personen dann den Wert 1, die nicht genannten den Wert 0). Auch hier ergeben sich Rechenergebnisse. Diese werden sich selbstverständlich von der "gestaffelten" Methode unterscheiden. UND es könnte eventuell auch mehrere GLEICHE Ergebnisse geben. Dies ist aber insofern kein Problem, da das Programm hinterher sowieso alle möglichen Kombinationen der Wertigkeit (also beginnend mit den besten) ausgeben kann - und man danach immer noch manuell eine aussuchen könnte.

Programmtechnisch wäre es kein Problem, sogar beides gleichzeitig abzufragen (also sowohl mit verschiedenen als auch mit gleichen Wertigkeiten zu arbeiten). Eine gleiche Wertigkeit wäre dann ORD(Wertigkeit<>0), die eben 1 oder 0 liefern würde, für "enthalten" oder "nicht enthalten") und daß derselbe Programmteil quasi beides je nach einer Wahl abarbeiten würde.

Ich werde also irgendwann demnächst mal dieses Tool auf meine Webseite zum Herunterladen stellen. Ich habe es in Textmode gemacht - so kann man es unter Windows auch im Fenster benutzen.
 
#15
danke schön!
bedeutet das, dass du dann jetzt komplett ein "brute-force"-programm erstellst?
genau: das mit den mehreren ergebnissen hatte ich schon vermutet, sodass man dann zwischen diesen wiederum auswählen oder losen oder was auch immer machen muss :)

ich freu mich schon auf dein progamm! :)
lg
 

amoxys

Well-Known Member
#17
Das mit den 128 Möglichkeiten versteh ich immer noch nicht. :(

Irgendwie war das damit erklärt, dass es 128 Zustände von 00000000 bis 01111111 gibt. Aber was sollen diese Zustände darstellen?
 

Xpyder

Well-Known Member
c-b Experte
#18
@x3r0x:
Ich programmiere immer gratis. Mir macht programmieren nämlich Spaß.
Und ich mag kein Bier (und auch sonst nichts alkoholisches). Aber wahrscheinlich sollte das nur ein Scherz sein.

(Daß es jetzt so gedauert hat, lag daran, daß ich noch Features in ein Projekt für jemand anderen eingebaut habe.)

Das mit den 128 Möglichkeiten versteh ich immer noch nicht. :(

Irgendwie war das damit erklärt, dass es 128 Zustände von 00000000 bis 01111111 gibt. Aber was sollen diese Zustände darstellen?
Es bezieht sich auf 16 Personen, die in 2 Gruppen aufgeteilt werden sollen, also 8 Personen je Gruppe.

Mein Ansatz dazu:
Ich nenne die Personen einfach mal A bis P - die Namen sind ja egal für die Aufteilung. Man teilt die Gruppen zuerst so auf:

Gruppe XY: A B C D E F G H
Gruppe YX: I J K L M N O P

Und dann testet man alle 256 (!) Möglichkeiten durch (das mit den 128 erkläre ich noch!), indem man einen Indexwert von 00000000 bis 11111111 durchzählt, binär. (Binär nur deshalb, weil es 2 Gruppen werden sollen. Wären es mehr als 2 Gruppen, wird die Sache komplexer.)
Das funktioniert, weil es ja EGAL ist, an welcher "Position" eine Person in einer Gruppe ist, Hauptsache, sie ist enthalten oder nicht enthalten.

Und wenn in dem Indexwert eine Stelle 0 ist, dann bekommt Gruppe 1 an der Stelle die Person aus Gruppe XY und Gruppe 2 die Person aus Gruppe YX. Ist an dem Indexwert eine Stelle 1, dann bekommt Gruppe 1 an der Stelle die Person aus Gruppe YX und Gruppe 2 die Person aus Gruppe XY.

Beispiel: Indexwert ist 01001101. Das ergibt die Gruppierungen:
Gruppe 1: A J C D M N G P
Gruppe 2: I B K L E F O H

Und nun noch die Erklärung für die 128 statt 256:
Würde man es mit 256 machen, würden sich ja Kombinationen wiederholen, das heißt, bei der Kombination 11111111 wären die Gruppen
Gruppe 1: I J K L M N O P
Gruppe 2: A B C D E F G H

Damit wären die Gruppen lediglich vertauscht, was aber nichts bringt, denn es geht ja nur darum, die Personen auf zwei Gruppen aufzuteilen, aber dafür gibt es eben immer 2 Möglichkeiten, weil die "invertierte" Darstellung immer jeweils das gleiche Ergebnis hervorbringt, nur mit vertauschten Gruppen. Um dies zu verhindern, kann man entweder alle Möglichkeiten testen, aber die ausklammern, für die es schon eine Gruppenverteilung gibt ODER man ändert einfach eines der Bits GAR NICHT - schon gibt es keine invertierten Darstellungen mehr. Der Einfachheit halber ist es so, daß man einfach das oberste oder unterste "Bit" nicht ändert. Ändert man das oberste nicht, so zählt man eben nur von 0 bis 127 (00000000 bis 01111111), also 128 Möglichkeiten. Ändert man das unterste "Bit" nicht, zählt man von 0 bis 254, aber in 2er Schritten (00000000 bis 11111110), was ebenfalls 128 Möglichkeiten ergibt.

Um es nicht "rechnerisch", sondern "logisch" zu erklären:
Wenn man erst EINE Person einer der beiden Gruppen zuteilt und diese Gruppe GRUPPE EINS nennt und dann alle anderen Personen aufteilt, ergibt sich dasselbe Ergebnis, als wenn man diese Person einer der Gruppen zuteilt und diese Gruppe GRUPPE ZWEI nennt.


Die RICHTIGE Methode ist natürlich noch leicht anders - das könnte ich auch noch kurz erklären, falls Interesse. - Mit RICHTIGER Methode meine ich eine, die auch mehr als 2 Gruppen erlaubt. Falls kein Interesse daran, dann einfach hier nicht weiterlesen.

Also: Die 2er-Gruppenverteilung ist einfach nur eine "Subfunktion" der "richtigen" Methode (die ich mir auch ausgedacht habe), d.h. man kann die 2er-Verteilung auch mit dieser jetzt von mir vorgestellten Methode machen.

Nehmen wir an, wir wollen 16 Personen auf 3 Gruppen aufteilen. Das ergibt maximal 6 Personen pro Gruppe, denn 16/3 = 5,3333 und man muß immer aufrunden. Das heißt, wir haben quasi 18 Personen, 16 "echte" Personen und 2 "Pseudo-Personen", die wir "hinten dranhängen". Damit haben wir 3 Gruppen, eine mit 6 Personen und 2 mit je 5 Personen und einer "Leer-Person", die nur dazu da ist, das Ganze rechnerisch hinzukriegen.

Wir haben jetzt also 18 Personen (rechnerisch ist es nicht wichtig, ob sie "Leer" sind oder nicht) und teilen sie in 3 Pseudo-Gruppen:

Gruppe #0: A B C D E F
Gruppe #1: G H I J K L
Gruppe #2: M N O P Q R

(Q und R sind jetzt z.B. die "Leer-Personen").

Dann beginnt man einen Zähler (6 stellig) laufen zu lassen, der aber im 3er-System läuft, also mit den Ziffern 0, 1 und 2..

Und dann ordnet man der Gruppe EINS die Personen aus den jeweiligen Pseudo-Gruppen zu.
Beispiel: Der Zähler hat den Wert 021201, dann erhält

GRUPPE EINS: A M H P E L

Übrig bleiben nun die Werte, bzw Personen B C D F G I J K M O Q R, diese teilen wir wieder in 2 Pseudo-Gruppen auf:
Gruppe ##0: B C D F G I
Gruppe ##1: J K M O Q R

Dafür machen wir nun einen Zählwert (wieder 6stellig) von 000000 bis 111111, aber im 2er-System und verteilen es auf Gruppe ZWEI so, daß für die Bits im Zählwert die jeweilige Person aus der Pseudo-Gruppe benutzt wird. Nehmen wir an, der Zählwert wäre 010110, dann wäre:

GRUPPE ZWEI: B K D O Q I

Nun ist nur noch EINE Gruppe übrig. Diese erhält die restlichen Personen, die ja C F G J M R sind:

GRUPPE DREI: C F G J M R

Dies entspricht auch der Aufteilung in 2 Gruppen, denn wenn man einer Gruppe die Hälfte der Personen zuweist, sind die andere Hälfte automatisch die restlichen.

So! Nun haben wir 3 Gruppen. Erklärung: JEDESMAL, wenn sich der 3er Zähler um eins ändert, muß der 2er Zähler wieder bei 0 anfangen und die Kombinationen für die restlichen Personen durchspielen! Sollen es 4 Gruppen sind, so entstehen 3 Kaskaden, d.h. erst ein Zähler im 4er System, dann einer im 3er System und dann einer im 2er System. JA, das klingt kompliziert, wenn man es von Hand macht und nicht dem Computer überläßt. Aber Computer sind ja schneller als Menschen und einmal korrekt eingegeben, machen sie auch immer wieder dasselbe. Computer sind ja bekanntlich blöd - aber dafür ziemlich schnell. Deshalb lassen wir ja so Dinge von Computern machen...

So, nun kommt noch ein Zwischen-Schritt. Den MUß man nicht machen, KANN man aber:
Man hat jetzt 3 Gruppen. Nun sortiert man innerhalb der Gruppen erstmal die Personen nach "Nummer" (bzw Buchstaben), das ergibt:
GRUPPE EINS: A E H L M P
GRUPPE ZWEI: B D I K O Q
GRUPPE DREI: C F G J M R
(Das kann man auch schon tun, wenn man die Gruppen bildet!)
Außerdem sortiert man noch die Gruppen nach "Größe", bzw nach der ersten Person, in diesem Fall ist es schon gegeben: GRUPPE EINS, GRUPPE ZWEI, GRUPPE DREI
und bildet einen "String" oder wasweißich daraus, der die Gruppenverteilung angibt.
VERTEILUNG: A E H L M P B D I K O Q C F G J M R
(Die Teilung nach je 6 Personen kann man sich denken.)
Warum tut man das? Nun ja, die Verteilungen speichert man in Listen, denen man dann die Zufriedenheitswerte zuordnet. Und wie die Gruppen-NUMMERN sind, ist ja quasi EGAL, Hauptsache die zusammengehörigen Personen sind in einer Gruppe. Durch dieses kaskadierte Hochzählen ergeben sich aber eventuell Doppelungen von Kombinationen, d.h. es sind zwar die gleichen Personen zusammen in Gruppen, aber die Gruppen-NAMEN sind dann vertauscht. Für 2 Gruppen ergeben sich immer (siehe oben) 2 Kombinationen (nämlich 1+2 und 2+1). Für 3 Gruppen ergeben sich schon 6 Kombinationen (nämlich 1+2+3, 1+3+2, 2+1+3, 2+3+1, 3+1+2 und 3+2+1)... und so weiter.
Indem man die Gruppen (und Personen innerhalb jeder Gruppe) ordnet, kann man diesen "String" mit den schon in der Gruppierungs-LISTE vergleichen und nur DANN, wenn es eine NEUE Kombination ist, muß diese Gruppierung in die Gruppierungs-Liste eingetragen und der "Zufriedenheitswert" ermittelt werden.
Achja: Man sollte darauf achten, daß man Gruppierungen, in der eine Gruppe mehr als eine "Pseudo-Person" enthält, von vornherein ausschließt!

Wie man leicht sieht, erhöht sich die Anzahl Berechnungen und Kombinationen sowohl durch Erhöhrung der Personenanzahl, als auch durch Erhöhung der gewünschten Gruppen - je mehr Gruppen vorhanden sind, umso mehr mögliche Kombinationen entstehen.

Und ja, ich weiß:
Man könnte auch eine 18-stellige Zahl nehmen, die man mit 18 Ziffern (für die 18 Personen) durchlaufen läßt - aber ich erkläre mal kurz, wieso das nichts bringt:

* Dabei hätte man ja in weit über 99% der Fälle doppelte "Ziffern" in der "Zahl" - diese Fälle sind von vornherein unbrauchbar und müßten jedesmal ausgesondert werden.

* Man könnte zwar auch: eine erste Ziffer von 0 bis 17 durchlaufen lassen, die zweite dann auch von 0 bis 17, unter Auslassung der ersten, die dritte auch von 0 bis 17 unter Auslassung der ersten beiden.... usw. - und erhielte zwar auch alle möglichen Kombinationen, die nur aus verschiedenen "Ziffern" (Personen) bestehen, aber man hätte eben Folgen dabei wie z.B.

A B C D E F
F E D C B A
D E A F C B (Hihi, taubes CB-Funkgerät....)
C D B F E A
usw...
... die ja quasi, wenn sie an 6er Positionen stehen, ALLE dieselbe Gruppierung bedeuten würden, d.h. man müßte wesentlich mehr Gruppierungen testen und aussondern.

Man sieht: Je mehr Gruppen es geben soll, umso mehr Tests sind nötig.

--------------------------------------------------------------------------------------------
ANDERER ANSATZ
Nun, wieso testet man dann nicht nur die "gewünschten" Kombinationen?

Das kann man natürlich auch machen - und wenn sich jede Person auf maximal die Hälfte (bwu 2 Gruppen), ein Drittel (bei 4 Gruppen) usw. beschränkt, wäre es noch einfacher.

Das Ganze ginge dann so:
Man legt einen Zähler PERSON an, der zählt von 1 bis Anzahl_Personen (oder von 0, is ja auch Wurst, wie man das intern numeriert. Ich numeriere immer ausgehend von 0, weil das die erste Zahl in jedem Zahlensystem ist).

Für diese Person legt man eine Gruppe an, die aus ihr selbst (PERSON) und den von ihr gewünschten Personen besteht. Und nur die restlichen "Stellen" füllt man mit restlichen Personen auf.
D.h. nehmen wir an (16 Personen, 2 Gruppen à 8 Personen): Person A will Personen F, G und J haben.
Dann wird daraus eine Gruppe mit A F G J
D.h. es sind noch 4 Personen (aus 12) "frei", die man nun als eine 4 stelligen Wert durchlaufen läßt, mit allen 4er Kombinationen aus 12 Personen. Die jeweils restlichen 8 sind dann der 2. Gruppe zugeteilt. Für jeden Fall stellt man einen Zufriedenheitswert auf.

Das macht man für alle 16 Personen.
Und das ergibt natürlich andere Möglichkeiten, nämlich, daß bei 3 oder mehr Gruppen, für den Zufriedenheitswert einer Person egal ist, wie die Kombination der anderen beiden Gruppen aussieht (in denen er/sie selbst nicht enthalten ist), solange die Zusammensetzung der eigenen Gruppe möglichst optimal ist.

Das Schwierige daran ist nur, daß die anderen Personen ebenfalls ihre Befindlichkeiten haben und der Zufriedenheitswert einer Kombination ja nur aus allen enthaltenen Mitgliedern errechnet wird.

Will sagen: Eventuell ist es auch sinnvoll, (vor allem bei mehr als 2 Gruppen), diesen Weg zu gehen, d.h. nur Personen in Gruppen zu testen, die man wirklich selbst gewünscht hat - dann darf man aber nicht mehr Personen angeben, als in eine Gruppe passen, sonst gilt für sich selbst nur diese eine Kombination als optimal (was ja auch stimmt).

Dieser Ansatz scheint zwar auch geeignet, da es die zu prüfenden Kombinationen minimiert - jedoch hat er den kleinen Nachteil, daß wenn Jeder zu viele und zu unterschiedliche Kombinationen wählt, bestimmte Kombinationen gar nicht mehr getestet werden, auch wenn sie, verteilt auf alle Personen, einen besseren "Gesamtzufriedenheitswert" ergeben würden. Dies wären dann solche "notwendiges Übel" oder "kleinstes gemeinsames Vielfaches" Kombinationen, die zwar für keinen optimal wären, aber in der Gesamtheit dafür sorgen würden, daß alle gleich zufrieden (oder gleich unzufrieden) damit wären.

------------------------------------------------------------------
Der Möglichkeiten gibt es viele und "Zufriedenheit" bei Zusammensetzungen von Personen zu Gruppen ist kein wirklich meßbarer Wert, man kann ihn höchsten versuchen zu abstrahieren. Es sieht am Ende eher so aus, als würden mehrere der Verfahren zu irgendeinem Ergebnis führen. Welches davon das "optimalste" oder "fairste" ist, muß am Ende sowieso alleine der Mensch entscheiden.

Im Prinzip besteht der ganze Schlunz aus zwei Teilproblemen:
1.) Wie kann man möglichst effektiv alle möglichen Kombinationen durchzählen, und zwar, OHNE doppelte und OHNE unbrauchbare (d.h. von vornherein für keinen wünschenswerte) mitzuzählen?

2.) Wie kann man möglichst fair einen allgemeinen Zufriedenheitswert erreichnen, der sich aus einer gleichwertigen Zufriedenheit der einzelnen Personen zusammensetzt?

--------------------------------------------------------------------

Und ja, ich weiß: Ich verwirre manche Leute immer mehr mit diesem Gelaber. Aber es ist eben nicht so, als würde ich mir darüber keine Gedanken machen.
 

amoxys

Well-Known Member
#19
Woah, das ist ziemlich ausführlich. :)

Ich bin noch nicht komplett durch den Post durchgekommen, aber bis zum Teil mit der "richtigen" Methode hab ich mich schon vorgearbeitet.

Und da wollte ich schon mal eine Zwischenfrage stellen.

Gruppe XY: A B C D E F G H
Gruppe YX: I J K L M N O P
Würden die Personen A und I niemals in der gleichen Gruppe landen können?


Es sieht am Ende eher so aus, als würden mehrere der Verfahren zu irgendeinem Ergebnis führen.
Das habe ich auch festgestellt. :D Man wendet irgendwelche Algorithmen an, und es gibt irgendein Ergebnis. Vielleicht wäre es gar nicht mal schlecht, die Gruppen einfach zufällig zu verteilen. Sollte ja wohl kein Problem darstellen, und dann fühlt sich keiner benachteiligt.
 
Zuletzt bearbeitet:

Xpyder

Well-Known Member
c-b Experte
#20
Woah, das ist ziemlich ausführlich. :)

Ich bin noch nicht komplett durch den Post durchgekommen, aber bis zum Teil mit der "richtigen" Methode hab ich mich schon vorgearbeitet.

Und da wollte ich schon mal eine Zwischenfrage stellen.

Würden die Personen A und I niemals in der gleichen Gruppe landen können?
Siehste, da haste recht!
Daran sieht man eben, wie kompliziert das ganze Problem mit den Kombinationen sich darstellt. Aber auch dafür habe ich natürlich eine mögliche Lösung.
Werde ich bei Gelegenheit mal posten.
 
Oben