Laden...

Gemeinsames Element von n Collections

Erstellt von the_lmich vor 16 Jahren Letzter Beitrag vor 16 Jahren 1.738 Views
the_lmich Themenstarter:in
248 Beiträge seit 2005
vor 16 Jahren
Gemeinsames Element von n Collections

Hallo,

ich benötige einen Algorithmus, der mir die gemeinsames Elemente von n Collections zurückliefert. Genauer benötige ich das erste gemeinsame Element von beliebig vielen Listen.

Kennt jemand von Euch vllt. eine fertige Implementierung im Framework? Nicht dass ich die Arbeit umsonst mache 😉

Danke,
🙂 Torsten

49.485 Beiträge seit 2005
vor 16 Jahren

Hallo the_lmich,

ich denke, dass es da nichts fertiges gibt.

Wie meinst du es genau? Das erste Element bezüglich welcher Collection? Oder das gemeinsame Element, dass in irgendeiner Collection einen Index hat, der kleiner (oder gleich) allen anderen Indices aller gemeinsamen Elemente alle Collections hat. Sind die Collections geordnet oder ungeordnet? Haben alle die gleiche Ordnung?

herbivore

the_lmich Themenstarter:in
248 Beiträge seit 2005
vor 16 Jahren

Hallo herbivore und danke für die Antwort,

ich suche alle Elemente, die gemeinsam in allen Listen vorkommen. Von diesen Elemente benötige ich dasjenige, welches ich zuerst finde, wenn ich die Liste von unten herauflaufe.

Bsp für zwei Listen:

Liste 1: a-b-c-d-e-f-g-h-i-j
Liste 2: k-l-c-n-o-p-q-r-h-t-u-v-w

Ich würde finden: h und c, benötige aber h. (In diesem Fall von rechts traversiert)

Grüße
🙂 Torsten

0
767 Beiträge seit 2005
vor 16 Jahren

für alle elemente in liste 2
liste1.Contains(x) aufrufen, und wenn true, das aktuelle element aus liste 2 returnen.

edit: ach moment, von rechts...

in dem fall musst du mit for() arbeiten, aber der schlüssel ist Contains()

loop:
btst #6,$bfe001
bne.s loop
rts

the_lmich Themenstarter:in
248 Beiträge seit 2005
vor 16 Jahren

Ja, nur bei n Collections ist das ja nicht grade perfomant 😦

49.485 Beiträge seit 2005
vor 16 Jahren

Hallo the_lmich,

richtig!

Was ich machen würde, hängt davon ab, wie ähnlich sich die Listen sind.

Wenn es viele gemeinsame Elemente gibt, würde ich mit das letzte Element der kürzesten Liste nehmen und bei allen anderen Listen von hinten durchlaufen, bis dieses Element gefunden wurde oder bis an den Punkt, wo feststeht, dass es nicht mehr kommen kann. Wenn das Element in allen Listen gefunden wurde, fertig. Wenn nicht, dann das gleiche für das vorige Element der kürzesten Liste. Natürlich beginnt die Suche in den anderen Listen an dem bisher erreichten Punkt.

Wenn es wenige gemeinsame Element gibt, dann würde ich quasi das gleiche machen, nur dass ich die anderen Listen nicht sequentiell, sondern per binärer Suche durchsuchen würde.

herbivore