Zufallsgenerator sinnvoll umgesetzt?

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?

asc

unskilled schrieb:

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

Bei bekannter Größe gibt es dennoch sinnvolle Alternative (wie array).

knivil schrieb:

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

Ich bin Anfänger und hab nur aus einer Idee heraus einen Zufallsgenerator schreiben wollen.