Starthilfe Programm Partygaeste

Hallo erstmal,

versuche gerade ein Problem zu Loesen, aber leider finde ich keinen guten Ansatz. Vielleicht kann mir jemand eine Idee geben:
"Auf eine Feier sollen nur Leute eingeladen werden, die mindestens X der anderen Gaeste kennen. Gegeben ist eine Liste mit Bekanntschafften z.B.
Person 1 kennt Person 3
Person 1 kennt Person 5
Person 1 kennt Person 8
Person 2 kennt Person 3
etc.

Somit weiss ich wer wen kennt. Aber wie kann ich das als Programm umsetzen, welches mir die moeglichen Gaeste ausgibt.
Hoffe mein Problem ist verstaendlich, danke vorab fuer Hinweise.

Eine Kreuztabelle (2D-Feld))

#define ANZAHLPERONEN = 10;
char Kennen[ANZAHLPERONEN+1][ANZAHLPERONEN+1]= {{0}}; // oder short oder int, je nach bedarf.
/*
Person 1 kennt Person 3 -> Kennen[1][3] = 1;
Person 1 kennt Person 5 -> Kennen[1][5] = 1;
Person 1 kennt Person 8 -> Kennen[1][8] = 1;
Person 2 kennt Person 3 -> Kennen[2][3] = 1; 
*/

In Zeile bzw Spalte 0 kannst du dann die Summe abspeichern

Erstmal danke fuer die Antwort!
Also grundsaetzlich scheint mir dein Vorschlag gut zu sein um eine Bekannschaft festzuhalten. Muss wohl in zwei Felder der Tabelle nen Eintrag pro Bekanntschaft machen. Beispiel:
Person 1 kennt Person 5 --> Kennen[1][5]=1; Kennen[5][1]=1.
Somit kann ich recht einfach zaehlen wieviele Personen eine Person kennt.

Allerdings sehe ich noch nicht, wie ich jetzt feststellen kann ob eine Person genuegend potentielle Gaeste kennt um eingeladen zu werden. Es kann ja sein, dass jemand 5 Personen kennt, aber von den 5 Personen kennt jeder nur eine Person. Somit, wenn z.B. "midestanzahl der Personen die man kennen musss"=4, trotz 5 Bekannter keine Einladung verschickt werden darf.

Ok, gebe zu hoert sich etwas kompliziert an. Hoffe Jemand versteht was ich meine.

SeppJ

Wenn du die Tabelle hast, könntest solange Personen von der Gästeliste streichen, bis alle verbliebenen Personen mehr als drei Bekanntschaften haben. In jedem Schritt löscht du dazu jede Person mit zwei oder weniger verbliebenen Bekanntschaften.

Ist vermutlich nicht die effizienteste Methode (das Problem klingt nach etwas, wo ein Graphentheoretiker die sofort einen tollen Algorithmus nennen könnte, jedoch bin ich kein Graphentheoretiker), aber anschaulich, einfach implementierbar und zumindest nicht ganz dumm.

volkard

Reicht es nicht, einfach pro potentiellem Partygast seine Bekannstschaften zu zählen. Also eindimensionales Array und in O(n) beim Lesen für jede vorkommende Zahl ++ zu machen?

Jester

Ne, stell dir vor, du hast einen der alle kennt, die kennen sich aber alle untereinander nicht. Dann darfste niemand einladen, auch wenn der, der alle kennt vielversprechend aussah.

Der Begriff aus der Graphentheorie dazu ist der k-Core -- insofern hat SeppJ recht. Den kann man ausrechnen, indem man iterativ Knoten mit zu kleinem Grad entfernt. Das lässt sich mit etwas Geschick in O(n+m) Zeit implementieren, ist also optimal. Insofern brauchts dafür auch keinen schlauen Graphtheoretiker.

Vielen Dank fuer die Tipps.
Habe SeppJ's Ueberlegung verstanden und werde diese versuchen umzusetzen. k-Core nie gehoert, aber lese ich mir auch mal was an, vielleicht ists ja interessant fuer mich.
Euch allen nen schoenen Tag und danke nochmal.