Algorithmus gesucht

life

volkard schrieb:

Ich will nicht herausfinden, ob zwei der Listen alle Elemente gleich haben. Ich will herausfinden, ob zwei der Listen kein gleiches Element haben.

Ups. Dann fällt mir aber leider auch spontan keine Möglichkeit ein, die Laufzeit unter O(n^2*m) zu drücken.

volkard

life schrieb:

volkard schrieb:

Ich will nicht herausfinden, ob zwei der Listen alle Elemente gleich haben. Ich will herausfinden, ob zwei der Listen kein gleiches Element haben.

Ups. Dann fällt mir aber leider auch spontan keine Möglichkeit ein, die Laufzeit unter O(n^2*m) zu drücken.

Smiley-Strichliste bisher (ohne Quotes und Sigs):
: I
: IIII
: I

Michael E.

volkard schrieb:

Gegenbeispiel:

a[1,2,6]   d[3,4,5] 
b[2,4,6]   e[1,2,5] 
c[1,3,6]   f[1,5,6]

Deine Zwischenliste:

1:a,c,e,f
2:a,b,e
3:c,d
4:b,d
5:d,e,f
6:a,b,c,f

Auch keine.

Ich weiß nicht, ob du oder ich SeppJ richtig verstanden hat. Ich verstehe ihn Folgendermaßen:

a -> bcdef
b -> acdef
c -> abdef
d -> abcef
e -> abcdf
f -> abcde

1. acef streicht mögliche Kandidaten in den jeweiligen Listen:
a -> bd
b -> acdef
c -> bd
d -> abcef
e -> bd
f -> bd

2. abe:
a -> d
b -> cdf
c -> bd
d -> abcef
e -> d
f -> bd

3. cd:
a -> d
b -> cdf
c -> b
d -> abef
e -> d
f -> bd

4. bd:
a -> d
b -> cf
c -> b
d -> aef
e -> d
f -> bd

5. def:
a -> d
b -> cf
c -> b
d -> a
e -> 
f -> b

6. abcf:
a -> d
b -> 
c -> 
d -> a
e -> 
f ->

Also sind a und d disjunkt.

volkard

knivil schrieb:

Keine Ahnung, ob das schon genannt wurde: Iteriere ueber alle Zahlen der "linken" Haelfte und speichere sie in einer Hashtabelle mit der Information, in welchen Listen diese Zahl vorkommt. Fuer die rechte Haelfte nimmst du dir jede Liste vor und schaust fuer jede enthaltene Zahl, in welcher Liste der "linken" Haelfte sie enthalten ist. Wenn fuer alles Hashtabellen verwendet werden, dann sollte diese Datenstruktur die Laufzeit auf O(z) druecken, wobei z die Anzahl der Zahlen ist.

Ist wohl das von 02 Aug 2010 12:25?
Das wäre dann meiner (hoffentlich richtigen) Abschätzung nach O(n^2*m).

SeppJ

volkard schrieb:

SeppJ schrieb:

Ist das nicht die Frage? Es gibt hier ja keine Listen ohne gemeinsames Element und genau das kam raus.

Oder habe ich die Frage falsch verstanden?

Hast die Frage richtig verstanden.

Gegenbeispiel:
a[1,2,6]   d[3,4,5] 
b[2,4,6]   e[1,2,5] 
c[1,3,6]   f[1,5,6]
Deine Zwischenliste:
1:a,c,e,f
2:a,b,e
3:c,d
4:b,d
5:d,e,f
6:a,b,c,f
Auch keine.

Ok, das kann ich korrigieren:
Man suche die Listen die niemals mit einer Liste aus der anderen Hälfte zusammen auftauchen.

Mögliche Kombinationen bei diesem Beispiel: (a,d), (a,e), (a,f), (b,d), (b,e), (b,f), (c,d), (c,e), (c,f).
Nach 1 bleiben: (a,d), (b,d), (b,e), (b,f), (c,d)
Nach 2 bleiben: (a,d), (b,d), (b,f), (c,d)
Nach 3 bleiben: (a,d), (b,d), (b,f)
Nach 4 bleiben: (a,d), (b,f)
Nach 5 bleiben: (a,d), (b,f)
Nach 6 bleiben: (a,d)

Jedoch wird es schon komplizierter, alle Tupel statt aller Einzellisten durchzugehen. Das gibt uns nämlich einen weiteren Faktor n, womit wir wieder bei O(n^2*m) sind . Außerdem ist es so nur eine andere Formulierung von m2ls Vorschlag (wenn ich diesen richtig verstanden habe).

knivil

