Erweitern Sie einen zufälligen Bereich von 1–5 bis 1–7

692

Schreiben Sie bei einer gegebenen Funktion, die eine zufällige Ganzzahl im Bereich von 1 bis 5 erzeugt, eine Funktion, die eine zufällige Ganzzahl im Bereich von 1 bis 7 erzeugt.

  1. Was ist eine einfache Lösung?
  2. Was ist eine effektive Lösung, um die Speichernutzung zu reduzieren oder auf einer langsameren CPU zu laufen?
Roger Pate
quelle
Es erwies sich als unerwartet interessantes Problem, ich denke immer noch, wie man 1) es in fester Zeit macht und 2) die gleichmäßige Verteilung nicht verdirbt (wenn es welche gab)
Eugensk
Wir hatten das ähnliche Problem, als wir einen von fünf Spielern mit einem Würfel auswählten. Wir haben abwechselnd gewürfelt, einer, der die maximale Punktzahl erreicht, wird ausgewählt. Die Gleichmäßigkeit wurde erreicht, aber keine Zeitkonstanz :)
Eugensk
Würde ich herabgestuft werden, wenn ich eine Antwort schreibe, die besagt, dass das Problem nicht vorschreibt, dass Sie die angegebene Funktion verwenden und einfach eine schreiben müssen, die zufällig 1-7 zurückgibt?
Doktor Blue
Was ist mit 7 * rand5() / 5?
Kiwixz
@kiwixz, das wird "zwischen 1 und 7" erzeugen, aber Sie erhalten nicht 3 oder 6: {1: 19.96, 2: 20.02, 4: 20.01, 5: 19.99, 7: 20.02} grobe Prozentsätze, die manuell getestet werden. 7 * .2, 7 * .4, 7 * .6, 7 * .8, 7 * 1.
Pythonlarry

Antworten:

572

Dies entspricht der Lösung von Adam Rosenfield, ist jedoch für einige Leser möglicherweise etwas klarer. Es wird davon ausgegangen, dass rand5 () eine Funktion ist, die eine statistisch zufällige Ganzzahl im Bereich von 1 bis einschließlich 5 zurückgibt.

int rand7()
{
    int vals[5][5] = {
        { 1, 2, 3, 4, 5 },
        { 6, 7, 1, 2, 3 },
        { 4, 5, 6, 7, 1 },
        { 2, 3, 4, 5, 6 },
        { 7, 0, 0, 0, 0 }
    };

    int result = 0;
    while (result == 0)
    {
        int i = rand5();
        int j = rand5();
        result = vals[i-1][j-1];
    }
    return result;
}

Wie funktioniert es? Stellen Sie sich das so vor: Stellen Sie sich vor, Sie drucken dieses zweidimensionale Array auf Papier aus, heften es an eine Dartscheibe und werfen zufällig Pfeile darauf. Wenn Sie einen Wert ungleich Null treffen, ist dies ein statistisch zufälliger Wert zwischen 1 und 7, da eine gleiche Anzahl von Werten ungleich Null zur Auswahl steht. Wenn Sie eine Null treffen, werfen Sie den Pfeil einfach weiter, bis Sie eine Nicht-Null treffen. Genau das macht dieser Code: Die Indizes i und j wählen zufällig einen Ort auf der Dartscheibe aus, und wenn wir kein gutes Ergebnis erzielen, werfen wir weiter Darts.

Wie Adam sagte, kann dies im schlimmsten Fall für immer laufen, aber statistisch gesehen passiert der schlimmste Fall nie. :) :)

Rob McAfee
quelle
5
Ich habe die Logik hinter dieser Lösung verstanden, kann aber nicht verstehen, wie sich daraus eine einheitliche Wahrscheinlichkeit ergibt. Kann jemand die Mathematik erklären?
user1071840
6
@ user1071840 - Wenn rand5es einheitlich ist, hat jede Zelle im valsRaster die gleiche Wahrscheinlichkeit, ausgewählt zu werden. Das Raster enthält genau drei Kopien jeder Ganzzahl im Intervall [1, 7] sowie vier Nullen. Der "rohe" Ergebnisstrom tendiert also zu einer gleichmäßigen Mischung von [1, 7] -Werten plus einigen Nullen, die etwas häufiger auftreten als jeder einzelne zulässige Wert. Dies spielt jedoch keine Rolle, da die Nullen entfernt werden und nur eine gleichmäßige Mischung von [1, 7] -Werten übrig bleibt.
Daniel Earwicker
3
Die Abkürzung, um das Problem damit zu realisieren: Wenn Sie rand5 () nur einmal aufrufen, haben Sie nur 5 mögliche Ergebnisse. Es gibt offensichtlich keine Möglichkeit, daraus mehr als 5 mögliche Ergebnisse zu machen, ohne mehr Zufälligkeit hinzuzufügen.
Daniel Earwicker
1
Die längere Version: rand5 () kann nur die Werte (1, 2, 3, 4, 5) haben. Daher kann rand5 () * 5 nur die Werte (5, 10, 15, 20, 25) haben, was nicht mit einem vollständigen Bereich (1 ... 25) identisch ist. Wenn dies der Fall wäre, würde das Subtrahieren von 4 (-3 ... 21) ergeben, aber in diesem Fall wird es (1, 6, 11, 16, 21), sodass die Endpunkte korrekt sind, aber es gibt vier große Löcher: ( 2..5), (7..10), (12..15), (17..21). Schließlich machst du Mod 7 und addierst 1, was (2, 7, 5, 3, 1) ergibt. Es treten also nie 4 oder 6 auf. Aber (siehe Abkürzung oben) wir wussten, dass es die ganze Zeit nur 5 Zahlen im resultierenden Bereich geben konnte, also musste es zwei Lücken geben.
Daniel Earwicker
1
Ah, weil wir nur rand5 () haben, nicht rand2 () :-)
gzak
352

Es gibt keine (genau korrekte) Lösung, die in einer konstanten Zeitspanne ausgeführt wird, da 1/7 eine unendliche Dezimalstelle in Basis 5 ist. Eine einfache Lösung wäre die Verwendung der Ablehnungsabtastung, z.


int i;
do
{
  i = 5 * (rand5() - 1) + rand5();  // i is now uniformly random between 1 and 25
} while(i > 21);
// i is now uniformly random between 1 and 21
return i % 7 + 1;  // result is now uniformly random between 1 and 7

Dies hat eine erwartete Laufzeit von 25/21 = 1,19 Iterationen der Schleife, aber es gibt eine unendlich geringe Wahrscheinlichkeit, dass die Schleife für immer wiederholt wird.

Adam Rosenfield
quelle
7
Die -1 wird nicht benötigt, wenn die> 21 auf> 26 b / c umgedreht wird. Es spielt keine Rolle, wohin ich die Untergrenze
BCS
26
Ich möchte erklären, warum dies richtig ist: Angenommen, ich möchte ein Programm schreiben, das einen Strom einheitlicher Zufallszahlen von 1 bis 25 ausgibt. dafür würde ich einfach 5 * (rand5 () - 1) + rand5 () zurückgeben, wie im Code in der Antwort. Wenn ich nun einen Stream mit einheitlichen Zufallszahlen zwischen 1 und 21 erstellen möchte, wenn ich nur den ersten Stream verwende, ihn aber so filtere, dass die Zahlen in [22, 25] abgelehnt werden, kann ich diesen Stream auch erstellen. Wenn ich als nächstes diesen Stream nehme und ihn so filtere, dass für jedes Element x I x% 7 + 1 ausgegeben wird, habe ich einen Stream mit einheitlichen Zufallszahlen von 1 bis 7! Ganz einfach, nicht wahr? : D
Paggas
6
Und Sie haben Recht, dass es darauf ankommt, ob Sie eine perfekte Verteilung mit unbegrenzter Worst-Case-Laufzeit oder eine unvollständige Verteilung mit begrenzter Laufzeit wünschen. Dies ist eine Folge der Tatsache, dass alle Potenzen 5 nicht durch 7 teilbar sind oder äquivalent, wenn Sie 5 ^ n gleich wahrscheinlich Folgen der Länge n haben, es keine Möglichkeit gibt, jeder Folge eine Zahl von 1 bis 7 zuzuweisen, so dass jede von 1..7 ist ebenso wahrscheinlich.
Adam Rosenfield
5
@ Jules Olléon: Angenommen, es gibt eine Lösung, die in konstanter Zeit ausgeführt wird Nund rand5()im schlimmsten Fall garantiert nur Anrufe tätigt . Dann gibt es 5 ^ N mögliche Ergebnisse der Folge von Anrufen an rand5, von denen jeder eine Ausgabe von 1-7 hat. Wenn Sie also alle möglichen Folgen von Anrufen kaddieren, deren Ausgabe für jeweils 1 ≤ k ≤ 7 ist, beträgt die Wahrscheinlichkeit, dass die Ausgabe km / 5 ^ N ist, wobei m die Anzahl solcher Folgen ist. Also, m / 5 ^ N = 1/7, aber es gibt keine möglichen ganzzahligen Lösungen (N, m) für diesen ==> Widerspruch.
Adam Rosenfield
4
@paxdiablo: Du bist falsch. Die Wahrscheinlichkeit, dass ein echtes RNG eine unendliche Folge von 5 erzeugt, ist genau 0, wobei eine ähnliche Argumentation verwendet wird wie die Tatsache, dass das unendliche Werfen einer Münze garantiert nicht unendlich viele aufeinanderfolgende Köpfe erzeugt . Dies bedeutet auch, dass die Wahrscheinlichkeit, dass sich dieser Code für immer wiederholt, genau 0 ist (obwohl es eine positive Chance gibt, dass er für eine beliebige Anzahl von Iterationen wiederholt wird).
BlueRaja - Danny Pflughoeft
153

Ich möchte zusätzlich zu meiner ersten Antwort eine weitere Antwort hinzufügen . Diese Antwort versucht, die Anzahl der Anrufe rand5()pro Anruf zu minimieren rand7(), um die Verwendung der Zufälligkeit zu maximieren. Das heißt, wenn Sie Zufälligkeit als wertvolle Ressource betrachten, möchten wir so viel wie möglich davon verwenden, ohne zufällige Teile wegzuwerfen. Diese Antwort hat auch einige Ähnlichkeiten mit der in Iwans Antwort dargestellten Logik .

