AlgoDat

Re(6): AlgoDat

Darth Maul — Fri, 13 Feb 2004 12:19:37 GMT

So, habs ausprobiert. Funktioniert tadellos. Danke nochmals.

mfg
Maul

Re(2): AlgoDat

komplexler — Thu, 12 Feb 2004 22:13:31 GMT

also dann eine multimenge!

Re(2): AlgoDat

Darth Maul — Thu, 12 Feb 2004 21:00:58 GMT

Danke, darüber wurde ich bereits aufgeklärt
"Unsortierte Listen" wäre wohl der richtige Ausdruck gewesen.

mfg
Maul

Re: AlgoDat

promillo — Thu, 12 Feb 2004 20:38:45 GMT

ich möchte nur darauf hinweisen das in deinem beispiel A sowie B keine mengen im klassischen sinn sind. es darf jedes element jeweils nur einmal enthalten sein!

Re(6): AlgoDat

m3t4tr0n — Thu, 12 Feb 2004 17:36:53 GMT

Weiß ich nicht *duck*

Ein Kollege meinte, schneller gehts nicht.

Und der ist nicht so eine kleiner Anfänger wie ich

Re(5): AlgoDat

komplexler — Thu, 12 Feb 2004 17:26:21 GMT

Aber die 16 Vergleiche sind trotzdem linear bezüglich B. somit habe ich sicher n log n.
Wie ist denn nach deiner Lösung die Laufzeit, diese Liste zu erstellen?

Re(4): AlgoDat

m3t4tr0n — Thu, 12 Feb 2004 17:17:39 GMT

Und was machst du in dem Fall:

A:= {1,2}
B:= {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2}

Da bist laufzeitmäßig genauso im Sand. 16 Vergleiche für 2 Elemente.

In einer Liste hättest gespeichert:

A:
1 - 1
2 - 1

B:
1 - 16
2 - 1 => nach 2 Vergleichen, weiß man, daß A ? B.

Du kannst also einfach die Listen durchlaufen und mußt anschließend nur so viele Vergleiche machen, wie es wertverschiedene Elemente in der Menge gibt.

Re(3): AlgoDat

komplexler — Thu, 12 Feb 2004 16:35:17 GMT

Naja wenns in (n log n) sortiert wird, kann man das ja linearer Laufzeit überprüfen oder?

Ich nehme das erste Element aus A, schaue das erste Element in B ob es enthalten ist. Wenn ja, weiter, wenn nein, gehe ich in B solange weiter, bis die Zahl größer ist als in A. Wenn nichts gefunden, ist das Ergebnis negativ. Danach gehe ich in A eins weiter, überprüfe es es wieder aus B. Ich brauche nie zurückgehen, da es ja geordnet ist.

und die Laufzeit sollte dann vom Sortieren bestimmt sein ( n log n )

Re(2): AlgoDat

m3t4tr0n — Thu, 12 Feb 2004 16:08:48 GMT

Was würde das ändern?

Re: AlgoDat

komplexler — Thu, 12 Feb 2004 14:43:32 GMT

schneller würde es vielleicht gehen, wenn man die Elemente vorher sortiert (n log n) und das dann überprüfst...

Re(5): AlgoDat

m3t4tr0n — Thu, 12 Feb 2004 13:40:09 GMT

public class menge{
     public static void main (String args[]){
          int[] menge1 = {1,1,1,2,2,3,4,5,6};
          int[] menge2 = {1,1,2,2,3,4,5,5,6};

//Hilfsarray der Länge von menge2 mit false initialisiert
          boolean[] hilfsarray = new boolean[menge2.length];
          for (int z=0;z<menge2.length;z++){
               hilfsarray[z]=false;
          }

//Counter zählt die Anzahl von "ture" im Hilfsarray
          int counter=0;

//Vergleich der Elemente - bei Übereinstimmung, Weitersprung zum nächsten Index
          for (int x=0;x<menge1.length;x++){
               for (int y=0;y

Re(4): AlgoDat

Darth Maul — Thu, 12 Feb 2004 13:00:08 GMT

Die Laufzeit ist nicht wichtig. Ich habe ohnehin nur kleine Listen, also kann es durchaus quadratisch bleiben.

mfg
Maul

Re(3): AlgoDat

m3t4tr0n — Thu, 12 Feb 2004 12:53:18 GMT

Ist dann zwar quadratisch von der Laufzeit her, aber linear wüßt ich nicht wie ichs ausführen sollte:

Durchlaufe die größere Menge, erstelle eine Liste davon, zähle gleiche Elemente.

Danach vergleichst du noch die Menge der gleichen Elemente damit kommt dabei ein Wert <0 heraus oder m te der Liste ein neues Element hinzugef gt werden so ist die Menge nicht enthalten in also mal mal Abziehen der Anzahl von Vorkommnissen in der zu vergl Menge mal mal/> 1
3 - 1 mal - 1 mal => 0
4 - 2 mal - 3 mal => -1 => Wert kleiner 0, die Menge ist nicht enthalten
5 - 1 mal - 1 mal => 0
6 müßte eingefügt werden, also ebenfalls ein Zeichen, daß die Menge nicht enthalten ist.

Frag mich aber nicht nach der genauen Syntax.

Re(2): AlgoDat

Darth Maul — Thu, 12 Feb 2004 11:39:06 GMT

Ja, so könnts gehen. Werd ich heut abend mal ausprobieren.

Danke,
Maul

Re(4): AlgoDat

m3t4tr0n — Thu, 12 Feb 2004 10:19:13 GMT

Und i in der ersten statt y Sorry, Copy&Paste ist zu verleitend

Re(3): AlgoDat

m3t4tr0n — Thu, 12 Feb 2004 10:18:30 GMT

Sollte natürlich menge2 in der zweiten for-Schleife heißen.

Re(2): AlgoDat

m3t4tr0n — Thu, 12 Feb 2004 10:11:00 GMT

for (int i=0; y<menge1.length;i++;)
    for (int y=0;y<menge1.length;y++;)
       if (menge1[i]==menge2[y] && !hilfsarray[y])
       hilfsarray[y]=true;

Am Ende vergleichst du noch die Anzahl von true im Hilfsarray mit menge1.length, wenn die gleich sind, ist die menge1 in menge2 enthalten.

Ich gebe keine Funktionsgarantie, bin selber blutiger Anfänger.

Re: AlgoDat

m3t4tr0n — Thu, 12 Feb 2004 10:02:12 GMT

Eine Menge enthält normal zwar keine Elemente doppelt, aber:

Boolean Hilfsarray erstellen in der Größe der zweiten Menge. Alle Stellen mit false initialisieren. Wenn du an einem Index dein Element gefunden hast, einfach im Hilfsarray die Stelle auf true setzen und dann entsprechend bei der Suche als Bedingung mit einbinden.

AlgoDat

Darth Maul — Thu, 12 Feb 2004 09:42:11 GMT

Ich habe Probleme bei folgendem Algorithmus (Sprache ist egal):

Gegeben: Menge A, Menge B
Gesucht: Ist A in B enthalten?

Probleme gibts, wenn A oder B doppelte Elemente enthalten, also so was in der Art:

A = {2,2,3,1,4}
B = {2,3,3,3,4,5,1,4,8,4,1,11,10}

In diesem Fall ist A wegen der doppelten 2 nicht in B enthalten. Doch wie krieg ich das in einen netten Algorithmus verpackt?

mfg
Maul