rand()%100 ohne doppelte Zahlen

11/08/2013 18:04 lolxdflyx3#1
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 :(

Code:
    int zahlen[6];
    bool doppelt;
    int zs, i1;
Code:
        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
11/08/2013 18:47 Hiris#2
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
11/08/2013 20:54 Tasiro#3
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.
11/09/2013 10:25 Raz9r#4
std::set kann dabei helfen. Und ich erinnere an einen Talk von STL: "rand() considered harmful".
11/09/2013 15:50 MrSm!th#5
Quote:
Originally Posted by Hiris View Post
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.
11/09/2013 16:11 Tasiro#6
Quote:
Originally Posted by MrSm!th View Post
Nach Verwendung einer Zahl wird diese aus dem Vektor entfernt.
Mit dem letzten Wert des Vektors überschrieben und der Vektor um ein verkleinert.
11/09/2013 18:10 MrSm!th#7
Quote:
Originally Posted by Tasiro View Post
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.
11/09/2013 18:18 Tasiro#8
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²).
11/09/2013 18:52 Schlüsselbein#9
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.