Zufallsgenerator sinnvoll umgesetzt?

Hallihallo,

ich hoffe mal ich hab hier das richtige Unterforum erwischt

Ich habe aus langeweile mal probiert einen Zufallsgenerator zu schreiben. Ich bin kein Profi, dass was ich kann sind bisher if Bedingungen, Schleifen und Arrays ..

Ich will die Zahlen 1-32 auf vier Parts (Arrays) aufteilen.
z. B. Part 1: 2, 7, 9, 14, 15, 22, 29, 32
und die restlichen Parts enthalten dann die ÜBRIGEN Zahlen, also es kommen keine Zahlen doppelt vor.

Es funktioniert auch alles einwandfrei, jedoch möchte ich jetzt von euch wissen, wie "gut" das Ergebnis ist.
Dazu habe ich ein Programm geschrieben, das nach jeder Vergabe der Zahlen den Durchschnitt berechnet. Z. B. wäre das bei dem Beispiel oben:
(2+7+9+14+15+22+29+32)/8 = 16.25

So .. das habe ich in eine Schleife gepackt und dann für jeden Part 50.000 mal laufen lassen. Die errechneten Durchschnitte addiert und durch 50.000 geteilt, so dass ich eine gesamten Durchschnitt bekomme.

Die Ergebnisse:
Part1 / Part2 / Part3 / Part4
17,6710 | 12,1430 | 16,7531 | 19,3615
13,7755 | 18,3095 | 16,6470 | 17,2680
14,3745 | 19,5665 | 16,3165 | 15,7426
18,0250 | 14,8750 | 15,9750 | 17,1250
14,7227 | 15,5889 | 16,7052 | 18,9832
17,4058 | 19,1730 | 14,8612 | 14,5601
16,9427 | 16,4717 | 16,6864 | 15,8992

So .. und jetzt zur eigentlichen Frage, sind das gute Werte??

Ich habe z. B. mal so lange rechnen lassen, bis in Part 1 acht Werte unter 15 sind. Nach 6.000.000 hatte ich noch kein Ergebnis.

Noch was zum Code:
Ich berechne erst ein Array mit 32 Elementen - die Funktion Richtigkeit überprüft dabei, das keine doppelten Werte vorkommen.

Nachdem das Array gesetzt ist soll sich Spieler1, Spieler2, Spieler3 und Spieler4 je 8 Werte per Zufall holen. Die Funktion Richtigkeit überprüft dabei, das ein Wert nicht schon in einem anderen Spielerx Array steht!

#include <cstdlib>
#include <iostream>
#include <time.h>

using namespace std;

//Array mit 32 Elemente auf gleiche Werte untersuchen
bool Richtigkeit(int Array[], int x)
{
    int n=0;
    for(int i=0; i<32; i++)
    {
        if(Array[i]==x)         //Wenn ein gleicher Wert gefunden wird, dann wird +1 addiert
            n++;
    }
    if(n>0)
        return false;           //==> n gleiche Werte gefunden
    else
        return true;            //Wert noch nicht vorhanden
}

//Spieler Arrays auf doppelte Werte untersuchen
bool Richtigkeit2(int Spieler1[], int Spieler2[], int Spieler3[], int Spieler4[], int x)
{
    int n=0;
    for(int i=0; i<8; i++)
    {
        if(Spieler1[i]==x || Spieler2[i]==x || Spieler3[i]==x || Spieler4[i]==x)
            n++;
    }
    if(n>0)
        return false;
    else
        return true;
}

