Algorithmus zur Berechnung einer Vereinigungsmenge

[Metalgurke]

Hallo Zusammen,
ich zerbrechne mir gerade meinen Kopf über folgendes Problem.
Ich versuche das Problem erstmal so abstrakt wie möglich zu beschreiben. Wenn ihr später konkrete Lösungswege, evtl. mit Javascript beschreibt, wäre das super!

Problemstellung: Ich möchte einen Algorithmus programmieren der mir von n-vielen verschiedenen Intervallen, die Vereinigungsmenge wiedergibt.

Über Denkansätze wäre ich schon dankbar. Lösungwege sind natürlich auch herzlich willkommen :)

Danke und Gruß
Metalgurke

[Metalgurke]

Nachtrag:
Mir ist gerade ein Gedanke gekommen.
Ich bilde eine Schnittmengenmatrix und an Hand der Matrix schaue ich welche Intervale mit einander korrelieren. (1 steht für eine Korrelation, 0 für keine)

Bsp:

• a b c d
  a 1 0 0 1
  b 0 1 1 0
  c 0 1 1 0
  d 1 0 0 1

Jetzt sehe ich das Intervall 'a' mit 'd' eine Vereinigungsmenge bilden und 'b' mit 'c'.

Also kann ich doch sagen das a mit d vereint, ein zusammenhängendes Intervall bilden (b mit d ebenso). Oder bin ich jetzt völlig aufem Holzweg?

[Der Martin]

Hallo,

Ich bilde eine Schnittmengenmatrix

wie machst du das? Und wieso hilft dir das, wo du doch die Vereinigungsmenge (aka Obermenge) haben möchtest?

• a b c d
  a 1 0 0 1
  b 0 1 1 0
  c 0 1 1 0
  d 1 0 0 1
  Jetzt sehe ich das Intervall 'a' mit 'd' eine Vereinigungsmenge bilden und 'b' mit 'c'.

Ich kann dir nicht folgen.

Also kann ich doch sagen das a mit d vereint, ein zusammenhängendes Intervall bilden (b mit d ebenso). Oder bin ich jetzt völlig aufem Holzweg?

Ich glaube ja, bin mir aber nicht sicher.
Lass es mich anders illustrieren. Du sprichst von Intervallen. Ein Intervall ist definiert durch einen Startwert und einen Endwert. Wir nehmen hier vereinfachend an, dass Start- und Endwert noch zum Intervall zählen (obwohl es bei den gewählten Zahlenwerten unerheblich ist).

Gegeben seien die Intervalle A, B, C, D:
 A = [ 6, 10]
 B = [17, 22]
 C = [ 4,  8]
 D = [15, 18]

Die Vereinigungsmenge ist nun zunächst einmal die Menge aller vier Intervalle. Nicht zwangsläufig lückenlos! Die Aufgabe besteht nun eigentlich darin, die Intervalle zusammenzufassen, wo das möglich ist. Und das ist möglich, wenn sie sich überschneiden (ach, deshalb bist du auf die Schnittmenge gekommen). Und überschneiden tun sie sich dann, wenn der größere der beiden Startwerte kleiner oder gleich dem kleineren der beiden Endwerte ist (bitte am Zahlenstrahl veranschaulichen).

Im Beispiel erkennen wir, dass wir A und C zu *einem* Intervall zusammenfassen können, außerdem die Intervalle B und D, so dass wir die Ergebnismenge erhalten:

( A+C = [4, 10]; B+D = [15,22] )

Eine weitere Zusammenfassung ist nicht möglich, deine Ergebnismenge enthält zwei getrennte Intervalle. Generell musst du natürlich davon ausgehen, dass bei n Intervallen auch die Vereinigungsmenge immer noch aus n getrennten Intervallen besteht.

Oder geht es dir nur um das kleinste Intervall, das seinerseits A bis D enthält, also [4, 22]? Dann bräuchtest du ja nur den kleinsten Startwert und den größten Endwert der n Intervalle zu suchen.

Oder meinst du noch etwas anderes? Dann solltest du das besser erläutern.

So long,
 Martin

[Vinzenz Mai]

Hallo,

Ich glaube ja, bin mir aber nicht sicher.
Lass es mich anders illustrieren. Du sprichst von Intervallen. Ein Intervall ist definiert durch einen Startwert und einen Endwert. Wir nehmen hier vereinfachend an, dass Start- und Endwert noch zum Intervall zählen.

Grundsätzlich müssen sie sich noch nicht einmal überschneiden:

A = [5, 10)
B = [10, 14]

lassen sich zusammenfassen,

C = [15, 20)
D = (20, 24]

dagegen nicht.

Freundliche Grüße

Vinzenz

[Metalgurke]

Grundsätzlich müssen sie sich noch nicht einmal überschneiden:

A = [5, 10)
B = [10, 14]

arghhh ich Blindfisch, du hast natürlich recht. Dann kann ich mir meine tolle Schnittmengenmatrix-Idee auch an den Hut stecken. :) Danke dir für den Hinweis.

[Metalgurke]

Gegeben seien die Intervalle A, B, C, D:
A = [ 6, 10]
B = [17, 22]
C = [ 4,  8]
D = [15, 18]

....

Im Beispiel erkennen wir, dass wir A und C zu *einem* Intervall zusammenfassen können, außerdem die Intervalle B und D, so dass wir die Ergebnismenge erhalten:

( A+C = [4, 10]; B+D = [15,22] )

Jo, hatte mich etwas ungenau ausgedrück. Genau das meine ich :)

[Vinzenz Mai]

Hallo,

ich zerbrechne mir gerade meinen Kopf über folgendes Problem.
Ich versuche das Problem erstmal so abstrakt wie möglich zu beschreiben. Wenn ihr später konkrete Lösungswege, evtl. mit Javascript beschreibt, wäre das super!

Problemstellung: Ich möchte einen Algorithmus programmieren der mir von n-vielen verschiedenen Intervallen, die Vereinigungsmenge wiedergibt.

die Vereinigungsmenge besteht somit aus einer Anzahl von 1 bis n verschiedenen Intervallen, je nach Datenlage.

Eine Idee wäre es, die Vereinigungsmenge mit einem zu InsertSort vergleichbaren Verfahren zusammenzustellen, wobei nach Intervallanfang sortiert wäre (geht natürlich genauso auch absteigend nach Intervallende). Die Einfügeoperation muss so modifiziert werden, dass Intervalle zusammengefasst werden, falls nötig. Da in der Vereinigungsmenge nur disjunkte Intervalle vorliegen, sollten sowohl Einfügeposition als auch zusammenzufassenden Intervalle effizient zu finden sein. Ob das Verfahren insgesamt effizient ist, hängt unter anderem von dem Aufwand ab, der für die Einfügeoperation und das Zusammenfassen erforderlich ist.

Freundliche Grüße

Vinzenz

[Metalgurke]

Danke dir für die Infos und den Link. Werde mir das mal durchlesen.