Die Entropie einer Zufallsvariablen ist eine genau definierte Größe. Für eine Zufallsvariable, die N Zustände mit gleichen Wahrscheinlichkeiten annimmt (eine gleichmäßige Verteilung), beträgt die Entropie log 2 N. Somit rand5()hat sie ungefähr 2,32193 Entropiebits und rand7()ungefähr 2,80735 Entropiebits. Wenn wir die Zufälligkeit optimal nutzen möchten, müssen wir alle 2,32193 Entropiebits von jedem Aufruf an verwenden rand5()und sie auf die Erzeugung von 2,80735 Entropiebits anwenden, die für jeden Aufruf von erforderlich sind rand7(). Die grundlegende Grenze ist also, dass wir nicht besser als log (7) / log (5) = 1.20906 Anrufe rand5()pro Anruf an machen könnenrand7() .

Randnotizen: Alle Logarithmen in dieser Antwort sind Basis 2, sofern nicht anders angegeben. rand5()Es wird angenommen, dass Zahlen im Bereich [0, 4] zurückgegeben werden, und es rand7()wird angenommen, dass Zahlen im Bereich [0, 6] zurückgegeben werden. Das Anpassen der Bereiche auf [1, 5] bzw. [1, 7] ist trivial.

Wie machen wir das? Wir erzeugen eine unendlich genaue reelle Zufallszahl zwischen 0 und 1 (tun Sie so, als könnten wir tatsächlich eine so unendlich genaue Zahl berechnen und speichern - wir werden dies später beheben). Wir können eine solche Zahl erzeugen, indem wir ihre Ziffern in Basis 5 erzeugen: Wir wählen die Zufallszahl 0. a1 a2 a3 ..., wobei jede Ziffer a idurch einen Aufruf von ausgewählt wird rand5(). Wenn unser RNG beispielsweise a i= 1 für alle gewählt ihat und die Tatsache ignoriert, dass dies nicht sehr zufällig ist, würde dies der reellen Zahl 1/5 + 1/5 2 + 1/5 3 + ... = entsprechen 1/4 (Summe einer geometrischen Reihe).

Ok, wir haben also eine zufällige reelle Zahl zwischen 0 und 1 ausgewählt. Ich behaupte jetzt, dass eine solche zufällige Zahl gleichmäßig verteilt ist. Intuitiv ist dies leicht zu verstehen, da jede Ziffer einheitlich ausgewählt wurde und die Zahl unendlich genau ist. Ein formaler Beweis dafür ist jedoch etwas komplizierter, da es sich jetzt um eine kontinuierliche Verteilung anstelle einer diskreten Verteilung handelt. Daher müssen wir beweisen, dass die Wahrscheinlichkeit, dass unsere Zahl in einem Intervall [ a, b] liegt, gleich der Länge von ist dieses Intervall , b - a. Der Beweis bleibt als Übung für den Leser =).

Nachdem wir nun eine zufällige reelle Zahl einheitlich aus dem Bereich [0, 1] ausgewählt haben, müssen wir sie in eine Reihe einheitlich zufälliger Zahlen im Bereich [0, 6] umwandeln, um die Ausgabe von zu generieren rand7(). Wie machen wir das? Genau das Gegenteil von dem, was wir gerade getan haben - wir konvertieren es in eine unendlich genaue Dezimalstelle in Basis 7, und dann entspricht jede Ziffer von Basis 7 einer Ausgabe von rand7().

Wenn wir im Beispiel von früher rand5()einen unendlichen Strom von Einsen erzeugen, ist unsere zufällige reelle Zahl 1/4. Wenn wir 1/4 in Basis 7 konvertieren, erhalten wir die unendliche Dezimalzahl 0,15151515 ..., sodass wir als Ausgabe 1, 5, 1, 5, 1, 5 usw. erzeugen.

Ok, wir haben also die Hauptidee, aber wir haben noch zwei Probleme: Wir können keine unendlich genaue reelle Zahl berechnen oder speichern. Wie gehen wir also mit nur einem endlichen Teil davon um? Zweitens, wie konvertieren wir es tatsächlich in Basis 7?

Eine Möglichkeit, eine Zahl zwischen 0 und 1 in Basis 7 umzuwandeln, ist folgende:

  1. Mit 7 multiplizieren
  2. Der integrale Bestandteil des Ergebnisses ist die nächste 7-stellige Basis
  3. Subtrahieren Sie den Integralteil und lassen Sie nur den Bruchteil übrig
  4. Gehe zu Schritt 1

Um das Problem der unendlichen Genauigkeit zu lösen, berechnen wir ein Teilergebnis und speichern eine Obergrenze für das Ergebnis. Nehmen wir an, wir haben rand5()zweimal angerufen und es wurde beide Male 1 zurückgegeben. Die Zahl, die wir bisher generiert haben, ist 0,11 (Basis 5). Was auch immer der Rest der unendlichen Reihe von Aufrufen sein rand5()mag, die zufällige reelle Zahl, die wir erzeugen, wird niemals größer als 0,12 sein: Es ist immer wahr, dass 0,11 ≤ 0,11xyz ... <0,12.

Wenn wir also die aktuelle Zahl und den Maximalwert verfolgen, den es jemals annehmen könnte, konvertieren wir beide Zahlen in Basis 7. Wenn sie sich auf die ersten kZiffern einigen , können wir die nächsten kZiffern sicher ausgeben - unabhängig davon, welche Unendlicher Strom von Basis 5-Ziffern, sie werden niemals die nächsten kZiffern der Basis 7-Darstellung beeinflussen!

Und das ist der Algorithmus - um die nächste Ausgabe von zu generieren rand7(), generieren wir nur so viele Ziffern, rand5()wie wir benötigen, um sicherzustellen, dass wir den Wert der nächsten Ziffer bei der Konvertierung der reellen Zufallszahl in Basis 7 mit Sicherheit kennen eine Python-Implementierung mit einem Testgeschirr:

import random

rand5_calls = 0
def rand5():
    global rand5_calls
    rand5_calls += 1
    return random.randint(0, 4)

def rand7_gen():
    state = 0
    pow5 = 1
    pow7 = 7
    while True:
        if state / pow5 == (state + pow7) / pow5:
            result = state / pow5
            state = (state - result * pow5) * 7
            pow7 *= 7
            yield result
        else:
            state = 5 * state + pow7 * rand5()
            pow5 *= 5

if __name__ == '__main__':
    r7 = rand7_gen()
    N = 10000
    x = list(next(r7) for i in range(N))
    distr = [x.count(i) for i in range(7)]
    expmean = N / 7.0
    expstddev = math.sqrt(N * (1.0/7.0) * (6.0/7.0))

    print '%d TRIALS' % N
    print 'Expected mean: %.1f' % expmean
    print 'Expected standard deviation: %.1f' % expstddev
    print
    print 'DISTRIBUTION:'
    for i in range(7):
        print '%d: %d   (%+.3f stddevs)' % (i, distr[i], (distr[i] - expmean) / expstddev)
    print
    print 'Calls to rand5: %d (average of %f per call to rand7)' % (rand5_calls, float(rand5_calls) / N)

Beachten Sie, dass rand7_gen()ein Generator zurückgegeben wird, da er einen internen Status hat, der die Konvertierung der Zahl in Basis 7 beinhaltet. Das Testkabel ruft next(r7)10000 Mal auf, um 10000 Zufallszahlen zu erzeugen, und misst dann deren Verteilung. Es wird nur eine ganzzahlige Mathematik verwendet, sodass die Ergebnisse genau korrekt sind.

Beachten Sie auch, dass die Zahlen hier sehr groß werden, sehr schnell. Potenzen von 5 und 7 wachsen schnell. Daher wird sich die Leistung nach der Erzeugung vieler Zufallszahlen aufgrund der Bignum-Arithmetik merklich verschlechtern. Aber denken Sie daran, mein Ziel war es, die Verwendung von Zufallsbits zu maximieren, nicht die Leistung zu maximieren (obwohl dies ein sekundäres Ziel ist).

In einem Durchgang habe ich 12091 Anrufe rand5()für 10000 Anrufe getätigt rand7(), wobei das Minimum von log (7) / log (5) -Aufrufen im Durchschnitt auf 4 signifikante Zahlen erreicht wurde, und die resultierende Ausgabe war einheitlich.

Um diesen Code in eine Sprache zu portieren, in der keine beliebig großen Ganzzahlen integriert sind, müssen Sie die Werte pow5und pow7den Maximalwert Ihres nativen Integraltyps begrenzen. Wenn diese zu groß werden, setzen Sie sie zurück alles und von vorne anfangen. Dadurch wird die durchschnittliche Anzahl der Anrufe rand5()pro Anruf rand7()geringfügig erhöht, aber hoffentlich sollte sie auch bei 32- oder 64-Bit-Ganzzahlen nicht zu stark ansteigen.

Adam Rosenfield
quelle
7
+1 für eine wirklich interessante Antwort. Wäre es möglich, anstatt auf einen bestimmten Wert zurückzusetzen, einfach verwendete Bits zu verschieben und die anderen Bits nach oben zu verschieben und im Grunde nur die Bits beizubehalten, die verwendet werden sollen? Oder fehlt mir etwas?
Chris Lutz
1
Ich bin mir nicht 100% sicher, aber ich glaube, wenn Sie das tun würden, würden Sie die Verteilung ganz leicht verzerren (obwohl ich bezweifle, dass ein solcher Versatz ohne Billionen von Versuchen messbar wäre).
Adam Rosenfield
FTW! Ich habe versucht, die Bignums kleiner zu machen, aber das geht nicht, weil keine Potenz von 5 Faktoren mit einer Potenz von 7 gemeinsam hat! Auch eine gute Verwendung des Yield-Schlüsselworts. Sehr gut gemacht.
Eyal
2
Sehr schön! Können wir die zusätzliche Entropie behalten, ohne zu wachsen? Der Trick besteht darin, zu bemerken, dass sowohl die Ober- als auch die Untergrenze zu jeder Zeit rationale Zahlen sind. Wir können diese addieren, subtrahieren und multiplizieren, ohne an Präzision zu verlieren. Wenn wir alles in Base-35 machen, sind wir fast da. Der Rest (multipliziert mit sieben und Beibehalten des Bruchteils) bleibt als Übung übrig.
Ian
@adam Sie müssen sich auf "Begrenzen Sie die Werte von pow5 und pow7 auf den Maximalwert Ihres nativen Integraltyps" beziehen. Ich stimme Ihrer Überzeugung zu, dass dies die Verteilung verzerren wird, zumindest wenn dies naiv erfolgt.
Katalysator
36

(Ich habe die Antwort von Adam Rosenfeld gestohlen und sie um etwa 7% schneller laufen lassen.)

