rand()%100 ohne doppelte Zahlen

[lolxdflyx3]

Hi,
ich brauche Zufallszahlen, die nicht doppelt vorkommen!
Lässt sich sowas unkompliziert machen, z.B. im srand()?
Bis jetzt habe ich es so versucht zu lösen, leider ohne Erfolg

    int zahlen[6];
    bool doppelt;
    int zs, i1;

        srand(i1); //i1 ist Zähler aus for-schleife
        for(int i=0; i<=5; i++)
        {
            while(doppelt==true)
            {
                doppelt=false;
                zs=(rand()%99)+1;
                for(int i2=0; i2<=i; i2++)
                {
                    if(zahlen[i2]==zs)
                    {
                        doppelt=true;
                    }
                    else
                    {
                        zahlen[i]=zs;
                    }
                }
            }
        }

Der Code-Auschnitt befindet sich in einer For-Schleife!

lolxdfly

[Hiris]

Pack zahlen die schonmal vorgekommen sind in einen std::vector und prüf einfach nach jedem random ergebniss ob es sowas bereits im vector gibt

[Tasiro]

Du könntest std::random_shuffle verwenden (in algorithm). Damit könntest du eine Liste der ersten hundert (oder sechs) Zahlen mischen und dann der Reihe nach durchgehen. Wenn du mehr als nur ein paar Elemente benötigst, ist das effizienter, als die bereits verwendeten Zahlen zu speichern.

[Raz9r]

std::set kann dabei helfen. Und ich erinnere an einen Talk von STL: "rand() considered harmful".

[MrSm!th]

Originally Posted by Hiris

Pack zahlen die schonmal vorgekommen sind in einen std::vector und prüf einfach nach jedem random ergebniss ob es sowas bereits im vector gibt

Ich würde mal behaupten, dass das im Worst Case die Laufzeit stark erhöht.
Ich würde eher einen Vector mit den Zahlen 1-100 füllen und den Random Wert als Index dafür verwenden. Nach Verwendung einer Zahl wird diese aus dem Vektor entfernt.
Logischerweise wäre es dann auch (rand() % (vec.size() - 1)) +1 damit man die Grenzen nicht überschreitet.

[Tasiro]

Originally Posted by MrSm!th

Nach Verwendung einer Zahl wird diese aus dem Vektor entfernt.

Mit dem letzten Wert des Vektors überschrieben und der Vektor um ein verkleinert.

[MrSm!th]

Originally Posted by Tasiro

Mit dem letzten Wert des Vektors überschrieben und der Vektor um ein verkleinert.

Stimmt, das würde es noch optimieren. Vector ist aber ohnehin schon ziemlich fix.

[Tasiro]

Nicht, wenn du nach und nach jedes einzelne Element aus der Mitte entfernst und dann alle anderen Elemente danach verschieben musst. Damit bist du wieder in O(n²).

[Schlüsselbein]

Hast vollkommen recht, Tasiro. Bei 100 Elementen von primitven Datentypen wird das aber nicht ins Gewicht fallen (die werden sowieso blitzschnell kopiert).
Falls der Inhalt auch noch in den Cache gepackt wird, geht der Unterschied wahrscheinlich sogar steil gegen 0.