3. Algorithmus gesucht

Algorithmus gesucht

  • L

    2 Ideen:

    1. Definiere eine Ordnung über deine Listen und pack die Listen der rechte Seite in eine TreeMap . Anschließend schaue mittels contains , ob eine Liste der linken Seite in der rechten Seite vorkommt. Laufzeit: O(n * log(n) * m)

    2. Berechne einen Hashwert für jede Liste und pack die Listen in eine HashMap . Anschließend schaue mittels contains , ob eine Liste der linken Seite in der rechten Seite vorkommt. Laufzeit je nach Anzahl der Kollisionen. Falls keine Kollisionen vorkommen, wohl sowas wie O(n * m).

    Edit: Das initiale Sortieren der Listen sollte natürlich bestehen bleiben.

    0
  • V

    ipsec schrieb:

    Nur eine fixe Idee: man bildet von jeder Liste jeweils die Summe und das Produkt aller enthaltenen Zahlen.

    life schrieb:

    2 Ideen:
    1. Definiere eine Ordnung über deine Listen und pack die Listen der rechte Seite in eine TreeMap . Anschließend schaue mittels contains , ob eine Liste der linken Seite in der rechten Seite vorkommt. Laufzeit: O(n * log(n) * m)

    2. Berechne einen Hashwert für jede Liste und pack die Listen in eine HashMap . Anschließend schaue mittels contains , ob eine Liste der linken Seite in der rechten Seite vorkommt. Laufzeit je nach Anzahl der Kollisionen. Falls keine Kollisionen vorkommen, wohl sowas wie O(n * m).

    Edit: Das initiale Sortieren der Listen sollte natürlich bestehen bleiben.

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

    0
  • V

    m2l schrieb:

    volkard schrieb:

    m2l schrieb:

    Liste mit möglichen ungleichen, map mit zahl zu liste -> aus Liste mit möglichen ungleichen streichen.

    m2l schrieb:

    Klar?

    Nein, habe den Plan nicht verstanden.

    Du machst eine Map mit allen Zahlen (Key) die in allen Listen (rechts) sind und Value sind diese Listen.

    Alle möglichen für Liste 1 (links) sind erst mal alle rechten.

    Liste 1 (links) durchgehen, erste Zahl in Map suchen, treffer -> Value Listen aus "alle möglichen" streichen. usw. bis "alle möglichen" leer (-> keine ungleiche -> Liste 2 (links) durchgehen) oder Liste 1 (links) durchgegangen (->Treffer in alle möglichen).

    Ich gehe davon aus, daß jede der überhaupt vorkommenden Zahlen in vielen Listen links und in vielen Listen rechts vorkommt. Dein Verfahren würde ausspucken, daß keine Zahl existiert, die in einer linken Liste aber in keiner rechten Liste vorkommt. Trotzdem kann es sein, daß eine linke Liste mit einer rechten Liste kein gemeinsames Element hat.

    0
  • R

    volkard schrieb:

    Bisher mache ich das so, daß ich alle Listen sortiere, dann alle n*(n-1)/2 (derzeit 8386560) Listenpaare vergleiche und pro Listenvergleich schlimmstenfalls ca 200 Integervergleiche brauche.

    Geht das auch schneller?

    vermutlich waere es schneller wenn du alle zahlen (sammt herkunft, ich meine sowas wie std::pair<int,CSourceList*> )in ein vector steckst, sortierst und dann nur in der range von zahlen die sich gleichen die listen in einer matrix gegenseitig ausmaskierst (kannst dir den matrix-bitcount ja noch seperate speichern damit du spaeter die kandidaten fixer findest).

    my2cent of my1min idea.

    0
  • V

    SeppJ schrieb:

    Alle Zahlen in den Listen durchgehen. Eine Zahlenliste erstellen in der die Listen stehen in der die Zahlen vorkommen. Die Zahlenliste durchgehen und gucken welche Listen immer nur einzeln in den Listenlisten vorkommen.

    Ich hoffe das war jetzt nicht zu kompliziert beschrieben 😃 .

    Wahrscheinlich nicht zu kompliziert. Aber mir scheint, es trifft dei Frage nicht.

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

    Deine Zwischenliste:

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

    Die Zahlenliste durchgehen und gucken welche Listen immer nur einzeln in den Listenlisten vorkommen.

    Keine. 😞

    0
  • J

    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.

    Sind die vorkommenden Zahlen beliebig groß? Wenn nicht, kannst Du vielleicht Listen invertieren?

    0
  • Mod

    volkard schrieb:

    SeppJ schrieb:

    Alle Zahlen in den Listen durchgehen. Eine Zahlenliste erstellen in der die Listen stehen in der die Zahlen vorkommen. Die Zahlenliste durchgehen und gucken welche Listen immer nur einzeln in den Listenlisten vorkommen.

    Ich hoffe das war jetzt nicht zu kompliziert beschrieben 😃 .

    Wahrscheinlich nicht zu kompliziert. Aber mir scheint, es trifft dei Frage nicht.

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

    Deine Zwischenliste:

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

    Die Zahlenliste durchgehen und gucken welche Listen immer nur einzeln in den Listenlisten vorkommen.

    Keine. 😞

    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?

    0
  • V

    rapso schrieb:

    vermutlich waere es schneller wenn du alle zahlen (sammt herkunft, ich meine sowas wie std::pair<int,CSourceList*> )in ein vector steckst, sortierst

    Moment, ich probiers mal...

    Ausgangsdaten:

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

    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

    und dann nur in der range von zahlen die sich gleichen

    Jede Zahl wird links und rechts vorhanden sein.

    die listen in einer matrix gegenseitig ausmaskierst (kannst dir den matrix-bitcount ja noch seperate speichern damit du spaeter die kandidaten fixer findest).

    Die fülle ich zuerst mit 1

    def