Angenommen, rand5 () gibt eines von {0,1,2,3,4} mit gleicher Verteilung zurück und das Ziel ist die Rückgabe von {0,1,2,3,4,5,6} mit gleicher Verteilung.

int rand7() {
  i = 5 * rand5() + rand5();
  max = 25;
  //i is uniform among {0 ... max-1}
  while(i < max%7) {
    //i is uniform among {0 ... (max%7 - 1)}
    i *= 5;
    i += rand5(); //i is uniform {0 ... (((max%7)*5) - 1)}
    max %= 7;
    max *= 5; //once again, i is uniform among {0 ... max-1}
  }
  return(i%7);
}

Wir verfolgen den größten Wert, den die Schleife in der Variablen erzeugen kann max. Wenn das bisherige Ergebnis zwischen max% 7 und max-1 liegt, wird das Ergebnis in diesem Bereich gleichmäßig verteilt. Wenn nicht, verwenden wir den Rest, der zufällig zwischen 0 und max% 7-1 liegt, und einen weiteren Aufruf von rand (), um eine neue Nummer und eine neue max. Dann fangen wir wieder an.

Bearbeiten: Erwarten Sie, wie oft rand5 () aufgerufen wird, ist x in dieser Gleichung:

x =  2     * 21/25
   + 3     *  4/25 * 14/20
   + 4     *  4/25 *  6/20 * 28/30
   + 5     *  4/25 *  6/20 *  2/30 * 7/10
   + 6     *  4/25 *  6/20 *  2/30 * 3/10 * 14/15
   + (6+x) *  4/25 *  6/20 *  2/30 * 3/10 *  1/15
x = about 2.21 calls to rand5()
Eyal
quelle
2
In 1.000.000 Versuchen katalogisierte Ergebnisse: 1 = 47216; 2 = 127444; 3 = 141407; 4 = 221453; 5 = 127479; 6 = 167536; 7 = 167465. Wie Sie sehen können, fehlt die Verteilung in Bezug auf die Wahrscheinlichkeit, eine 1 zu erhalten.
Robert K
2
@ The Wicked Flea: Ich denke, Sie irren sich. Sind Sie sicher, dass die Eingabe rand5 (), die Sie für Ihren Test verwendet haben, 0-4 anstelle von 1-5 ergab, wie in dieser Lösung angegeben?
Adam Rosenfield
5
Das Hinzufügen gleichmäßig verteilter Nummern führt nicht zu einer gleichmäßig verteilten Nummer. Tatsächlich müssen Sie nur 6 solcher gleichmäßig verteilten Variablen summieren, um eine vernünftige Annäherung an eine Normalverteilung zu erhalten.
Mitch Wheat
2
@MitchWheat - Das Hinzufügen von zwei gleichmäßig verteilten Ganzzahlen führt tatsächlich zu einer gleichmäßig verteilten Zufallszahl, vorausgesetzt, jede mögliche Summe kann auf genau eine Weise generiert werden. Das ist im Ausdruck der Fall 5 * rand5() + rand5().
Ted Hopp
28

Algorithmus:

7 kann in einer Folge von 3 Bits dargestellt werden

Verwenden Sie rand (5), um jedes Bit zufällig mit 0 oder 1 zu füllen.
Zum Beispiel: Rufen Sie rand (5) und auf

Wenn das Ergebnis 1 oder 2 ist, füllen Sie das Bit mit 0,
wenn das Ergebnis 4 oder 5 ist, füllen Sie das Bit mit 1,
wenn das Ergebnis 3 ist, ignorieren Sie es und wiederholen Sie es (Zurückweisung)

Auf diese Weise können wir 3 Bits zufällig mit 0/1 füllen und so eine Zahl von 1-7 erhalten.

EDIT: Dies scheint die einfachste und effizienteste Antwort zu sein. Hier ist ein Code dafür:

public static int random_7() {
    int returnValue = 0;
    while (returnValue == 0) {
        for (int i = 1; i <= 3; i++) {
            returnValue = (returnValue << 1) + random_5_output_2();
        }
    }
    return returnValue;
}

private static int random_5_output_2() {
    while (true) {
        int flip = random_5();

        if (flip < 3) {
            return 0;
        }
        else if (flip > 3) {
            return 1;
        }
    }
}
Lance Roberts
quelle
1
Es gibt immer das schwache Gespenst des Halteproblems, da ein schlechter Zufallszahlengenerator irgendwann einfach viele Dreien erzeugen könnte .
Alex North-Keys
"Wenn das Ergebnis 1 oder 2 ist, füllen Sie das Bit mit 0, wenn das Ergebnis 4 oder 5 ist, füllen Sie das Bit mit 1" Nach welcher Logik wurden 1,2,4,5 akzeptiert und 3 abgelehnt? Kannst du das erklären?
Gkns
@gkns Es gibt keine Logik, Sie könnten 1 und 2 mittlere Füllung mit 0 Bit und 3 und 4 mittlere Füllung mit 1 haben. Wichtig ist, dass jede Option eine 50% ige Wahrscheinlichkeit hat, aufzutreten, wodurch die Zufälligkeit Ihrer Funktion garantiert wird mindestens so zufällig wie die ursprüngliche Rand (5) -Funktion. Es ist eine großartige Lösung!
Mo Beigi
Dies ist weder einfach noch effizient. Die Anzahl der Cals zu random_5 pro random_7 beträgt bestenfalls 3 normalerweise mehr. Andere Lösungen auf dieser Seite sind näher an den tatsächlich besten, die bei 2,2 liegen.
Eyal
1
Trotzdem habe ich den Teil "while returnValue == 0" verpasst
NicholasFolk
19
int randbit( void )
{
    while( 1 )
    {
        int r = rand5();
        if( r <= 4 ) return(r & 1);
    }
}

int randint( int nbits )
{
    int result = 0;
    while( nbits-- )
    {
        result = (result<<1) | randbit();
    }
    return( result );
}

int rand7( void )
{
    while( 1 )
    {
        int r = randint( 3 ) + 1;
        if( r <= 7 ) return( r );
    }
}
Mike F.
quelle
2
Eine korrekte Lösung, die durchschnittlich 30/7 = 4,29 Aufrufe von rand5 () pro Aufruf von rand7 () ausführt.
Adam Rosenfield
17
rand7() = (rand5()+rand5()+rand5()+rand5()+rand5()+rand5()+rand5())%7+1

Edit: Das funktioniert nicht ganz. Es ist um ungefähr 2 Teile in 1000 (unter der Annahme eines perfekten Rand5). Die Eimer bekommen:

value   Count  Error%
1       11158  -0.0035
2       11144  -0.0214
3       11144  -0.0214
4       11158  -0.0035
5       11172  +0.0144
6       11177  +0.0208
7       11172  +0.0144

Durch Umschalten auf eine Summe von

n   Error%
10  +/- 1e-3,
12  +/- 1e-4,
14  +/- 1e-5,
16  +/- 1e-6,
...
28  +/- 3e-11

scheint für jede 2 hinzugefügten eine Größenordnung zu gewinnen

Übrigens: Die obige Fehlertabelle wurde nicht durch Stichproben generiert, sondern durch die folgende Wiederholungsrelation:

p[x,n]ist die Anzahl der Möglichkeiten output=x, die bei nAnrufen auftreten können rand5.

  p[1,1] ... p[5,1] = 1
  p[6,1] ... p[7,1] = 0

  p[1,n] = p[7,n-1] + p[6,n-1] + p[5,n-1] + p[4,n-1] + p[3,n-1]
  p[2,n] = p[1,n-1] + p[7,n-1] + p[6,n-1] + p[5,n-1] + p[4,n-1]
  p[3,n] = p[2,n-1] + p[1,n-1] + p[7,n-1] + p[6,n-1] + p[5,n-1]
  p[4,n] = p[3,n-1] + p[2,n-1] + p[1,n-1] + p[7,n-1] + p[6,n-1]
  p[5,n] = p[4,n-1] + p[3,n-1] + p[2,n-1] + p[1,n-1] + p[7,n-1]
  p[6,n] = p[5,n-1] + p[4,n-1] + p[3,n-1] + p[2,n-1] + p[1,n-1]
  p[7,n] = p[6,n-1] + p[5,n-1] + p[4,n-1] + p[3,n-1] + p[2,n-1]
BCS
quelle
8
Dies ist keine gleichmäßige Verteilung. Es ist sehr nahe an der Uniform, aber nicht perfekt einheitlich.
Adam Rosenfield
Ah! Würfel und 7er. Wenn Sie sagen wollen, dass ich falsch liege, sollten Sie den Beweis nicht als Übung für den Leser hinterlassen.
BCS
45
Der Beweis, dass es nicht einheitlich ist, ist einfach: Es gibt 5 ^ 7 mögliche Wege, wie die Zufälligkeit gehen kann, und da 5 ^ 7 kein Vielfaches von 7 ist, ist es nicht möglich, dass alle 7 Summen gleich wahrscheinlich sind. (Grundsätzlich läuft es darauf hinaus, dass 7 relativ prim zu 5 ist oder äquivalent 1/7 keine abschließende Dezimalstelle in Basis 5 ist.) Tatsächlich ist es unter dieser Bedingung nicht einmal die "einheitlichste", die möglich ist: Die direkte Berechnung zeigt die der 5 ^ 7 = 78125 Summen, die Häufigkeit, mit der Sie die Werte 1 bis 7 erhalten, beträgt {1: 11145, 2: 11120, 3: 11120, 4: 11145, 5: 11190, 6: 11215, 7: 11190}.
ShreevatsaR
@ShreevatsaR Was wäre, wenn wir nicht sieben Mal die Summe von rand5 () nehmen würden, sondern 5 * 7 - würde das nicht funktionieren? 35 ^ 7% 7 = 35 ^ 5% 7 = 0.
kba
4
@KristianAntonsen: Wie oft Sie rand5 () ausführen, erhalten Sie keine einheitliche Verteilung. Wenn Sie es N-mal machen, gibt es 5 ^ N mögliche Ausgänge, die nicht durch 7 teilbar sind. (Wenn Sie es 35-mal machen, gibt es 5 ^ 35, nicht 35 ^ 7.) Sie kommen immer näher einheitlich die größere Anzahl von Anrufen, die Sie verwenden (und es kann eine beliebige Anzahl sein, muss nicht durch 7 teilbar sein), aber IMHO, anstatt eine sehr große Anzahl von Anrufen für rand () zu verwenden, können Sie auch die Wahrscheinlichkeit verwenden Algorithmus in den oberen Antworten, der eine exakte Gleichverteilung ergibt und dessen erwartete Anzahl von Aufrufen von rand () gering ist.
ShreevatsaR
15
int ans = 0;
while (ans == 0) 
{
     for (int i=0; i<3; i++) 
     {
          while ((r = rand5()) == 3){};
          ans += (r < 3) >> i
     }
}
Nescio
quelle
2
Eine korrekte Lösung, die durchschnittlich 30/7 = 4,29 Aufrufe von rand5 () pro Aufruf von rand7 () ausführt.
Adam Rosenfield
3
Bedürfnisse sein Linksverschiebung : für den Algorithmus zur Arbeitans += (r < 3) << i
woolfie
13