Bei der jetzigen Darstellung wirst du wohl jede Liste mit jeder anderen vergleichen muessen. Wie sieht denn das uebergeordnete Problem aus? Es scheint eine Variation von http://en.wikipedia.org/wiki/Exact_cover zu sein, nur ohne "excat". Dafuer gibt es z.B. http://en.wikipedia.org/wiki/Dancing_Links .

volkard schrieb:

für alle rechten Listen //n-mal
  possible=alleNamenVonLinks=[a,b,c] //billig
  Liste (zb d[3,4,5]) nehmen und die passenden Values (hier [c,b]) aus possible wegstreichen
  //m Nachgucker zu O(1) bei Hashtable 
  //und da jede Zahl in fast jeder Liste ist, pro Nachgucker n Streichungen
  Wenn was übrig bleibt 
    Das ist ein Fund.

Macht O(n*n*m)
Das hatte ich Anfangs schon, nur einfacher zu implementieren.

Aber m Nachgucker mit n Streichungen ist doch relativ unrealistisch, weil es insgesamt nur n Streichungen gibt, also wäre possible schnell leer.

volkard

Michael E. schrieb:

Ich weiß nicht, ob du oder ich SeppJ richtig verstanden hat. Ich verstehe ihn Folgendermaßen:

a -> bcdef
b -> acdef
c -> abdef
d -> abcef
e -> abcdf
f -> abcde

1. acef streicht mögliche Kandidaten in den jeweiligen Listen:
a -> bd
b -> acdef
c -> bd
d -> abcef
e -> bd
f -> bd

2. abe:
a -> d
b -> cdf
c -> bd
d -> abcef
e -> d
f -> bd

3. cd:
a -> d
b -> cdf
c -> b
d -> abef
e -> d
f -> bd

4. bd:
a -> d
b -> cf
c -> b
d -> aef
e -> d
f -> bd

5. def:
a -> d
b -> cf
c -> b
d -> a
e -> 
f -> b

6. abcf:
a -> d
b -> 
c -> 
d -> a
e -> 
f ->

Also sind a und d disjunkt.

Dann vestehst Du ihn richtig. Den Plan verstehe ich. Überzeugend einfach.

Läßt sich sogar ein klein wenig tunen, wenn man statt

a -> bcdef
b -> acdef
c -> abdef
d -> abcef
e -> abcdf
f -> abcde

nur

a -> def
b -> def
c -> def
d -> abc
e -> abc
f -> abc

speichert.

Oder gar nur

def
a111
b111
c111

1. acef streicht mögliche Kandidaten in den jeweiligen Listen:

Also a streicht cef, c streicht aef, e streicht acf, f streicht ace. Hier ist ein O(n^2) drin. Und das pro vorkommender Zahl.

Damit sind wir bei 02 Aug 2010 11:59

Nochmal mir ein wenig Klarheit über die Zeit machen...

Ausgangslage:
a[1,2,6]   d[3,4,5] 
b[2,4,6]   e[1,2,5] 
c[1,3,6]   f[1,5,6] 
Hier stehen 2*n*m Zahlen. 

Umschichten

Zwischenlisten:
1:ac ef
2:ab e
3:c d
4:b d
5:d ef
6:abc f 
Hier stehen jetzt 2*n*m Buchstaben. Sie v die Anzahl der vorkommenden Zahlen. 
Dann stehen in jeder Zeile 2*n*m/v Zahlen. 
Davon links n*m/v und rechts n*m/v

Tabelle:
 def
a111
b111
c111

1. ac ef streicht mögliche Kandidaten in den jeweiligen Listen:
(n*m/v)*(n*m/v) Streichungen
a -> bd
b -> acdef
c -> bd
d -> abcef
e -> bd
f -> bd

2. usw.

Macht 
v*(n*m/v)*(n*m/v) Streichungen
=
n^2*m^2/v
=
n^2*m * m/v

Und ich hatte 
n^2*m

