Zufallsliste erstellen OHNE Doppelten

Zuvor gewählte Nummern speichern und bei neuer Zufallszahl prüfen ob sie in der Liste enthalten; und somit schon einmal ausgewählt worden ist.

SeppJ

N: Anzahl der zu ziehenden Zahlen
I: Anzahl der möglichen Zahlen

a) Container mit den ziehbaren Zahlen füllen.
b) Zahl I ziehen, nenne diese R
c) Zahl an Containerposition R nehmen. Zahl an Stelle R mit letzter Zahl aus Container ersetzen
d) I um eins erniedrigen
e) Weiter bei b, bis N Zahlen gezogen.

Dies ist im Gegensatz zu Nexus Vorschlag O(N), Nexus ist (bei meiner Notation) O(I), und es ist immer N<I.

CaribicSurfer

Danke an alle

Habs nun erstmal mit Nexus Ansatz eine Lösung:

std::vector<int> Number(length);
for (int i=0;i<length;i++)
Number[i] = i;

std::random_shuffle(Number.begin(),Number.end());

Werde mir später den Ansatz von SeppJ anschauen, den habe ich nicht auf Anhieb verstanden.

Danke und Gruß

SeppJ

CaribicSurfer schrieb:

Werde mir später den Ansatz von SeppJ anschauen, den habe ich nicht auf Anhieb verstanden.

Ich glaube ich habe mich nur kompliziert ausgedrückt. Das ist ganz einfach: Du hast eine Liste mit allen möglichen Zahlen, wenn du eine ziehst, dann entfernst du die Zahl aus der Liste. Fertig.

Das mit dem Einfügen der letzten Zahl und so sind bloß Details, weil dies die effizienteste Möglichkeit ist, ein Element aus einem vector zu entfernen.

Nexus

@ SeppJ: Du hast mehrere Möglichkeiten, eine Zahl aus der Liste zu ziehen. Vom anfänglichen Füllen, das ohnehin O(I) benötigt, sehen wir nun einmal ab. Wenn man STL-Container verwendet, ergeben sich meiner Ansicht nach folgende Fälle:

1. Liste mischen -> benötigt O(I)

2. Liste aufsteigend sortiert lassen, Index als Zufallszahl in [1,I[ erzeugen, Element an der Stelle löschen.

2a. std::vector , std::deque : Löschen benötigt O(I)
2b. std::list : Kein Random Access, Zugriff braucht O(I)

Hab ich was übersehen?

Edit: Ah, alles klar. Löschen aus Random-Access-Containern geht ja mit dem Swap-Trick in O(1). Die Technik empfehle ich sogar selbst regelmässig

Nexus schrieb:

Edit: Ah, alles klar. Löschen aus Random-Access-Containern geht ja mit dem Swap-Trick in O(1). Die Technik empfehle ich sogar selbst regelmässig

Könntest du das bitte genauer erklären?

Nexus

Aber sicher doch

// 1. Benötigt O(n), wobei n = #Elemente
// (alle nachfolgenden Elemente werden nach vorne verschoben)
myVector.erase(myIterator);

// 2. Benötigt O(1)
// (nur letztes Element wird gelöscht, dafür wird die
// Reihenfolge verändert, was aber oft egal ist)
swap(*myIterator, myVector.back());
myVector.pop_back();

Danke für die Erklärung

SeppJ schrieb:

N: Anzahl der zu ziehenden Zahlen
I: Anzahl der möglichen Zahlen

a) Container mit den ziehbaren Zahlen füllen.
b) Zahl I ziehen, nenne diese R
c) Zahl an Containerposition R nehmen. Zahl an Stelle R mit letzter Zahl aus Container ersetzen
d) I um eins erniedrigen
e) Weiter bei b, bis N Zahlen gezogen.

Dies ist im Gegensatz zu Nexus Vorschlag O(N), Nexus ist (bei meiner Notation) O(I), und es ist immer N<I.

exakt genauso mach ich das auch. Man hat keine Vergleiche, und keinen Ballast, außer dass man ein zusätzliches Array erzeugen muss und danach wieder zerstören muss. Schnell gehts wohl kaum.

padreigh

Es geht auch ohne <int> Array - Performance müsste man testen.

Ich gehe davon aus das du mit den Dateien auch irgendwas machen willst?
Hol dir ein QDir meinDir(derPfadZuDenDateien); Nutze dessen entryList() um alle Datein zu bekommen. Stopf die resultierende QStringList mit ihren Iteratoren in std::rnd_shuffle(stringlist.begin(),stringlist.end()) . Mach dann ein stringlist.erase(stringlist.begin()+500); darauf - dann kannst du direkt damit weiterarbeiten...

Unter Umständen ist das schneller als jedesmal den n-ten Filenamen wieder zu holen - insgesamt musst du das aber testen da es stark davon abhängt wie Qt die Interna der Listen handelt und wie da wo optimiert ist.