Das Folgende erzeugt eine gleichmäßige Verteilung auf {1, 2, 3, 4, 5, 6, 7} unter Verwendung eines Zufallszahlengenerators, der eine gleichmäßige Verteilung auf {1, 2, 3, 4, 5} erzeugt. Der Code ist chaotisch, aber die Logik ist klar.

public static int random_7(Random rg) {
    int returnValue = 0;
    while (returnValue == 0) {
        for (int i = 1; i <= 3; i++) {
            returnValue = (returnValue << 1) + SimulateFairCoin(rg);
        }
    }
    return returnValue;
}

private static int SimulateFairCoin(Random rg) {
    while (true) {
        int flipOne = random_5_mod_2(rg);
        int flipTwo = random_5_mod_2(rg);

        if (flipOne == 0 && flipTwo == 1) {
            return 0;
        }
        else if (flipOne == 1 && flipTwo == 0) {
            return 1;
        }
    }
}

private static int random_5_mod_2(Random rg) {
    return random_5(rg) % 2;
}

private static int random_5(Random rg) {
    return rg.Next(5) + 1;
}    
Jason
quelle
2
Eine korrekte Lösung (die Sie der Kurve weit voraus bringt), wenn auch nicht sehr effizient. Dies ergibt einen Durchschnitt von 25/6 = 4,17 Aufrufen von random_5_mod_2 pro fairem Münzwurf, für einen Gesamtdurchschnitt von 100/7 = 14,3 Aufrufen von random_5 () pro Aufruf von random_7 ().
Adam Rosenfield
Der Vorteil dieser Lösung gegenüber den anderen besteht darin, dass sie leicht erweitert werden kann, um einen anderen gleichmäßig verteilten Bereich zu erzeugen. Wählen Sie einfach zufällig jedes der Bits aus und rollen Sie erneut auf ungültigen Werten (wie dem 0-Wert in unserer aktuellen Lösung, der 8 Zahlen erzeugt).
DenTheMan
1
mögliche Endlosschleifen usw.
Robermorales
1
@romormorales: Sehr unwahrscheinlich.
Jason
13
int rand7() {
    int value = rand5()
              + rand5() * 2
              + rand5() * 3
              + rand5() * 4
              + rand5() * 5
              + rand5() * 6;
    return value%7;
}

Im Gegensatz zur gewählten Lösung wird der Algorithmus in konstanter Zeit ausgeführt. Rand5 wird jedoch 2 Mal mehr aufgerufen als die durchschnittliche Laufzeit der ausgewählten Lösung.

Beachten Sie, dass dieser Generator nicht perfekt ist (die Zahl 0 hat eine um 0,0064% höhere Wahrscheinlichkeit als jede andere Zahl), aber für die meisten praktischen Zwecke überwiegt die Garantie einer konstanten Zeit wahrscheinlich diese Ungenauigkeit.

Erläuterung

Diese Lösung ergibt sich aus der Tatsache, dass die Zahl 15.624 durch 7 teilbar ist. Wenn wir also zufällig und gleichmäßig Zahlen von 0 bis 15.624 erzeugen und dann Mod 7 nehmen können, können wir einen nahezu einheitlichen rand7-Generator erhalten. Zahlen von 0 bis 15.624 können einheitlich erzeugt werden, indem rand5 sechsmal gewürfelt und daraus die Ziffern einer Basis-5-Zahl wie folgt gebildet werden:

rand5 * 5^5 + rand5 * 5^4 + rand5 * 5^3 + rand5 * 5^2 + rand5 * 5 + rand5

Die Eigenschaften von Mod 7 erlauben es uns jedoch, die Gleichung ein wenig zu vereinfachen:

5^5 = 3 mod 7
5^4 = 2 mod 7
5^3 = 6 mod 7
5^2 = 4 mod 7
5^1 = 5 mod 7

Damit

rand5 * 5^5 + rand5 * 5^4 + rand5 * 5^3 + rand5 * 5^2 + rand5 * 5 + rand5

wird

rand5 * 3 + rand5 * 2 + rand5 * 6 + rand5 * 4 + rand5 * 5 + rand5

Theorie

Die Zahl 15.624 wurde nicht zufällig ausgewählt, sondern kann mit dem kleinen Satz von Fermat entdeckt werden, der besagt, dass wenn p eine Primzahl ist, dann

a^(p-1) = 1 mod p

Das gibt uns also,

(5^6)-1 = 0 mod 7

(5 ^ 6) -1 ist gleich

4 * 5^5 + 4 * 5^4 + 4 * 5^3 + 4 * 5^2 + 4 * 5 + 4

Dies ist eine Zahl in Basis 5-Form, und daher können wir sehen, dass diese Methode verwendet werden kann, um von einem beliebigen Zufallszahlengenerator zu einem anderen Zufallszahlengenerator zu wechseln. Bei Verwendung des Exponenten p-1 wird jedoch immer eine kleine Vorspannung in Richtung 0 eingeführt.

Um diesen Ansatz zu verallgemeinern und genauer zu sein, können wir eine Funktion wie diese haben:

def getRandomconverted(frm, to):
    s = 0
    for i in range(to):
        s += getRandomUniform(frm)*frm**i
    mx = 0
    for i in range(to):
        mx = (to-1)*frm**i 
    mx = int(mx/to)*to # maximum value till which we can take mod
    if s < mx:
        return s%to
    else:
        return getRandomconverted(frm, to)
Thirlan
quelle
1
Dieser Generator ist genau, aber nicht perfekt gleichmäßig. Um dies zu sehen, bedenken Sie die Tatsache, dass ein einheitlicher Generator in [0,15624] 15625 mögliche Ergebnisse hat, die nicht durch 7 teilbar sind. Dies führt zu einer Verzerrung der Zahl 0 (die eine Chance von 2233/15625 hat, und der anderen nur 2232/15625). Während die Verwendung von Fermats kleinem Theorem auf den ersten Blick richtig erscheint, heißt es schließlich, dass (5 ^ 6)% 7 = 1 und nicht (5 ^ 6)% 7 = 0. Letzteres ist für jeden Exponenten offensichtlich unmöglich, da 5 und 7 beide Primzahlen sind. Ich denke, es ist immer noch eine akzeptable Lösung, und ich habe Ihren Beitrag bearbeitet, um dies widerzuspiegeln.
Flieger
12

Sind hier Hausaufgabenprobleme erlaubt?

Diese Funktion berechnet grob "Basis 5", um eine Zahl zwischen 0 und 6 zu generieren.

function rnd7() {
    do {
        r1 = rnd5() - 1;
        do {
            r2=rnd5() - 1;
        } while (r2 > 1);
        result = r2 * 5 + r1;
    } while (result > 6);
    return result + 1;
}
Will Hartung
quelle
3
Eine korrekte Lösung (die Sie der Kurve weit voraus bringt), wenn auch nicht sehr effizient. Dies führt zu durchschnittlich 5 Aufrufen von rnd5 () für jeden Aufruf von rnd7 ().
Adam Rosenfield
brauche noch eine Erklärung pls
Barry
1
@Barry - Erstens können Sie nicht einfach zwei Zufallszahlen addieren, Sie erhalten keine lineare Lösung (betrachten Sie ein Würfelpaar). Betrachten Sie nun "Basis 5": 00, 01, 02, 03, 04, 10, 11. Diese 0-6 in Basis 5. Wir müssen also einfach 2 Ziffern der Basis 5-Nummer generieren und diese addieren, bis wir Holen Sie sich eine, die in Reichweite ist. Das macht der r2 * 5 + r1. Die r2> 1-Schleife ist da, weil wir niemals eine hohe Ziffer von> 1 wollen würden.
Will Hartung
Diese Lösung erzeugt keine gleichmäßige Verteilung. Die Zahlen 1 und 7 können nur auf eine Weise erzeugt werden, aber 2 bis 6 können jeweils auf zwei Arten erzeugt werden: mit r1 gleich der Zahl minus 1 und r2 gleich 0 oder mit r1 gleich der Zahl minus 2 und r2 gleich 1. Somit werden 2 bis 6 durchschnittlich doppelt so oft wie 1 oder 7 zurückgegeben.
Ted Hopp
12

Wenn wir die zusätzliche Einschränkung betrachten, zu versuchen, die effizienteste Antwort zu geben, dh eine, die bei einem Eingabestream Ivon gleichmäßig verteilten Ganzzahlen mit einer Länge mvon 1 bis 5 einen Strom Ovon gleichmäßig verteilten Ganzzahlen von 1 bis 7 der längsten relativen Länge ausgibt zu msagen L(m).

Der einfachste Weg, dies zu analysieren, besteht darin, die Ströme I und Oals 5-ary- bzw. 7-ary-Zahlen zu behandeln. Dies wird durch die Idee der Hauptantwort erreicht, den Stream a1, a2, a3,... -> a1+5*a2+5^2*a3+..und ähnlich für den Stream zu nehmen O.

Dann nehmen wir einen Abschnitt des Eingabestreams mit der Länge, m choose n s.t. 5^m-7^n=cwo c>0und ist so klein wie möglich. Dann gibt es eine einheitliche Abbildung vom Eingabestrom der Länge m auf Ganzzahlen von 1bis 5^mund eine weitere einheitliche Abbildung von Ganzzahlen von 1 bis 7^nzum Ausgabestrom der Länge n, bei der wir möglicherweise einige Fälle aus dem Eingabestream verlieren müssen, wenn die Ganzzahl abgebildet wird überschreitet 7^n.

Dies ergibt also einen Wert für L(m)ungefähr, m (log5/log7)der ungefähr ist .82m.

Die Schwierigkeit bei der obigen Analyse ist die Gleichung, 5^m-7^n=cdie nicht einfach genau zu lösen ist, und der Fall, in dem der einheitliche Wert von 1bis 5^mübersteigt 7^nund wir an Effizienz verlieren.

