Verteilungsproblem

[ThunderZone]

Hi,

ich sitze gerade vor einem Algoproblem, welches man möglichst effizient in Java lösen soll. (Ich weiß nicht, ob ich hier richtig bin, vllt könnte man mich auch wo anders hin verweisen...)

Ich hab bis jetzt zwei Lösungsansätze bei denen ich zum einen nicht weiß, welcher effizienter ist und mir relativ sicher bin, dass das viel geschickter gehen müsste...

Also hier erstmal das Problem:

Man hat n verschiedene Elemente (sind in einem Object Array gespeichert) und diese soll man auf n/3 Buckets verteilen, wobei in jedes Bucket maximal 4 Elemente reinpassen. Deswetieren passen die Elemente in nur jeweils 2 Buckets rein.

Habt ihr eine Idee, wie man das möglichst effizient machen kann? Damti ihr seht, dass ich mir acuh schon Gedanken gemacht habe:

Ich habe mir überlegt, dass man ganz naiv immer ein Element nach dem anderen einfügen kann, wobei man immer den Bucket auffüllt, welcher noch nicht so viele Elemente besitzt. Sobald für ein Element beide zur Auswahl stehenden Buckets voll wären, schaut man sich im Prinzip wie bei der der Breitensuche die anderen Elemente in den Buckets an und verschiebt diese falls möglich in ein anderes Bucket, sodass das neue eingefügt werden kann. Das Ganze dürfte in O(n²) liegen.

Der andere Lösungsansaz wäre, dass man guckt, welche Buckets besonders beliebt sind und dann erst diejenigen auffüllt, welche überhaupt nicht gewollt werden. Das heißt, wenn in ein Bucket nur drei Elemente rein dürfen und da drinnen noch Platz für 4 ist, dann kommen die drei Elemente da sofort rein. Dürfte auch in O(n²) liegen.

Nur damit man einen Anhaltspunkt bekommt, wie groß das n ist: n ist eine beliebige ganze Zahl zwischen 2^15 und 2^25

Danke schon einmal Smile

[flashpixx]

Generell gelten ja die Landau-Symbole: Landau-Symbole ? Wikipedia

aber da Du ja schon von Buckets redest: Bucketsort ? Wikipedia

Du solltest auch noch überlegen, ob es sich hier _nur_ um den Formalismus handelt oder eine konkrete Implementierung, denn bei der konkreten Implementierung macht natürlich ein O(cn) für große bzw kleines c auch noch einen wirklichen Unterschied.

Phil

[ThunderZone]

Also ich soll es programmieren, von daher wäre das c auch wichtig

Ich kenne Bucketsort, aber Bucketsort benutzt keine zwei Buckets und die Buckets sind auch nicht beschränkt...

Das Problem ist hier glaube ich ein anderes, oder nicht?

[flashpixx]

Ich kenne Bucketsort, aber Bucketsort benutzt keine zwei Buckets und die Buckets sind auch nicht beschränkt...

Doch das geht, denn Du kennst zu beginn die Anzahl an Elementen, nach Deiner Angabe max 2^25 Elemente, damit die die Menge endlich und Du kannst 2^25 / 3 Buckets damit anlegen. Zusätzlich sagst Du ja es dürfen maximal 4 Elemente pro Bucket sein, d.h. 0 <= x <= 4. Da Du beim maximalen Wert von 2^25 Elementen nur 1/3 an Buckets hast, kannst Du diese komplett füllen, ohne dass Du gegen Deine Vorgabe verstößt

Natürlich ist die Frage des "wie befüllst Du die Buckets". Darüber hast Du nichts gesagt, d.h. ich würde naiv mit dem ersten Bucket beginnen und eben gleich verteilen, d.h. im maximalen Fall hast Du 3 Elemente pro Bucket, im minimalsten Fall entstehen leere Buckets.

Oder soll es sich hier um ein Optimierungsproblem handeln wie z.B. Rucksackproblem ? Wikipedia ?

Phil

[ThunderZone]

Ich glaub, ich muss das Problem etwas näher beschreiben...

Man hat n verschiedene Elemente (sind in einem Object Array gespeichert) und diese soll man auf n/3 Buckets verteilen, wobei in jedes Bucket maximal 4 Elemente reinpassen. Deswetieren passen die Elemente in nur jeweils 2 Buckets rein.

Mit dem "Deswetieren passen die Elemente in nur jeweils 2 Buckets rein." meinte ich, dass ein Element von mir aus ab , ac oder bc heißt und dann entsprechend entweder in Bucket "A oder B", "A oder C" oder "B oder C" einsortiert werden muss.

[flashpixx]

Mit dem "Deswetieren passen die Elemente in nur jeweils 2 Buckets rein." meinte ich, dass ein Element von mir aus ab , ac oder bc heißt und dann entsprechend entweder in Bucket "A oder B", "A oder C" oder "B oder C" einsortiert werden muss.

Das heißt dann dass "ab" in Bucket a oder (xor) b kann. Aber wenn ich nun 5 mal ein Element habe, dass "ab" heißt, dann kann ich 4 in a und 1 in b stecken, aber bei 9 "ab"'s geht das nicht mehr in 2 Buckets, denn das würde den pro Bucket maximalen Wert übersteigen.

Was man rein technisch machen kann, Du würdest von jedem Element ein Hash bilden und eine entsprechende Hashmap benutzen, die Duplikate zulässt. D.h. Du weißt dem Bucket einen Hash zu, jedes Element, das in den Bucket soll, erhält den identischen Hash. Ist nun die erste Hashmap voll also in Deinem Bsp es gäbe 6 "ab"'s, und 4 hast Du in den ersten Bucket einsortiert, dann würde die nächsten 2 einen anderen Hash bekommen und in Bucket "b" landen. Schau Dir das Prinzip des "Sondierens" Hashtabelle ? Wikipedia einmal an. Das ist genau dafür gedacht.

Aber Du erschlägst nicht das Problem, dass Du, wenn Du wie im Bsp 9 Elemente hast, aber nur 2 Buckets die verwendet werden dürfen, eben einen Fehler produzierst. Also der erste Ansatz ist eine Hashmap die mehrere Schlüssel zulässt, damit ist jeder Hash das Bucket und dahinter liegen die Werte, Du musst dann eben nur noch eine maximale Begrenzung einführen.

Mein Tipp wäre: Nimm eine entsprechende Hashmap aus Java und vererbe alle in Deine eigene Klasse, in der Du eben nur die entsprechenden Routinen mit dem Count erweiterst.

HTH

Phil