int main(int argc, char *argv[])
{
    srand(time(0));
    int x;
    int Array[32]={0,0};
    int Spieler1[8]={0,0};
    int Spieler2[8]={0,0};
    int Spieler3[8]={0,0};
    int Spieler4[8]={0,0};

    //Array mit 32 Elementen per Zufall einlesen
    for(int i=0; i<32; i++)
    {
        x=1+rand()%(32-1+1);
        while(Richtigkeit(Array, x)==false)
            x=1+rand()%(32-1+1);
        Array[i]=x;
    }

    //Je 8 Werte aus 32-wertigen Array per Zufall ermitteln
    //Spieler 1
    for(int i=0; i<8; i++)
    {
        x=1+rand()%(32-1+1);
        while(Richtigkeit2(Spieler1,Spieler2,Spieler3,Spieler4,x)==false)
            x=1+rand()%(32-1+1);
        Spieler1[i]=x;
    }
    //Spieler 2
    for(int i=0; i<8; i++)
    {
        x=1+rand()%(32-1+1);
        while(Richtigkeit2(Spieler1,Spieler2,Spieler3,Spieler4,x)==false)
            x=1+rand()%(32-1+1);
        Spieler2[i]=x;
    }
    //Spieler 3
    for(int i=0; i<8; i++)
    {
        x=1+rand()%(32-1+1);
        while(Richtigkeit2(Spieler1,Spieler2,Spieler3,Spieler4,x)==false)
            x=1+rand()%(32-1+1);
        Spieler3[i]=x;
    }
    //Spieler 4
    for(int i=0; i<8; i++)
    {
        x=1+rand()%(32-1+1);
        while(Richtigkeit2(Spieler1,Spieler2,Spieler3,Spieler4,x)==false)
            x=1+rand()%(32-1+1);
        Spieler4[i]=x;
    }

    //Ausgabeschleife
    for(int i=0; i<8; i++)
        cout<<Spieler1[i]<<"\t"<<Spieler2[i]<<"\t"<<Spieler3[i]<<"\t"<<Spieler4[i]<<endl;

    cout<<endl<<endl;

system("PAUSE");
return 0;
}

Der Code bezieht sich nur auf den Zufallsgenerator damit der Code übersichtlicher bleibt.

Michael E.

Wie "gut" dein Code ist, hängt von deinem Ziel ab. Du berechnest eine sogenannte Permutation, also eine zufällige Reihenfolge, der Zahlen 1 bis 32. Normalerweise will man, dass jede der 32! möglichen Permutationen gleichwahrscheinlich ist. Dafür kann man BTW random_shuffle aus der Standardbibliothek nehmen. Das scheint aber nicht dein Ziel zu sein. Du willst wohl eher, dass die Summe in jeder Partition gleich groß ist. Dafür gibt es natürlich eine optimale Anordnung, nur hast du dann keinen Zufall mehr im Spiel. Du musst also eine Wahrscheinlichkeitsdichte definieren, d.h. für jede Permutation eine Wahrscheinlichkeit angeben, um deine Arbeit beurteilen zu können.

Ach genau, mein Ziel .. das wollte ich noch sagen

Also das soll praktisch eine Kartenverteilung darstellen.
Hinter jeder Zahl steckt eine Karte.

Nach der Kartenverteilung wollte ich dann rumprobieren, wie oft man neu verteilen muss um eine bestimmte Kombination zu bekommen.

Michael E.

Hab deinen ersten Beitrag mal genauer gelesen. Dir gehts wohl gar nicht darum, dass du Teilsummen gleich sind, sondern tatsächlich um eine uniform zufällige Permutation. Unter diesem Stichpunkt findest du deutlich bessere Algorithmen als das, was du gemacht hast.

Ein erster Ansatzpunkt für dich: Wenn die Zahlen 1 bis 32 bereits in zufälliger Reihenfolge in Array stehen, kannst du die ersten 8 Zahlen Spieler 1, die zweiten 8 Zahlen Spieler 2 etc. zuweisen. Die Kartenverteilung wird nicht "zufälliger" dadurch, dass du jedem Spieler zufällige Positionen zuweist. Du bleibst bei einer Gleichverteilung.

Dann wäre das einfacher und ich hätte das gleiche Ergebnis.

Wo finde ich den solche Algorithmen ??

Michael E.

Google mal nach "uniform permutation" oder Ähnlichem. Das bringt dann z.B. http://en.wikipedia.org/wiki/Random_permutation und http://en.wikipedia.org/wiki/Knuth_shuffle.

knivil

www.cplusplus.com/reference/algorithm/random_shuffle/

Danke für die Links
Bei Gelegenheit werd ich sie mir natürlich genauer anschauen.

Ich hab mir nochmal selber was ausgedacht. Ist der Zufallsgenerator jetzt "besser" ??