Die Frage ist, wie nahe der bestmögliche Wert von m (log5 / log7) erreicht werden kann. Wenn sich diese Zahl beispielsweise einer Ganzzahl nähert, können wir dann einen Weg finden, um diese exakte ganzzahlige Anzahl von Ausgabewerten zu erreichen?

Wenn 5^m-7^n=cwir dann aus dem Eingabestream effektiv eine einheitliche Zufallszahl von 0bis generieren (5^m)-1und keine höheren Werte als verwenden 7^n. Diese Werte können jedoch gerettet und erneut verwendet werden. Sie erzeugen effektiv eine einheitliche Folge von Zahlen von 1 bis 5^m-7^n. Wir können dann versuchen, diese zu verwenden und sie in 7-fache Zahlen umzuwandeln, damit wir mehr Ausgabewerte erstellen können.

Wenn wir T7(X)die durchschnittliche Länge der Ausgabesequenz von random(1-7)ganzen Zahlen sein wollen, die aus einer einheitlichen Eingabe der Größe abgeleitet sind X, und dies annehmen 5^m=7^n0+7^n1+7^n2+...+7^nr+s, s<7.

Dann T7(5^m)=n0x7^n0/5^m + ((5^m-7^n0)/5^m) T7(5^m-7^n0)haben wir, da wir eine Länge haben, keine Folge mit der Wahrscheinlichkeit 7 ^ n0 / 5 ^ m mit einem Rest der Länge 5^m-7^n0mit der Wahrscheinlichkeit (5^m-7^n0)/5^m).

Wenn wir einfach weiter ersetzen, erhalten wir:

T7(5^m) = n0x7^n0/5^m + n1x7^n1/5^m + ... + nrx7^nr/5^m  = (n0x7^n0 + n1x7^n1 + ... + nrx7^nr)/5^m

Daher

L(m)=T7(5^m)=(n0x7^n0 + n1x7^n1 + ... + nrx7^nr)/(7^n0+7^n1+7^n2+...+7^nr+s)

Eine andere Art, dies auszudrücken, ist:

