Hallo,

ich habe folgendes Problem: Ich habe eine Menge Objekte (in Java) und möchte N Objekte ohne zurücklegen ziehen.

Ich möchte das aber möglichst effizient machen.

Die Objekte werden in eine ArrayListe gespeichert und haben damit Indizes.

Für die Grenzfälle habe ich akzeptable Lösungen:

Bei einer großen Menge aus der ich "relativ wenig" ziehe:
Alle bisher gezogenen Objekte merken (HashSet) und bei jeder weiteren Ziehung solange zufällig ziehen, bis ich ein Objekt erwische, dass noch nicht gezogen wurde.

Wenn ich alle Objekte ziehe und nur die Reihenfolge variieren möchte, kann ich einfach N mal zwei zufällige Objekte vertauschen.
(Bei 'sehr großem N' kann man letzteres mit ersterem verknüpfen)

Was aber, wenn N zB etwa ein drittel der Gesamtobjektzahl ist?
Was ist eine effiziente Datenstruktur, mit der man sowas realisieren kann?

mfg
- eth

[Wo soll man Posten, wenn etwas nicht auf das eigene Semester abziehlt aber ein Informatisches Problem ist?]

Wenn ich alle Objekte ziehe und nur die Reihenfolge variieren möchte, kann ich einfach N mal zwei zufällige Objekte vertauschen.

Ist das Ergebnis dann wirklich gleichverteilt? Mein Bauch sagt mir, dass fuer ein gegebenes Element die Wahrscheinlichkeit, dass es auf seinem Platz bleibt, groesser als 1/N ist. Kann mich aber auch irren.

Besser: Erst das erste mit einem zufaelligen tauschen, dann das zweite, dann das dritte, …
Das laesst sich dann sogar trivial auf

Was aber, wenn N zB etwa ein drittel der Gesamtobjektzahl ist?

verallgemeinern.

[Wo soll man Posten, wenn etwas nicht auf das eigene Semester abziehlt aber ein Informatisches Problem ist?]

passt schon.

Wenn ich alle Objekte ziehe und nur die Reihenfolge variieren möchte, kann ich einfach N mal zwei zufällige Objekte vertauschen.

Ist das Ergebnis dann wirklich gleichverteilt? Mein Bauch sagt mir, dass fuer ein gegebenes Element die Wahrscheinlichkeit, dass es auf seinem Platz bleibt, groesser als 1/N ist.

Dein Bauch scheint recht zu haben. Hier hilft ein
kombinatorisches Argument: bei der oben beschriebenen
Vorgehensweise gibt es [img]http://mokrates.de/cgi-bin/texstring?(n(n-1))%5En[/img] (oder [img]http://mokrates.de/cgi-bin/texstring?n%5E%7B2n%7D[/img],
aber dann gilt das gleiche) verschiedne Ergebnisse. Diese
gleichmäßig als Permutationen zu interpretieren geht nur
dann, wenn n! ein Teiler davon ist. Das ist aber bereits
dann nicht erfüllt, wenn es eine Primzahl <n gibt, die weder
ein Teiler von n noch einer von n-1 ist.

Besser: Erst das erste mit einem zufaelligen tauschen, dann das zweite, dann das dritte, …
Das laesst sich dann sogar trivial auf

Was aber, wenn N zB etwa ein drittel der Gesamtobjektzahl ist?

verallgemeinern.

Falls du das nicht schon so meintest: das hat den Vorteil,
dass man dann die Zufallszahl immer aus dem Bereich [k+1,n]
wählen kann, wenn man bereits k Elemente gewählt hat. Dann
ist das Problem der Verschiedenheit der Indizes schon keines
mehr [img]http://www.fb18.de/gfx/23.gif[/img]

Okay danke, das hat meinen Code ganz nett beschleunigt ;-)

- eth

Ah, ja, Fisher-Yates shuffle, sehr praktisch und gerne wird mit einer fehlerhaften Implementierung die Gleichverteilung zerstört. ;-)

Ich würde auf die Speziellösung für "wenige ziehen" verzichten und generell die Vertauschlösung wählen. Zumindest ohne das zu messen würde ich hier keine Sondernbehandlung wählen, die noch dazu eine Voraussage über die Verwendung benötigt.

Desweiteren würde ich nicht mit dem Element am Anfang, sondern mit dem am Ende vertauschen. Statt einen eigenen Zähler zu führen, kann man dann auch einfach a.remove(a.size() -1) aufrufen. Das hat natürlich etwas Overhead, aber der ist zumindest bei der derzeitigen Sun-Implementierung gering. Wenn eine Messung ergibt, dass er doch zu groß ist, kann man einen eigenen Zähler einsetzen.