Meine Idee:
Ich lese in einem Array 32 Werte ein .. von 1-32 (inkl.)
Dann lasse ich per rand() eine Zahl generieren, die die Tauschvorgänge im Array angibt.
In einer for-Schleife berechne ich dann nochmal per rand() zwei Zahlen zwischen 0 und 31 (inkl.). Jetzt werden die Werte im 32-wertigen Array an den beiden rand() Werten getauscht.

#include <cstdlib>
#include <iostream>
#include <time.h>

using namespace std;

int main(int argc, char *argv[])
{
    srand(time(0));
    int Array[32];
    int m=0;            //Zähler für Sx[8] einlesen

    //Array Werte einlesen
    for(int i=0; i<32; i++)
        Array[i]=i+1;

    //Tauschvorgänge
    int n=rand();

    //Tauschvorgang
    for(int i=0; i<n; i++)
    {
        int x=rand()%32;
        int y=rand()%32;
        int platz1=Array[x];
        int platz2=Array[y];
        Array[x]=platz2;
        Array[y]=platz1;
    }

    //Auf 4 aufteilen
    int S1[8], S2[8], S3[8], S4[8];

    //Werte für Sx[8] einlesen
    //S1
    for(int i=0; i<8; i++)
        S1[i]=Array[i];

    //S2
    for(int i=8; i<16; i++)
    {
        S2[m]=Array[i];
        m++;
    }
    m=0;

    //S3
    for(int i=16; i<24; i++)
    {
        S3[m]=Array[i];
        m++;
    }
    m=0;

    //S4
    for(int i=24; i<32; i++)
    {
        S4[m]=Array[i];
        m++;
    }

    //Ausgabeschleife
    for(int i=0; i<8; i++)
        cout<<S1[i]<<"\t"<<S2[i]<<"\t"<<S3[i]<<"\t"<<S4[i]<<endl;

    cout<<endl<<endl;

    system("PAUSE");
    return 0;
}

Michael E.

Bei deinem neuen Verfahren ist nicht jede Permutation gleichwahrscheinlich. Je größer dein n ist, desto mehr näherst du dich der Gleichverteilung, aber du wirst sie nie ganz erreichen können. Es gibt genauso komplizierte Algorithmen (wie z.B. der verlinkte), die eine Gleichverteilung hinbekommen. Insofern hast du zwar deine Laufzeit verbessert, aber das Ergebnis verschlechtert.

Was heißt denn Gleichverteilung genau??

Wenn ich öfters zufällig tausche, warum nähere ich mich dann da an??

Übrigens danke für die schnelle Hilfe

knivil

Ja.

Michael E.

Gleichverteilung bedeutet, dass jede Anordnung deiner Zahlen 1 bis 32 gleichwahrscheinlich ist. Um genau zu sein, hat dann jede Permutation die Wahrscheinlichkeit 1/32!, weil es genau 32! (32 Fakultät) verschiedene Permutationen gibt.

Warum du dich dieser Verteilung mit großem n annäherst: Da fällt mir auf die Schnelle auch kein formales Argument ein. Das war mehr eine intuitive Aussage.

Aber ich dachte es ist gut wenn jede Verteilung gleichwahrscheinlich ist

ah ok .. hab den vorherigen Post nochmal gelesen.

Ich näher mich der Gleichverteilung nur an .. aber ich erreiche sie nicht .. okay

Warum ist das eigentlich so, dass nicht alle Kombinationen gleichwahrscheinlich sind??

Das kann ich mir irgendwie nicht vorstellen ..

Michael E.

Es gibt 32! verschiedene Permutationen. Dein Algorithmus wählt eine von 32^(2n) Möglichkeiten für n Vertauschungen. Damit jede Permutation gleichwahrscheinlich ist, müsste 32^(2n) durch 32! teilbar sein. Das ist aber nicht der Fall.

Pures C ins C++ Dorum gesetzt nur wegen cout und keiner sagt was ...

Schau dir vector an und vergiss c Arrays, die brauchst du nur noch sehr selten
(in c++).

unskilled

boost schrieb:

Schau dir vector an und vergiss c Arrays, die brauchst du nur noch sehr selten
(in c++).

stimmt. arrays sind hier ja äußerst fehl am platz. weil die länge des arrays ja erst zur laufzeit bekannt ist. oh... wait !

knivil

Ich raff es noch nicht: Was spricht dagegen, std::random_shuffle einfach zu benutzen?