If 5^m has 7-ary representation `a0+a1*7 + a2*7^2 + a3*7^3+...+ar*7^r
Then L(m) = (a1*7 + 2a2*7^2 + 3a3*7^3+...+rar*7^r)/(a0+a1*7 + a2*7^2 + a3*7^3+...+ar*7^r)

Der bestmögliche Fall ist mein Original oben wo 5^m=7^n+s, wo s<7.

Dann T7(5^m) = nx(7^n)/(7^n+s) = n+o(1) = m (Log5/Log7)+o(1)wie zuvor.

Der schlimmste Fall ist, wenn wir nur k und st 5 ^ m = kx7 + s finden können.

Then T7(5^m) = 1x(k.7)/(k.7+s) = 1+o(1)

Andere Fälle liegen irgendwo dazwischen. Es wäre interessant zu sehen, wie gut wir für sehr große m abschneiden können, dh wie gut wir den Fehlerterm erhalten können:

T7(5^m) = m (Log5/Log7)+e(m)

Es scheint e(m) = o(1)im Allgemeinen unmöglich zu erreichen, aber wir können es hoffentlich beweisen e(m)=o(m).

Das Ganze beruht dann auf der Verteilung der 7-stelligen Ziffern von 5^mfür verschiedene Werte von m.

Ich bin mir sicher, dass es da draußen eine Menge Theorie gibt, die dies abdeckt. Ich werde vielleicht irgendwann einen Blick darauf werfen und darüber berichten.

Ivan
quelle
+2 (wenn ich könnte) - dies war die einzig gute Antwort (im Gegensatz zu nur angemessen). Sie haben die zweitbeste Antwort, die in 32-Bit-Ganzzahlen passt.
Rex Kerr
10

Hier ist eine funktionierende Python-Implementierung von Adams Antwort .

import random

def rand5():
    return random.randint(1, 5)

def rand7():
    while True:
        r = 5 * (rand5() - 1) + rand5()
        #r is now uniformly random between 1 and 25
        if (r <= 21):
            break
    #result is now uniformly random between 1 and 7
    return r % 7 + 1

Ich mag es, Algorithmen, die ich mir anschaue, in Python zu werfen, damit ich mit ihnen herumspielen kann. Ich dachte, ich würde sie hier veröffentlichen, in der Hoffnung, dass es für jemanden da draußen nützlich ist, nicht dass es lange gedauert hat, sie zusammen zu werfen.

James McMahon
quelle
Nein, das ist ganz anders als meine Antwort. Sie durchlaufen 21 Schleifen und verwerfen die Ergebnisse der ersten 20 Iterationen. Sie verwenden auch ein rand4 () und ein rand5 () als Eingabe, was ganz offensichtlich gegen die Regeln verstößt, nur rand5 () zu verwenden. Schließlich erzeugen Sie eine ungleichmäßige Verteilung.
Adam Rosenfield
Das tut mir leid. Ich war ziemlich müde, als ich diese Frage durchgesehen habe, müde genug, dass ich Ihren Algorithmus völlig falsch verstanden habe. Ich habe es tatsächlich in Python geworfen, weil ich nicht verstehen konnte, warum Sie 21 Mal geloopt haben. Macht jetzt viel mehr Sinn. Ich habe das Random.Randint (1, 4) -Ding als Abkürzung verwendet, aber ich denke, Sie haben Recht, es ist gegen den Geist der Frage. Ich habe den Code korrigiert.
James McMahon
@robermorales - Wie Adam Rosenfeld in seiner Antwort erklärte , beinhaltet jede Lösung, die eine echte Gleichverteilung auf [1, 7] ergibt, eine Art Akzeptanz-Ablehnungs-Schleife, die möglicherweise unendlich ist. (Wenn rand5()es sich jedoch um ein anständiges PRNG handelt, ist die Schleife nicht unendlich, da sie letztendlich 5*(rand5() - 1) + rand5()definitiv <= 21 sein wird.)
Ted Hopp
10

Warum nicht einfach?

int random7() {
  return random5() + (random5() % 3);
}

Die Wahrscheinlichkeit, in dieser Lösung 1 und 7 zu erhalten, ist aufgrund des Modulos geringer. Wenn Sie jedoch nur eine schnelle und lesbare Lösung wünschen, ist dies der richtige Weg.

Ante
quelle
13
Dies führt nicht zu einer gleichmäßigen Verteilung. Dies ergibt die Zahlen 0-6 mit den Wahrscheinlichkeiten 2/25, 4/25, 5/25, 5/25, 5/25, 3/25, 1/25, was durch Zählen aller 25 möglichen Ergebnisse überprüft werden kann.
Adam Rosenfield
8

Unter der Annahme, dass Rand (n) hier "zufällige Ganzzahl in einer gleichmäßigen Verteilung von 0 bis n-1 " bedeutet, ist hier ein Codebeispiel unter Verwendung von Pythons Randint, das diesen Effekt hat. Es werden nur Randint (5) und Konstanten verwendet, um den Effekt von Randint (7) zu erzeugen . Eigentlich ein bisschen albern

from random import randint
sum = 7
while sum >= 7:
    first = randint(0,5)   
    toadd = 9999
    while toadd>1:
        toadd = randint(0,5)
    if toadd:
        sum = first+5
    else:
        sum = first

assert 7>sum>=0 
print sum
Joshua Fox
quelle
1
@robermorales Weil Python nicht hat do ... while. Es hätte 1337, oder 12345, oder eine beliebige Anzahl> 1.
Doorknob
8

Die Voraussetzung für die richtige Antwort von Adam Rosenfield lautet:

  • x = 5 ^ n (in seinem Fall: n = 2)
  • Manipuliere n rand5-Aufrufe, um eine Zahl y innerhalb des Bereichs [1, x] zu erhalten.
  • z = ((int) (x / 7)) * 7
  • Wenn y> z, versuchen Sie es erneut. Andernfalls wird y% 7 + 1 zurückgegeben

Wenn n gleich 2 ist, haben Sie 4 Wegwerfmöglichkeiten: y = {22, 23, 24, 25}. Wenn Sie n gleich 6 verwenden, haben Sie nur 1 Wegwerfartikel: y = {15625}.

5 ^ 6 = 15625
7 * 2232 = 15624

Sie rufen rand5 noch öfter an. Sie haben jedoch eine viel geringere Chance, einen Wegwerfwert (oder eine Endlosschleife) zu erhalten. Wenn es eine Möglichkeit gibt, keinen möglichen Wegwerfwert für y zu erhalten, habe ich ihn noch nicht gefunden.

Dinah
quelle
1
Es gibt nachweislich keinen Fall ohne Wegwerfwerte - wenn es keinen Wegwerfwert gäbe, hätten 5 ^ n und 7 ^ m einen gemeinsamen Faktor. Aber sie sind (Kräfte von) Primzahlen, also nicht.
Rex Kerr
8

Hier ist meine Antwort:

static struct rand_buffer {
  unsigned v, count;
} buf2, buf3;

void push (struct rand_buffer *buf, unsigned n, unsigned v)
{
  buf->v = buf->v * n + v;
  ++buf->count;
}

#define PUSH(n, v)  push (&buf##n, n, v)

int rand16 (void)
{
  int v = buf2.v & 0xf;
  buf2.v >>= 4;
  buf2.count -= 4;
  return v;
}

int rand9 (void)
{
  int v = buf3.v % 9;
  buf3.v /= 9;
  buf3.count -= 2;
  return v;
}

int rand7 (void)
{
  if (buf3.count >= 2) {
    int v = rand9 ();

    if (v < 7)
      return v % 7 + 1;

    PUSH (2, v - 7);
  }

  for (;;) {
    if (buf2.count >= 4) {
      int v = rand16 ();

      if (v < 14) {
        PUSH (2, v / 7);
        return v % 7 + 1;
      }

      PUSH (2, v - 14);
    }

    // Get a number between 0 & 25
    int v = 5 * (rand5 () - 1) + rand5 () - 1;

    if (v < 21) {
      PUSH (3, v / 7);
      return v % 7 + 1;
    }

    v -= 21;
    PUSH (2, v & 1);
    PUSH (2, v >> 1);
  }
}

Es ist etwas komplizierter als andere, aber ich glaube, es minimiert die Aufrufe von rand5. Wie bei anderen Lösungen besteht eine geringe Wahrscheinlichkeit, dass es zu einer langen Schleife kommt.

Chris Suter
quelle
Dies führt zu einer Verteilung, die sich nicht wesentlich von den anderen Lösungen unterscheidet, hat jedoch den zusätzlichen Nachteil, dass sie unnötig komplex ist. Es leidet auch unter der nachweislich falschen Möglichkeit einer nicht deterministischen Schleife für immer, wenn die Zahlen wirklich zufällig sind. Ich denke immer noch, dass diejenigen, die eine etwas weniger gleichmäßige Verteilung erzeugen (obwohl immer noch weit mehr als ausreichend), aber deterministisches Verhalten garantieren, besser sind.
Paxdiablo
@Pax: Bitte klären Sie mich auf, wie dies zu einer ungleichmäßigen Verteilung führt. Meine Analyse des Codes sowie meine eigenen Tests zeigen, dass dies zu einer gleichmäßigen Verteilung führt. Wie bereits erwähnt, ist es unmöglich, sowohl eine perfekt gleichmäßige Verteilung als auch eine garantierte Obergrenze der Laufzeit mit konstanter Zeit zu erzielen.
Adam Rosenfield
7

Einfach und effizient:

int rand7 ( void )
{
    return 4; // this number has been calculated using
              // rand5() and is in the range 1..7
}

(Inspiriert von Was ist dein Lieblings-Cartoon "Programmierer"? ).

Chiccodoro
quelle
6

Solange nicht mehr sieben Möglichkeiten zur Auswahl stehen, ziehen Sie eine weitere Zufallszahl, die die Anzahl der Möglichkeiten mit fünf multipliziert. In Perl:

$num = 0;
$possibilities = 1;

sub rand7
{
  while( $possibilities < 7 )
  {
    $num = $num * 5 + int(rand(5));
    $possibilities *= 5;
  }
  my $result = $num % 7;
  $num = int( $num / 7 );
  $possibilities /= 7;
  return $result;
}
user223264
quelle
Ihre Verteilung ist zumindest beim ersten Anruf nicht einheitlich. In der Tat $possibilitiesmuss immer auf 25 wachsen, um die Schleife zu verlassen und zurückzukehren. Ihr erstes Ergebnis ist also [0-124] % 7, dass es nicht gleichmäßig verteilt ist, weil 125 % 7 != 0(dies ist tatsächlich 6).
Bernard Paulus
6

Ich mag keine Bereiche ab 1, also fange ich bei 0 an :-)

unsigned rand5()
{
    return rand() % 5;
}

unsigned rand7()
{
    int r;

    do
    {
        r =         rand5();
        r = r * 5 + rand5();
        r = r * 5 + rand5();
        r = r * 5 + rand5();
        r = r * 5 + rand5();
        r = r * 5 + rand5();
    } while (r > 15623);

    return r / 2232;
}
Fredoverflow
quelle
Dies ist ein Gewinner. Dies ergibt alle 7 Ergebnisse mit gleicher Wahrscheinlichkeit. from collections import defaultdict def r7(n): if not n: yield [] else: for i in range(1, 6): for j in r7(n-1): yield [i] + j def test_r7(): d = defaultdict(int) for x in r7(6): s = (((((((((x[5] * 5) + x[4]) * 5) + x[3]) * 5) + x[2]) * 5) + x[1]) * 5) + x[0] if s <= 15623: d[s % 7] += 1 print d
Hughdbrown
5

Los geht's, gleichmäßige Verteilung und null Rand5-Anrufe.

def rand7:
    seed += 1
    if seed >= 7:
        seed = 0
    yield seed

Das Saatgut muss vorher gesetzt werden.

Kugel
quelle
5

Ich weiß, dass es beantwortet wurde, aber scheint das in Ordnung zu sein, aber ich kann Ihnen nicht sagen, ob es eine Voreingenommenheit hat. Meine "Tests" legen nahe, dass dies zumindest vernünftig ist.

Vielleicht wäre Adam Rosenfield so freundlich, einen Kommentar abzugeben?

Meine (naive?) Idee ist folgende:

Akkumulieren Sie rand5, bis genügend zufällige Bits vorhanden sind, um einen rand7 zu erstellen. Dies dauert höchstens 2 Rand5. Um die rand7 Nummer zu bekommen, benutze ich den akkumulierten Wert mod 7.

Um zu vermeiden, dass der Akku überläuft, und da der Akku Mod 7 ist, nehme ich den Mod 7 des Akkus:

(5a + rand5) % 7 = (k*7 + (5a%7) + rand5) % 7 = ( (5a%7) + rand5) % 7

Die Funktion rand7 () folgt:

(Ich lasse den Bereich von rand5 0-4 sein und rand7 ist ebenfalls 0-6.)

int rand7(){
  static int    a=0;
  static int    e=0;
  int       r;
  a = a * 5 + rand5();
  e = e + 5;        // added 5/7ths of a rand7 number
  if ( e<7 ){
    a = a * 5 + rand5();
    e = e + 5;  // another 5/7ths
  }
  r = a % 7;
  e = e - 7;        // removed a rand7 number
  a = a % 7;
  return r;
}

Bearbeiten: Ergebnisse für 100 Millionen Versuche hinzugefügt.

'Real' Rand Funktionen Mod 5 oder 7

rand5: avg = 1.999802 0: 20003944 1: 19999889 2: 20003690 3: 19996938 4: 19995539 rand7: avg = 3.000111 0: 14282851 1: 14282879 2: 14284554 3: 14288546 4: 14292388 5: 14288736 6: 14280046

Mein rand7

Durchschnitt sieht gut aus und Zahlenverteilungen sehen auch gut aus.

randt: avg = 3.000080 0: 14288793 1: 14280135 2: 14287848 3: 14285277 4: 14286341 5: 14278663 6: 14292943

philcolbourn
quelle
Sie sollten sich wahrscheinlich die sequentielle Korrelation ansehen. Ich denke, wenn Sie aufeinanderfolgende Paare nehmen (jede "Zufallszahl" gepaart mit ihrem Vorgänger), werden Sie vielleicht überraschende Dinge finden. Sie haben nicht erklärt, warum die Verteilung auf jeden Fall einheitlich bleiben sollte. Ein Arbeitsprogramm sollte normalerweise mit einer Erklärung beginnen, warum es funktioniert.
Ian
Würde die sequentielle Korrelation für viele dieser Lösungen gelten?
Philcolbourn
Würde die sequentielle Korrelation für viele dieser Lösungen gelten? Es ist eine Weile her, seit ich das versucht habe und ich dachte, ich hätte es erklärt. Wenn ich es mir jetzt ansehe, sieht es so aus, als würde ich zufällige Bits in einem Pool von rand5 akkumulieren, um sicherzustellen, dass genug akkumuliert wurden, bevor ich genug zurückziehe, um eine rand7-Zahl zu erstellen, und um sicherzustellen, dass mein Akkumulator nicht überläuft.
Philcolbourn
4

Es gibt elegante Algorithmen, die oben zitiert wurden, aber hier ist eine Möglichkeit, sich dem anzunähern, obwohl es sich um einen Kreisverkehr handeln könnte. Ich gehe von Werten aus, die aus 0 generiert wurden.

R2 = Zufallszahlengenerator mit Werten unter 2 (Stichprobenraum = {0, 1})
R8 = Zufallszahlengenerator mit Werten unter 8 (Stichprobenraum = {0, 1, 2, 3, 4, 5, 6, 7) })

Um R8 aus R2 zu generieren, führen Sie R2 dreimal aus und verwenden das kombinierte Ergebnis aller 3 Läufe als Binärzahl mit 3 Ziffern. Hier ist der Wertebereich, wenn R2 dreimal ausgeführt wird:

0 0 0 -> 0
.
.
1 1 1 -> 7

Um nun R7 aus R8 zu generieren, führen wir R7 einfach erneut aus, wenn es 7 zurückgibt:

int R7() {
  do {
    x = R8();
  } while (x > 6)
  return x;
}

Die Kreisverkehrslösung besteht darin, R2 aus R5 zu generieren (genau wie wir R7 aus R8 generiert haben), dann R8 aus R2 und dann R7 aus R8.

Ashwin
quelle
Wie bei vielen anderen kann dieser Ansatz pro R7-Aufruf beliebig lange dauern, da R8 eine lange Reihe von Siebenen abrufen kann.
Alex North-Keys
4

Hier ist eine Lösung, die vollständig in ganze Zahlen passt und innerhalb von etwa 4% des Optimums liegt (dh 1,26 Zufallszahlen in {0..4} für jede in {0..6} verwendet). Der Code ist in Scala, aber die Mathematik sollte in jeder Sprache einigermaßen klar sein: Sie nutzen die Tatsache, dass 7 ^ 9 + 7 ^ 8 sehr nahe an 5 ^ 11 liegt. Sie wählen also eine 11-stellige Zahl in Basis 5 aus und interpretieren sie dann als 9-stellige Zahl in Basis 7, wenn sie sich im Bereich befindet (9 Basis-7-Zahlen), oder als 8-stellige Zahl, wenn sie über der 9-stelligen Zahl liegt .:

abstract class RNG {
  def apply(): Int
}

class Random5 extends RNG {
  val rng = new scala.util.Random
  var count = 0
  def apply() = { count += 1 ; rng.nextInt(5) }
}

class FiveSevener(five: RNG) {
  val sevens = new Array[Int](9)
  var nsevens = 0
  val to9 = 40353607;
  val to8 = 5764801;
  val to7 = 823543;
  def loadSevens(value: Int, count: Int) {
    nsevens = 0;
    var remaining = value;
    while (nsevens < count) {
      sevens(nsevens) = remaining % 7
      remaining /= 7
      nsevens += 1
    }
  }
  def loadSevens {
    var fivepow11 = 0;
    var i=0
    while (i<11) { i+=1 ; fivepow11 = five() + fivepow11*5 }
    if (fivepow11 < to9) { loadSevens(fivepow11 , 9) ; return }
    fivepow11 -= to9
    if (fivepow11 < to8) { loadSevens(fivepow11 , 8) ; return }
    fivepow11 -= to8
    if (fivepow11 < 3*to7) loadSevens(fivepow11 % to7 , 7)
    else loadSevens
  }
  def apply() = {
    if (nsevens==0) loadSevens
    nsevens -= 1
    sevens(nsevens)
  }
}

Wenn Sie einen Test in den Interpreter einfügen (tatsächlich REPL), erhalten Sie:

scala> val five = new Random5
five: Random5 = Random5@e9c592

scala> val seven = new FiveSevener(five)
seven: FiveSevener = FiveSevener@143c423

scala> val counts = new Array[Int](7)
counts: Array[Int] = Array(0, 0, 0, 0, 0, 0, 0)

scala> var i=0 ; while (i < 100000000) { counts( seven() ) += 1 ; i += 1 }
i: Int = 100000000

scala> counts
res0: Array[Int] = Array(14280662, 14293012, 14281286, 14284836, 14287188,
14289332, 14283684)

scala> five.count
res1: Int = 125902876

Die Verteilung ist schön und flach (innerhalb von etwa 10k von 1/7 von 10 ^ 8 in jedem Bin, wie von einer ungefähr-Gaußschen Verteilung erwartet).

Rex Kerr
quelle
3

Mit einer rollierenden Summe können Sie beides

  • eine gleichmäßige Verteilung aufrechterhalten; und
  • Sie müssen kein Element in der zufälligen Reihenfolge opfern.

Diese beiden Probleme sind ein Problem bei den rand(5)+rand(5)...Lösungen vom simplen Typ. Der folgende Python-Code zeigt, wie er implementiert wird (das meiste davon beweist die Verteilung).

import random
x = []
for i in range (0,7):
    x.append (0)
t = 0
tt = 0
for i in range (0,700000):
    ########################################
    #####            qq.py             #####
    r = int (random.random () * 5)
    t = (t + r) % 7
    ########################################
    #####       qq_notsogood.py        #####
    #r = 20
    #while r > 6:
        #r =     int (random.random () * 5)
        #r = r + int (random.random () * 5)
    #t = r
    ########################################
    x[t] = x[t] + 1
    tt = tt + 1
high = x[0]
low = x[0]
for i in range (0,7):
    print "%d: %7d %.5f" % (i, x[i], 100.0 * x[i] / tt)
    if x[i] < low:
        low = x[i]
    if x[i] > high:
        high = x[i]
diff = high - low
print "Variation = %d (%.5f%%)" % (diff, 100.0 * diff / tt)

Und diese Ausgabe zeigt die Ergebnisse:

pax$ python qq.py
0:   99908 14.27257
1:  100029 14.28986
2:  100327 14.33243
3:  100395 14.34214
4:   99104 14.15771
5:   99829 14.26129
6:  100408 14.34400
Variation = 1304 (0.18629%)

pax$ python qq.py
0:   99547 14.22100
1:  100229 14.31843
2:  100078 14.29686
3:   99451 14.20729
4:  100284 14.32629
5:  100038 14.29114
6:  100373 14.33900
Variation = 922 (0.13171%)

pax$ python qq.py
0:  100481 14.35443
1:   99188 14.16971
2:  100284 14.32629
3:  100222 14.31743
4:   99960 14.28000
5:   99426 14.20371
6:  100439 14.34843
Variation = 1293 (0.18471%)

Eine Vereinfachung rand(5)+rand(5), bei der die Fälle ignoriert werden, in denen mehr als 6 zurückgegeben werden, weist eine typische Abweichung von 18% auf, das 100-fache der oben gezeigten Methode:

pax$ python qq_notsogood.py
0:   31756 4.53657
1:   63304 9.04343
2:   95507 13.64386
3:  127825 18.26071
4:  158851 22.69300
5:  127567 18.22386
6:   95190 13.59857
Variation = 127095 (18.15643%)

pax$ python qq_notsogood.py
0:   31792 4.54171
1:   63637 9.09100
2:   95641 13.66300
3:  127627 18.23243
4:  158751 22.67871
5:  126782 18.11171
6:   95770 13.68143
Variation = 126959 (18.13700%)

pax$ python qq_notsogood.py
0:   31955 4.56500
1:   63485 9.06929
2:   94849 13.54986
3:  127737 18.24814
4:  159687 22.81243
5:  127391 18.19871
6:   94896 13.55657
Variation = 127732 (18.24743%)

Und auf Anraten von Nixuz habe ich das Skript aufgeräumt, damit Sie es einfach extrahieren und verwenden können rand7...:

import random

# rand5() returns 0 through 4 inclusive.

def rand5():
    return int (random.random () * 5)

# rand7() generator returns 0 through 6 inclusive (using rand5()).

def rand7():
    rand7ret = 0
    while True:
        rand7ret = (rand7ret + rand5()) % 7
        yield rand7ret

# Number of test runs.

count = 700000

# Work out distribution.

distrib = [0,0,0,0,0,0,0]
rgen =rand7()
for i in range (0,count):
    r = rgen.next()
    distrib[r] = distrib[r] + 1

# Print distributions and calculate variation.

high = distrib[0]
low = distrib[0]
for i in range (0,7):
    print "%d: %7d %.5f" % (i, distrib[i], 100.0 * distrib[i] / count)
    if distrib[i] < low:
        low = distrib[i]
    if distrib[i] > high:
        high = distrib[i]
diff = high - low
print "Variation = %d (%.5f%%)" % (diff, 100.0 * diff / count)
paxdiablo
quelle
2
Ähm, lassen Sie mich das umformulieren. Da ein bestimmtes x zu einem bestimmten Zeitpunkt in der Sequenz erzeugt wurde, können nur 5 von 7 Zahlen für die nächste Zahl in der Folge erzeugt werden. Bei einem echten RNG wären alle Proben unabhängig voneinander, in diesem Fall jedoch eindeutig nicht.
Adam Rosenfield
3
Es ist wahr, dass die ursprüngliche Frage nicht angibt, ob die Eingabe- und Ausgabefunktionen unabhängige und identisch verteilte (iid) Samples erzeugen, aber ich denke, es ist eine vernünftige Erwartung, dass wenn die Eingabe rand5 () iid ist, die Ausgabe rand7 () sollte auch iid sein. Wenn Sie der Meinung sind, dass dies nicht sinnvoll ist, haben Sie Spaß mit Ihrem nicht-iid RNG.
Adam Rosenfield
1
Also, was ist das Wort von den Mathematikern an der Universität?
Adam Rosenfield
1
Diese Lösung ist eindeutig gebrochen. Es ist offensichtlich, dass Sie rand5 (im Durchschnitt) mehr als einmal pro Aufruf von rand7 aufrufen müssen, und diese Lösung funktioniert nicht. Daher können die Ergebnisse durch keine vernünftige Definition von zufällig zufällig sein.
Chris Suter
1
@Pax Bei jeder Iteration Ihrer Funktion kann nur einer von fünf verschiedenen Werten zurückgegeben werden (allerdings im Bereich von 0 bis 6). Die allererste Iteration kann nur eine Zahl im Bereich von 0 bis 4 zurückgeben. Es sollte also klar sein, dass Ihre Funktion zwar eine gleichmäßige Verteilung aufweist, die Stichproben jedoch nicht unabhängig sind, dh sie sind korreliert, was Sie in einem Zufallszahlengenerator nicht möchten.
Chris Suter
3

Diese Antwort ist eher ein Experiment, um mit der Rand5-Funktion die größtmögliche Entropie zu erzielen. Es ist daher etwas unklar und mit ziemlicher Sicherheit viel langsamer als andere Implementierungen.

Angenommen, die Gleichverteilung von 0-4 und die daraus resultierende Gleichverteilung von 0-6:

public class SevenFromFive
{
  public SevenFromFive()
  {
    // this outputs a uniform ditribution but for some reason including it 
    // screws up the output distribution
    // open question Why?
    this.fifth = new ProbabilityCondensor(5, b => {});
    this.eigth = new ProbabilityCondensor(8, AddEntropy);
  } 

  private static Random r = new Random();
  private static uint Rand5()
  {
    return (uint)r.Next(0,5);
  }

  private class ProbabilityCondensor
  {
    private readonly int samples;
    private int counter;
    private int store;
    private readonly Action<bool> output;

    public ProbabilityCondensor(int chanceOfTrueReciprocal,
      Action<bool> output)
    {
      this.output = output;
      this.samples = chanceOfTrueReciprocal - 1;  
    }

    public void Add(bool bit)
    {
      this.counter++;
      if (bit)
        this.store++;   
      if (counter == samples)
      {
        bool? e;
        if (store == 0)
          e = false;
        else if (store == 1)
          e = true;
        else
          e = null;// discard for now       
        counter = 0;
        store = 0;
        if (e.HasValue)
          output(e.Value);
      }
    }
  }

  ulong buffer = 0;
  const ulong Mask = 7UL;
  int bitsAvail = 0;
  private readonly ProbabilityCondensor fifth;
  private readonly ProbabilityCondensor eigth;

  private void AddEntropy(bool bit)
  {
    buffer <<= 1;
    if (bit)
      buffer |= 1;      
    bitsAvail++;
  }

  private void AddTwoBitsEntropy(uint u)
  {
    buffer <<= 2;
    buffer |= (u & 3UL);    
    bitsAvail += 2;
  }

  public uint Rand7()
  {
    uint selection;   
    do
    {
      while (bitsAvail < 3)
      {
        var x = Rand5();
        if (x < 4)
        {
          // put the two low order bits straight in
          AddTwoBitsEntropy(x);
          fifth.Add(false);
        }
        else
        { 
          fifth.Add(true);
        }
      }
      // read 3 bits
      selection = (uint)((buffer & Mask));
      bitsAvail -= 3;     
      buffer >>= 3;
      if (selection == 7)
        eigth.Add(true);
      else
        eigth.Add(false);
    }
    while (selection == 7);   
    return selection;
  }
}

Die Anzahl der Bits, die dem Puffer pro Aufruf von Rand5 hinzugefügt werden, beträgt derzeit 4/5 * 2, also 1,6. Wenn der 1/5 Wahrscheinlichkeitswert enthalten ist, der sich um 0,05 erhöht, also 1,65, aber siehe den Kommentar im Code, in dem ich dies deaktivieren musste.

Bits, die durch Aufruf von Rand7 = 3 + 1/8 * (3 + 1/8 * (3 + 1/8 *) verbraucht werden (...
Dies ist 3 + 3/8 + 3/64 + 3/512 ... also ca. 3,42

Durch Extrahieren von Informationen aus den Siebenen fordere ich 1/8 * 1/7 Bits pro Aufruf zurück, also ungefähr 0,018

Dies ergibt einen Nettoverbrauch von 3,4 Bit pro Anruf, was bedeutet, dass das Verhältnis für jeden Rand7 2,125 Anrufe zu Rand5 beträgt. Das Optimum sollte 2.1 sein.

Ich würde mir vorstellen, dass dieser Ansatz erheblich langsamer ist als viele der anderen hier, es sei denn, die Kosten für den Anruf bei Rand5 sind extrem hoch (z. B. das Anrufen einer externen Entropiequelle).

ShuggyCoUk
quelle
Abgesehen von einigen einfachen Fehlern scheint Ihre Lösung korrekt zu sein: "if (count> 1)" sollte "if (count <= 1)" sein, und das kurz danach auftretende "i ++" sollte sich in den geschweiften Klammern befinden, die davor stehen. Ich bin nicht sicher, ob BitsSet () korrekt ist oder nicht, aber das ist etwas irrelevant.
Adam Rosenfield
Insgesamt ist Ihre Funktion jedoch sehr schwer zu verstehen. Die Entropie wird etwas besser genutzt als sonst, auf Kosten einer höheren Komplikation. Es gibt auch keinen Grund, den Puffer beim ersten Aufruf zunächst mit 35 zufälligen Bits zu füllen, wenn 3 ausreichen würden.
Adam Rosenfield
Ich habe das <= danke korrigiert, das i ++ sollte aber wirklich da sein. Dies sollte im Fall Null und 1 geschehen (Hinzufügen einer 1 bzw. einer Null zum Puffer). Dies ist absolut nicht das, was ich vorschlagen würde, es ist schrecklich kompliziert. Ich war nur daran interessiert, wie nahe ich den theoretischen Entropiegrenzen kommen könnte, die dem Problem innewohnen ... Danke für das Feedback. Ironischerweise war das Füllen des Puffers beim ersten Aufruf, um das Schreiben zu
vereinfachen
Ich habe dies überarbeitet, um es leichter zu verstehen (auf Kosten der Geschwindigkeit), aber es auch korrekt gemacht. Es ist noch nicht optimal, aus irgendeinem Grund verursachen die 1/5 Bits Probleme, obwohl sie in ihrer Anzahl einheitlich sind.
ShuggyCoUk
3

in php

function rand1to7() {
    do {
        $output_value = 0;
        for ($i = 0; $i < 28; $i++) {
            $output_value += rand1to5();
        }
    while ($output_value != 140);
    $output_value -= 12;
    return floor($output_value / 16);
}

Schleifen, um eine Zufallszahl zwischen 16 und 127 zu erzeugen, dividieren durch 16, um einen Gleitkommawert zwischen 1 und 7,9375 zu erzeugen, runden dann ab, um einen Int zwischen 1 und 7 zu erhalten. Wenn ich mich nicht irre, besteht eine 16/112-Chance eines der 7 Ergebnisse.

dqhendricks
quelle
obwohl es wahrscheinlich eine einfachere Antwort gibt, die dieser ähnelt, ohne bedingte Schleife und Modulo anstelle von Floor. Ich kann die Zahlen gerade nicht knacken.
Dqhendricks
3
extern int r5();

int r7() {
    return ((r5() & 0x01) << 2 ) | ((r5() & 0x01) << 1 ) | (r5() & 0x01);
}
maxchengcn
quelle
Problem: Dies gibt ungleichmäßig im Bereich 0-7 zurück, nicht 0-6. In der Tat können Sie 7 = 111bmitp(7) = 8 / 125
Bernard Paulus
3

Ich glaube, ich habe vier Antworten, von denen zwei exakte Lösungen wie die von @Adam Rosenfield liefern, aber ohne das Endlosschleifenproblem, und die anderen zwei mit nahezu perfekter Lösung, aber schnellerer Implementierung als die erste.

Die beste exakte Lösung erfordert 7 Anrufe rand5, aber lassen Sie uns fortfahren, um zu verstehen.

Methode 1 - Genau

Die Stärke von Adams Antwort ist, dass es eine perfekte gleichmäßige Verteilung gibt und es eine sehr hohe Wahrscheinlichkeit (21/25) gibt, dass nur zwei Aufrufe von rand5 () benötigt werden. Der schlimmste Fall ist jedoch die Endlosschleife.

Die erste Lösung unten bietet ebenfalls eine perfekte gleichmäßige Verteilung, erfordert jedoch insgesamt 42 Anrufe an rand5 . Keine Endlosschleifen.

Hier ist eine R-Implementierung:

rand5 <- function() sample(1:5,1)

rand7 <- function()  (sum(sapply(0:6, function(i) i + rand5() + rand5()*2 + rand5()*3 + rand5()*4 + rand5()*5 + rand5()*6)) %% 7) + 1

Für Leute, die nicht mit R vertraut sind, gibt es hier eine vereinfachte Version:

rand7 = function(){
  r = 0 
  for(i in 0:6){
    r = r + i + rand5() + rand5()*2 + rand5()*3 + rand5()*4 + rand5()*5 + rand5()*6
  }
  return r %% 7 + 1
}

Die Verteilung von rand5bleibt erhalten. Wenn wir rechnen, hat jede der 7 Iterationen der Schleife 5 ^ 6 mögliche Kombinationen, also die Gesamtzahl der möglichen Kombinationen (7 * 5^6) %% 7 = 0. Somit können wir die erzeugten Zufallszahlen in gleiche Gruppen von 7 teilen. Weitere Informationen hierzu finden Sie in Methode 2.

Hier sind alle möglichen Kombinationen:

table(apply(expand.grid(c(outer(1:5,0:6,"+")),(1:5)*2,(1:5)*3,(1:5)*4,(1:5)*5,(1:5)*6),1,sum) %% 7 + 1)

    1     2     3     4     5     6     7 
15625 15625 15625 15625 15625 15625 15625 

Ich denke, es ist einfach zu zeigen, dass Adams Methode viel schneller laufen wird. Die Wahrscheinlichkeit, dass rand5in Adams Lösung 42 oder mehr Aufrufe enthalten sind, ist sehr gering ( (4/25)^21 ~ 10^(-17)).

Methode 2 - Nicht genau

Nun die zweite Methode, die fast einheitlich ist, aber 6 Aufrufe erfordert rand5:

rand7 <- function() (sum(sapply(1:6,function(i) i*rand5())) %% 7) + 1

Hier ist eine vereinfachte Version:

rand7 = function(){
  r = 0 
  for(i in 1:6){
    r = r + i*rand5()
  }
  return r %% 7 + 1
}

Dies ist im Wesentlichen eine Iteration von Methode 1. Wenn wir alle möglichen Kombinationen generieren, ergeben sich hier folgende Zählungen:

table(apply(expand.grid(1:5,(1:5)*2,(1:5)*3,(1:5)*4,(1:5)*5,(1:5)*6),1,sum) %% 7 + 1)

   1    2    3    4    5    6    7 
2233 2232 2232 2232 2232 2232 2232

Eine Zahl wird in 5^6 = 15625Versuchen noch einmal erscheinen .

In Methode 1 verschieben wir nun durch Addition von 1 zu 6 die Zahl 2233 zu jedem der aufeinanderfolgenden Punkte. Somit stimmt die Gesamtzahl der Kombinationen überein. Dies funktioniert, weil 5 ^ 6 %% 7 = 1 ist und wir dann 7 geeignete Variationen durchführen, also (7 * 5 ^ 6 %% 7 = 0).

Methode 3 - Genau

Wenn das Argument von Methode 1 und 2 verstanden wird, folgt Methode 3 und erfordert nur 7 Aufrufe von rand5. An diesem Punkt denke ich, dass dies die Mindestanzahl von Anrufen ist, die für eine genaue Lösung erforderlich sind.

Hier ist eine R-Implementierung:

rand5 <- function() sample(1:5,1)

rand7 <- function()  (sum(sapply(1:7, function(i) i * rand5())) %% 7) + 1

Für Leute, die nicht mit R vertraut sind, gibt es hier eine vereinfachte Version:

rand7 = function(){
  r = 0 
  for(i in 1:7){
    r = r + i * rand5()
  }
  return r %% 7 + 1
}

Die Verteilung von rand5bleibt erhalten. Wenn wir rechnen, hat jede der 7 Iterationen der Schleife 5 mögliche Ergebnisse, also die Gesamtzahl der möglichen Kombinationen(7 * 5) %% 7 = 0 . Somit können wir die erzeugten Zufallszahlen in gleiche Gruppen von 7 teilen. Weitere Informationen hierzu finden Sie in Methode eins und zwei.

Hier sind alle möglichen Kombinationen:

table(apply(expand.grid(0:6,(1:5)),1,sum) %% 7 + 1)

1 2 3 4 5 6 7  
5 5 5 5 5 5 5 

Ich denke, es ist einfach zu zeigen, dass Adams Methode immer noch schneller läuft. Die Wahrscheinlichkeit, dass rand5in Adams Lösung 7 oder mehr Aufrufe enthalten sind, ist immer noch gering ( (4/25)^3 ~ 0.004).

Methode 4 - Nicht genau

Dies ist eine geringfügige Variation der zweiten Methode. Es ist fast einheitlich, erfordert jedoch 7 Aufrufe von rand5, das ist eine zusätzliche zu Methode 2:

rand7 <- function() (rand5() + sum(sapply(1:6,function(i) i*rand5())) %% 7) + 1

Hier ist eine vereinfachte Version:

rand7 = function(){
  r = 0 
  for(i in 1:6){
    r = r + i*rand5()
  }
  return (r+rand5()) %% 7 + 1
}

Wenn wir alle möglichen Kombinationen generieren, ergeben sich folgende Zählungen:

table(apply(expand.grid(1:5,(1:5)*2,(1:5)*3,(1:5)*4,(1:5)*5,(1:5)*6,1:5),1,sum) %% 7 + 1)

    1     2     3     4     5     6     7 
11160 11161 11161 11161 11161 11161 11160

In 5^7 = 78125Versuchen werden zwei Zahlen einmal weniger angezeigt. Für die meisten Zwecke kann ich damit leben.

Shambho
quelle
1
Ich bin nicht mit R vertraut, aber wenn ich nicht falsch verstehe, wie diese funktionieren, ist Methode 1 nicht genau. Es hat (5 ^ 6) ^ 7 = 5 ^ 42 mögliche Ergebnisse, nicht (5 ^ 6) * 7; 5 ^ 42 ist nicht durch 7 teilbar. Ebenso ist Methode 3 nicht genau. Es hat 5 ^ 7 mögliche Ergebnisse, nicht 5 * 7. (Die letzte Schleifeniteration in Methode 3 mit hat i=7ebenfalls keine Auswirkung, da das Hinzufügen 7*rand5()zu rden Wert von rMod 7 nicht ändert .)
Adam Rosenfield
2

Die Funktion, die Sie benötigen, ist rand1_7 () . Ich habe rand1_5 () geschrieben, damit Sie sie testen und zeichnen können.

import numpy
def rand1_5():
    return numpy.random.randint(5)+1

def rand1_7():
    q = 0
    for i in xrange(7):  q+= rand1_5()
    return q%7 + 1
Andrea Ambu
quelle