a111
b111
c111

    und mache dann 0 überall, wo ein Paar aus den Zwischenlisten ist.

    Die Paare:

    ae af ce cf
bd be cd ce
ad
be bf
ad af bd bf cd cf

    Nach dem Streichen:

    def
a000
b000
c000

    Aha. Nur noch Nullen.

    Könnte glatt klappen.

    Mal den Gewinn betrachten...

    Ausgangsdaten:

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

    //Einfaches Umschreiben. O(2*n*m)

    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

    und dann nur in der range von zahlen die sich gleichen

    Jede Zahl wird links und rechts vorhanden sein.

    die listen in einer matrix gegenseitig ausmaskierst (kannst dir den matrix-bitcount ja noch seperate speichern damit du spaeter die kandidaten fixer findest).

    Die fülle ich zuerst mit 1
    //Billig

    def
a111
b111
c111

    und mache dann 0 überall, wo ein Paar aus den Zwischenlisten ist.

    //Ups, es gibt aber viele Paare. Mir scheint, das spart keine Arbeit,
    //hat sie nur umgeschichtet.
    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.

    Wenn m größer wird, wächst meiner sublinear mit m (weil die Zahlen so dicht sind) und Deiner quadratisch mit der Anzahl verschiedener Zahlen und das sehr langsame Wachsen der Anzahl verschiedener Zahlen gleicht das wieder aus.

    Ein Teufelskreis. Nette Idee.
    Aber am Ausmaskieren der vielen Paare aus der Matrix hapert's. Ich sehe auch keinen kräftigen Schub durch bittwiddeling.

    0
  • ?

    volkard schrieb:

    m2l schrieb:

    volkard schrieb:

    m2l schrieb:

    Liste mit möglichen ungleichen, map mit zahl zu liste -> aus Liste mit möglichen ungleichen streichen.

    m2l schrieb:

    Klar?

    Nein, habe den Plan nicht verstanden.

    Du machst eine Map mit allen Zahlen (Key) die in allen Listen (rechts) sind und Value sind diese Listen.

    Alle möglichen für Liste 1 (links) sind erst mal alle rechten.

    Liste 1 (links) durchgehen, erste Zahl in Map suchen, treffer -> Value Listen aus "alle möglichen" streichen. usw. bis "alle möglichen" leer (-> keine ungleiche -> Liste 2 (links) durchgehen) oder Liste 1 (links) durchgegangen (->Treffer in alle möglichen).

    Ich gehe davon aus, daß jede der überhaupt vorkommenden Zahlen in vielen Listen links und in vielen Listen rechts vorkommt. Dein Verfahren würde ausspucken, daß keine Zahl existiert, die in einer linken Liste aber in keiner rechten Liste vorkommt. Trotzdem kann es sein, daß eine linke Liste mit einer rechten Liste kein gemeinsames Element hat.

    #include <iostream>