Ich fürchte, m wächst schneller als v. Die Version ist wohl sogar für kleine Listen schneller, 
wird aber später langsamer. :(

volkard

m2l schrieb:

volkard schrieb:
für alle rechten Listen //n-mal
  possible=alleNamenVonLinks=[a,b,c] //billig
  Liste (zb d[3,4,5]) nehmen und die passenden Values (hier [c,b]) aus possible wegstreichen
  //m Nachgucker zu O(1) bei Hashtable 
  //und da jede Zahl in fast jeder Liste ist, pro Nachgucker n Streichungen
  Wenn was übrig bleibt 
    Das ist ein Fund.
Macht O(n*n*m)
Das hatte ich Anfangs schon, nur einfacher zu implementieren.
Aber m Nachgucker mit n Streichungen ist doch relativ unrealistisch, weil es insgesamt nur n Streichungen gibt, also wäre possible schnell leer.

Ja, aber das ist, fürchte ich, das gleiche Argument, das beim Ursprungsalgo auch zieht.
Hier: Sobald possible ganz leer ist, kann ich frühzeitig aus dieser Schleife raus. Das passiert schlimmstenfalls erst ganz zum Schluß. Aber normalerweise schon viel früher, gerne schon in den ersten 10%.
Dort: Sobald zwei Listen einen Gleichen haben, kann ich frühzeitig aussteigen. Das passiert schlimmstenfalls erst ganz zum Schluß. Aber normalerweise schon viel früher, gerne schon in den ersten 10%.

volkard

knivil schrieb:

Bei der jetzigen Darstellung wirst du wohl jede Liste mit jeder anderen vergleichen muessen.

Das Erstellen der Listen dauert sehr lange und geschieht durch mich. Ich kann sie problemlos als doppelt verkettete Listen, als Bäume, als Hashtables oder was auch immer darstellen. Auch Dancing_Links, wenn das passen würde.

knivil schrieb:

Wie sieht denn das uebergeordnete Problem aus? Es scheint eine Variation von http://en.wikipedia.org/wiki/Exact_cover zu sein, nur ohne "excat". Dafuer gibt es z.B. http://en.wikipedia.org/wiki/Dancing_Links .

Tut nichts zur Sache, glaube ich. Das würde nur die Diskussion umwerfen. Vor dem ersten edit suchte ich nach dem Maximum der Minima aller möglichen Links-Rechts-Schnittmengen, aber die neue Frage fühlt sich schneller und einfacher an und läßt sich nachher überführen.

Ich habe vorher Zeit um Listen zum Beispiel in anderes Format zu bringen. Ich habe nachher Zeit zum Auswerten. Entführten Algorithmen gebe ich auch eine Chance, wenn die Übersetzung nicht ganz plem ist. Angenommen, SeppJs allgemeines Verfahren, aus n Mengen zwei disjunkte Mengen herauszufinden, wäre prinzipiell schnell. Dann würde ich einfach zwei Zahlen dl und dr basteln, die noch nirgends vorkommnen, allen linken Listen dl zufügen, allen rechten Listen dr zufügen und das Verfahren abfeuern. Falls es disjunkte Mengen findet, sind sie auomatisch auch auf verschiedenen Seiten.

Damit ist die Ausweichfrage aufgemacht worden: Wie findet man n Mengen zu m Elementen zwei disjunkte Mengen raus? Und braucht man O(n^2*m) Zeit? Das hat zwar weniger Einschränkungen als die Ausgangfrage und ist damit potenziell lahmer, aber supi googlebar, was ich jetzt mal machen werde.

volkard schrieb:

...
Zwischenlisten:

1:a,c         1:e,f 
2:b,c         2:d,e 
4:a           4:d 
5:b           5:e,f 
6:a,b,c       6:d,f

ich meinte das eher als eine liste, in etwa

1:a,c,e,f 
2:b,c,d,e 
4:a,d 
5:b,e,f 
6:a,b,c,d,f

bzw

1:a
1:c
1:e
1:f 
2:b
2:c
2:d
2:e 
4:a
4:d 
5:b
5:e
5:f 
6:a
6:b
6:c
6:d
6:f

aber ich glaube am resultat aendert es nicht allzuviel.

Bei ungefähr 20000 Zahlen kommen auf jede Liste 20000/4096=50 Zahlen
und das macht 2500 Paare und das *20000 = 50Mio.
Im Gegensatz zu am Anfang ca 80Mio schnelleren Operationen kein Gewinn.

ich wuste nicht welche range "m" bei dir hat, ich haette gedacht es gibt wenig ueberlappungen und dann waere es ein sehr sparsames ueber-ein-array-gehen und nur wirklich die konflicktstellen auszumaskieren.

btw. pro zeile der matrix ein counter als ++

SeppJ

In welchem Bereich liegen die Zahlen eigentlich?

Falls es eine bekannte Obergrenze gibt und diese nicht zu groß ist, könnte man für jede Liste ein Bitset anlegen und diese dann verUNDen.

volkard

SeppJ schrieb:

In welchem Bereich liegen die Zahlen eigentlich?
Falls es eine bekannte Obergrenze gibt und diese nicht zu groß ist, könnte man für jede Liste ein Bitset anlegen und diese dann verUNDen.

Ich rechne so mit 20000, kann mir kaum mehr als 30000 vorstellen, als Länge der Bitsets. Da klingt std::set_intersection schon lecker.

SeppJ

volkard schrieb:

SeppJ schrieb:

In welchem Bereich liegen die Zahlen eigentlich?
Falls es eine bekannte Obergrenze gibt und diese nicht zu groß ist, könnte man für jede Liste ein Bitset anlegen und diese dann verUNDen.

Ich rechne so mit 20000, kann mir kaum mehr als 30000 vorstellen, als Länge der Bitsets. Da klingt std::set_intersection schon lecker.

Ok, hatte zwar auf so etwas wie 128 als Obergrenze gehofft, aber 30000 geht ja eigentlich auch noch.

Doch, oh weh! Es sind n*m mäßig teure Operationen zum Berechnen der Sets und ((n/2)^2 * Obergrenze) ziemlich billige Vergleichsoperationen (wobei man hiervon sehr viele einsparen kann durch frühzeitiges Abbrechen). Klingt so betrachtet eigentlich nicht ganz so gut wie vor einer Stunde als ich die Idee hatte.

volkard

SeppJ schrieb:

Doch, oh weh! Es sind n*m mäßig teure Operationen zum Berechnen der Sets und ((n/2)^2 * Obergrenze) ziemlich billige Vergleichsoperationen (wobei man hiervon sehr viele einsparen kann durch frühzeitiges Abbrechen). Klingt so betrachtet eigentlich nicht ganz so gut wie vor einer Stunde als ich die Idee hatte.

Die Vergleichsoperationen mit 20000 langen Bitsets ist eben nicht soo billig. Obwohl, 20000/64=313 Verglichen mit der Alternative http://www.cplusplus.com/reference/algorithm/set_intersection/
Es wäre hier nicht von Bedeutung. Das miese ((n/2)^2) würde ich gerne tot haben.

SeppJ

Man müsste irgendeine Vergleichsoperation definieren, die komplett disjunkte Mengen als gleich ansieht. Dann könnte man mit Sortieralgorithmen auf n*log(n) als Vorfaktor kommen, indem man die Listen nach ihrer Ungleichheit sortiert. Das Problem ist, dass man dazu auch noch strenge schwache Ordnung braucht. Und da hakt es bei mir. Vermutlich geht das gar nicht. Ich werde nochmal ein bisschen drüber nachdenken, vielleicht gibt es ja ein geniales Vergleichkriterium, welches alles erfüllt oder ein einsichtiges Argument, warum es so etwas nicht geben kann.

edit: Ok, das einleuchtende Gegenargument ist natürlich, dass bei einer solchen Ordnung A<A gelten würde, aber auch A>A.
Und wenn man nach Ähnlichkeit sortiert, kommst man auch schnell auf Gegenbeispiele.

mazal

Idee:

Annahme jede Liste liegt sortiert vor.

Du hast die linken Listen

L1 a_11, a_12, .. a_1m
..
Ln a_n1, a_n2, ...a_nm

verkette die linken Listen zu einem "String"

$ a_11 .. a_1m $ a_21 .. a_2m $ .. $ a_n1 .. a_nm $

$ ist ein Trenner der in keiner Liste vorkommt

Bis hier hin O( n*m), wenn ich annehme, dass Sortieren kostenlos ist.

Dann erstellst du ein Suffix-Array (dafür gibt es Linearzeit-Algorithmen)

Dann gehst du die rechen Listen durch baust dir einen String

$ a_i1 .. a_im $

Weil die Listen sortiert sind sehen sie falls sie gleiche Elemente enthalten in Stringform gleich aus.

Suchen mithilfe des Suffix-Arrays

kostet O( log (n*m))

Suchphase insgesammt also O ( n*( log (n*m)))

Damit, wenn ich mich alles täuscht O( n*m)

knivil

Ich hab's nicht verstanden ...

volkard

mazal schrieb:

Suffix-Array

Das klingt gut.

volkard

knivil schrieb:

Ich hab's nicht verstanden ...

Ich glaube, ich hab's.
Aus der Ausgangsaufgabe

a[1,2,6]   d[3,4,5] 
b[2,4,6]   e[1,2,5] 
c[1,3,6]   f[1,5,6]

"Sind hier ein linker und ein rechter disjunkt?", baue ich die neue Aufgabe

"Sind alle Strings 3450, 1250 und 1560 im String 126024601360 enthalten?".
Und kann deswegen auf ein reichhaltiges Angebot von Algorithmen zur Stringsuche zugreifen. http://en.wikipedia.org/wiki/String_searching_algorithm

Ähm, dann sehe ich doch nur, ob ein linker und ein rechter gleich sind? Das wollte ich gar nicht.
Verwirrt bin.