vector / shuffle / iteratoren

wie funktioniert der algo?

kann man auch folgendes implementieren? ich weiss, der algo ist recht schlecht von der laufzeit...

vector<int> vec = {1, 2, 3, 4, 5, 6, 7};

void shuffle(vector<int> &vec) {
	vector<int> shuffled(vec.size());
	int index = 0;

	while (index < shuffled.size()) {
		int r = rand() % vec.size();

		if (vec[r] != -1) {
			shuffled[index] = vec[r];
			vec[r] = -1;
			index++;
		}
	}

	std::copy(shuffled.begin(). shuffled.end(), vec.begin());
}

coder007 schrieb:

kann man auch folgendes implementieren? ich weiss, der algo ist recht schlecht von der laufzeit...

Vorausgesetzt, das Eingabearray hat keine -1, dann produziert dieser Algorithmus eine zufällige Permutation. Insofern ist er "korrekt".

Aber langsam, unelegant und ungenerisch.

das stimmt, was wäre die nächst schnellere variante?

wie funktioniert dieser random_shuffle algo aus dem vorherigen post?

Nathan

Hier eine lesbarere Implementierung (von http://en.cppreference.com/w/cpp/algorithm/random_shuffle):

template< class RandomIt >
void random_shuffle( RandomIt first, RandomIt last )
{
    typename std::iterator_traits<RandomIt>::difference_type i, n;
    n = last - first;
    for (i = n-1; i > 0; --i) {
        using std::swap;
        swap(first[i], first[std::rand() % (i+1)]);
    }
}

(diese Version ist deprecated, weil sie rand() nutzt, in C++11 gibt es wesentlich bessere Generatoren)
Sie läuft einfach in einer Schleife von n-1 bis 0 und swappt das i-te Element mit einem Element aus dem Intervall [0, i].

Nathan schrieb:

Sie läuft einfach in einer Schleife von n-1 bis 0 und swappt das i-te Element mit einem Element aus dem Intervall [0, i].

Hier der Link zur Erklärung, warum das funktioniert: https://en.wikipedia.org/wiki/Fisher–Yates_shuffle

welche laufzeit komplexitaet hat dieser algo?

void shuffle(vector<int> &vec) { 
    vector<int> shuffled(vec.size()); 
    int index = 0; 

    while (index < shuffled.size()) { 
        int r = rand() % vec.size(); 

        if (vec[r] != -1) { 
            shuffled[index] = vec[r]; 
            vec[r] = -1; 
            index++; 
        } 
    } 

    std::copy(shuffled.begin(). shuffled.end(), vec.begin()); 
}

Skym0sh0

O(n)

Skym0sh0 schrieb:

O(n)

Mit der O-Notation kann man hier nicht argumentieren, Worst Case ist Endlosschleife.

Der i-te Schritt braucht etwa n/(n-i) Schritte. Nimmt man die Summe hat man n*(1/1+1/2+1/3+...+1/n), was n*Hn≈n log n entspricht.

Also durchschnittlich quasilinear Laufzeit.

SeppJ schrieb:

Skym0sh0 schrieb:

O(n)

Nein, das ist O(n^2). Die Schleife läuft im Schnitt so viele Schritte wie die Summe der ganzen Zahlen von 1 bis n.

Er nimmt sich einen zufälligen Index, er läuft nicht von vorne nach hinten durch. Das n/2-te Element braucht nur etwa 2 Versuche, da 50% aller Zufallsindices noch voll sind.

SeppJ

Induktionsherd schrieb:

SeppJ schrieb:

Skym0sh0 schrieb:

O(n)

Nein, das ist O(n^2). Die Schleife läuft im Schnitt so viele Schritte wie die Summe der ganzen Zahlen von 1 bis n.

Er nimmt sich einen zufälligen Index, er läuft nicht von vorne nach hinten durch. Das n/2-te Element braucht nur etwa 2 Versuche, da 50% aller Zufallsindices noch voll sind.

Hast recht, das fiel mir wenige Sekunden nach dem Posten auch selber auf und ich habe den Beitrag daher wieder gelöscht, da zu dem Zeitpunkt noch keine andere Antwort da war. Da warst du anscheinend wirklich in diesem 20 Sekundenfenster aktiv, als meine Antwort so im Forum stand.

Skym0sh0

Induktionsherd schrieb:

Skym0sh0 schrieb:

O(n)

Mit der O-Notation kann man hier nicht argumentieren, Worst Case ist Endlosschleife.

Der i-te Schritt braucht etwa n/(n-i) Schritte. Nimmt man die Summe hat man n*(1/1+1/2+1/3+...+1/n), was n*Hn≈n log n entspricht.

Also durchschnittlich quasilinear Laufzeit.

Ups, mist übersehen.

Ja, hast Recht. Worst-Case ist echt die Endlosschleife. Mein Fehler.