#include <vector>
#include <map>
#include <set>

int main()
{
	std::vector<std::vector<int>> l;
    std::vector<int> l1;
	l1.push_back(28);
	l1.push_back(9);
	l1.push_back(210);
	l1.push_back(211);
	l.push_back(l1);
	l1.clear();
	l1.push_back(2);
	l1.push_back(8);
	l1.push_back(6);
	l1.push_back(16);
	l.push_back(l1);

	std::vector<std::vector<int>> r;
    std::vector<int> r1;
	r1.push_back(8);
	r1.push_back(18);
	r1.push_back(6);
	r1.push_back(16);
	r.push_back(r1);
	r1.clear();
	r1.push_back(9);
	r1.push_back(15);
	r1.push_back(6);
	r1.push_back(10);
	r.push_back(r1);

	std::multimap<int,int> m;
	for(size_t i=0;i<l.size();i++)
	{
		for(size_t j=0;j<l[i].size();j++)
		{
			m.insert(std::make_pair(l[i][j],i));
		}
	}

	for(size_t i=0;i<r.size();i++)
	{
		std::set<int> possible;
		for(size_t k=0;k<l.size();k++)
		{
			possible.insert(k);
		}
		for(size_t j=0;j<r[i].size();j++)
		{
			std::multimap<int,int>::iterator iter = m.find(r[i][j]);
			while( iter != m.end() && iter->first == r[i][j])
			{
				possible.erase(iter->second);
				++iter;
			}
			if(possible.size() == 0)
			{
				break;
			}
		}
		if(possible.size() != 0)
		{
			for(size_t j=0;j<r[i].size();j++)
			{
				std::cout<<"r"<<i<<":";
				std::cout<<r[i][j];
				for(std::set<int>::iterator iter = possible.begin();iter!=possible.end(); ++iter)
				{
					std::cout<<" l"<<*iter<<":";;
					std::cout<<l[*iter][j];
				}
				std::cout<<"\n";
			}
		}
	}

}

    Mach mal ein Beispiel was du meinst.

    0
  • V

    SeppJ schrieb:

    volkard schrieb:

    SeppJ schrieb:

    Alle Zahlen in den Listen durchgehen. Eine Zahlenliste erstellen in der die Listen stehen in der die Zahlen vorkommen. Die Zahlenliste durchgehen und gucken welche Listen immer nur einzeln in den Listenlisten vorkommen.

    Ich hoffe das war jetzt nicht zu kompliziert beschrieben 😃 .

    Wahrscheinlich nicht zu kompliziert. Aber mir scheint, es trifft dei Frage nicht.

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

    Deine Zwischenliste:

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

    Die Zahlenliste durchgehen und gucken welche Listen immer nur einzeln in den Listenlisten vorkommen.

    Keine. 😞

    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.

    0
  • V

    Jester 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.

    Sind die vorkommenden Zahlen beliebig groß? Wenn nicht, kannst Du vielleicht Listen invertieren?

    Oh, das ist aber eine feine Idee.
    Leider sind die Zahlen auch groß bis viele Milliarden.

    0
  • V

    m2l schrieb:

    ...

    Dein Code klappt bei den ersten beiden per Hand eingetippten Beispielen. Ich versuche mal, zu verstehen, was er macht...

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

    Erster verschachtelte Schleife: Umschreiben von L.
    //billig mit 2*n*m

    L:
    1:ac
    2:ab
    3:c
    4:b
    6:abc

    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. 😞

    0
  • K

    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.

    0
  • L

    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. 😞

    0
  • V

    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

    0
  • M

    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.

    0
  • V

    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).

    0
  • Mod

    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).

    0
  • K

    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 .

    0
  • ?

    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.

    0
Anmelden zum Antworten