Heiraten

[Daniel22]

Hallo Alle! Hab ne interesante Aufgabe zum lösen. Hab selbst schon ein wenig programmiert und komme nicht weiter und bitte daher um eure Hilfe. Die Aufgabe lautet:
Gegeben sind zwei Listen von Männern und Frauen. Beispielsweise:
Hierbei sind sowohl die Frauen als auch die Männer (eindeutig) durchnummeriert
und haben jeweils eine vollständige Wunschliste = Präferenzliste
(„Alle Männer (Frauen) sind von jeder Frau (jedem Mann) in
eine Rangordnung gebracht worden“; z.B. hat Julia die höchste Präferenz
für Peter, dann die zweithöchste für Romeo, …).
Der Algorithmus von Gale & Shapley besagt, dass bei Vorliegen vollständiger
Präferenzlisten sowohl „frauenfreundliche“ als auch „männerfreundliche“,
„stabile“ Partnerschaften für alle Männer und alle Frauen
existieren.
„Stabil“ bedeutet hier, dass es am Ende nicht einen Mann und eine
Frau aus verschiedenen Partnerschaften gibt, wo der Mann auf der
Präferenzliste der Frau und die Frau auf der Präferenzliste des Mannes
höher angesiedelt sind als die tatsächlichen Partner. „Freundlich“ bezieht
sich auf die Tatsache, wer die Wahl hat, seine Präferenzen
„durchzusetzen“.
Der Algorithmus kann (für „frauenfreundlich“) umgangssprachlich wie
folgt beschrieben werden:
Nr Name Partner Präferenzen
1 Julia 4 1 2 3
2 Trudi 1 4 2 3
3 Anna 4 1 2 3
4 Heidi 1 3 2 4
Nr Name Partner Präferenzen
1 Romeo 2 1 4 3
2 Bob 4 2 1 3
3 John 3 1 2 4
4 Peter 3 2 1 4
Solange es noch unverheiratete Frauen f gibt:
Macht f dem Mann m ganz oben auf Ihrer Präferenzliste einen
Heiratsantrag.
Ist m unverheiratet, so heiraten m und f.
Ist m verheiratet, so prüft er, ob f weiter oben auf seiner
Präferenzliste steht als sein jetziger Partner. Ist dies der Fall, so
lässt er sich von seinem jetzigen Partner scheiden und heiratet
f.
Gelingt es f nicht m zu heiraten, so streicht Sie ihn aus Ihrer
Präferenzliste und versucht es erneut.
Sie können diesen Algorithmus sicher relativ leicht nachvollziehen (eventuell
mit einem Rollenspiel!), aber die Programmierung ist nicht so
offensichtlich. Daher hier ein Programmgerüst:

import java.util.*;
public class Partnervermittlung {
public static void main(String[] args) {
List<Person> men = new ArrayList<Person>();
men.add(new Person(1,"Romeo",2,1,4,3));
men.add(new Person(2,"Bob",4,2,1,3));
men.add(new Person(3,"John",3,1,2,4));
men.add(new Person(4,"Peter",3,2,1,4));
List<Person> women = new ArrayList<Person>();
women.add(new Person(1,"Julia",4,1,2,3));
women.add(new Person(2,"Trudi",1,4,2,3));
women.add(new Person(3,"Anna",4,1,2,3));
women.add(new Person(4,"Heidi",1,3,2,4));
List<Person> unMarried = new ArrayList<Person>();
unMarried.addAll(women);
//Lösung (Gale & Shapley 1962)
while(!unMarried.isEmpty()) {
//Hier müss ich meine Lösung noch programmieren
}//end while
for (Person p : men) System.out.println(p);
}//end main
}//end class Partnervermittlung
class Person {
private String name;
private int index;
private List<Integer> preference;
private Person partner;
public Person(int index,String name,int... p) {
this.name = name; //der Name der Person
this.index = index; //eindeutige Nummer zwischen 1 und N
preference = new ArrayList<Integer>();//die Präferenzliste
for (int j : p) preference.add(j);
partner = null;
}
public boolean isMarried() { return partner!=null; }
public int getIndex() { return index; }
public String getName() { return name; }
public Person getPartner() { return partner; }
public void setPartner(Person partner) { this.partner = partner; }
public boolean isBetterPartner(Person partner) {
return (this.partner==null) ||
(preference.indexOf(this.partner.getIndex()) >
preference.indexOf(partner.getIndex()));
}
public int getFirstPreference() {
if(preference.size()>0)
return preference.get(0);
else
return -1;
}
public boolean removeFirstPreference() {
if(preference.size()>0){
preference.remove(0);
return true;
} else {
return false;
}
}
public String toString() {
if (partner != null) {
return name+" (verheiratet mit "+partner.getName()+")";
}else{
return name+" (unverheiratet)";
}
}
}//end class Person

Was muss eigentlich geändert werden, um eine „männerfreundliche“
Lösung zu finden? Wie sieht diese aus? Warum endet der Algorithmus
immer? Warum sind die Partnerschaften stabil?
Für die vorgegebenen Daten sieht das „frauenfreundliche“ Ergebnis übrigens
wie folgt aus:
Romeo (verheiratet mit Trudi)
Bob (verheiratet mit Julia)
John (verheiratet mit Heidi)
Peter (verheiratet mit Anna)
Sie sollen für die Abgabe aber das folgende (komplizierter anmutende)
Problem lösen:
Nr Name Präferenzen
1 Arnold 1 5 7 6 4 2 10 9 8 3
2 Eros 5 2 1 9 7 6 10 8 3 4
3 Hansruedi 3 1 5 10 8 9 7 6 2 4
4 Robbie 6 2 1 5 9 7 3 10 8 4
5 Leonardo 5 3 6 2 8 1 7 4 9 10
6 Mick 10 2 6 4 3 8 9 5 1 7
7 Romeo 7 2 5 4 10 3 6 1 8 9
8 Bruce 8 3 6 5 1 4 7 2 9 10
9 Hugo 4 2 10 8 7 6 3 9 1 5
10 Kevin 5 1 9 8 7 6 10 4 2 3

Vielen Dank im Voraus
Gruß
Daniel

 

[André Uhres]

..lässt er sich von seinem jetzigen Partner scheiden und heiratet..

Das könnte man dann noch erweitern: was geschieht mit den Kindern, falls sie schon Kinder haben?

 

[norman]

"frauenfreundlich" heißt hier doch lediglich, dass in die präferenzliste der frau geschaut wird, welchen mann sie am liebsten heiraten will. der mann wird nicht gefragt.

für eine "männerfreundliche" lösung sollte daher der tausch einiger variablen genügen (m, f)..

 

[Daniel22]

Ja genau norman, so hab ich das auch verstanden! Weißt du schon wie ich das in java umsetzen könnte, weil ich nicht wirklich eine Idee habe was die Programmierung angeht

 

[André Uhres]

..Hab selbst schon ein wenig programmiert und komme nicht weiter ..

Zeig uns bitte deinen Ansatz.