vector / shuffle / iteratoren

leech

die länge des vectors kannst du ermitteln, indem du in einer for-schleife vom anfang bis zum ende mit dem iterator durchläufst und dann einen counter hochzählst... oder du nimmst einfach:

int laenge = vectorname.size();

aber warum übergibst du die iteratoren und nicht einfach den vector selber? das wäre doch viel leichter und nicht so umständlich...

mr.delete

weil die aufgabe so gestellt wurde!
ich weiss es gebe diverse einfachere lösungsansätze,
aber die aufgabenstellung verlangt eine funktion, welche einen vector mischt,
der funktion werden aber nur start und end iterator übergeben.

gibt es keine -unter dieser einschränkenden bedingung - elegantere lösung
als das durchzählen mit einem counter?

John Doe

Nun, du könntest dir, zur Inspiration, ja mal die "Musterlösung" in
random_shuffle ankucken.

mfg JJ

mr.delete

wo finde ich die?

terraner

in <algorithm>
(im include verzeichnis deines compilers )

mfg

mr.delete

// random_shuffle

template <class _RandomAccessIter>
inline void random_shuffle(_RandomAccessIter __first,
                           _RandomAccessIter __last) {
  if (__first == __last) return;
  for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
    iter_swap(__i, __first + __random_number((__i - __first) + 1));
}

recht elegant, obwhol ich es so nicht ganz verstehe und nicht direkt verwenden kann....hmmm

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.