Ziehen ohne Zurücklegen
2006-08-25 18:27
ethrandil
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?]
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?]