Erweitern Sie einen Zufallsbereich von 1-5 auf 1-7

Question

Geben Sie eine Funktion an, die eine zufällige ganze Zahl im Bereich von 1 bis 5 erzeugt. Schreiben Sie eine Funktion, die eine zufällige ganze Zahl 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 mit einer langsameren CPU zu arbeiten?

Answer 1

Dies entspricht der Lösung von Adam Rosenfield, ist aber für einige Leser vielleicht etwas klarer. Sie geht davon aus, dass rand5() eine Funktion ist, die eine statistisch zufällige ganze Zahl 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 das? Stellen Sie sich Folgendes vor: Drucken Sie dieses zweidimensionale Feld auf Papier aus, heften Sie es an eine Dartscheibe und werfen Sie nach dem Zufallsprinzip Dartpfeile darauf. Wenn Sie einen Wert ungleich Null treffen, handelt es sich um einen statistisch zufälligen Wert zwischen 1 und 7, da eine gleiche Anzahl von Werten ungleich Null zur Auswahl steht. Wenn du eine Null triffst, wirf den Pfeil einfach weiter, bis du eine andere Zahl als Null triffst. Das ist es, was dieser Code macht: Die Indizes i und j wählen zufällig eine Stelle auf der Dartscheibe aus, und wenn wir kein gutes Ergebnis erhalten, werfen wir weiter Dartpfeile.

Wie Adam sagte, kann dies im schlimmsten Fall ewig dauern, aber statistisch gesehen tritt der schlimmste Fall nie ein :)

Answer 2

Es gibt keine (exakt korrekte) Lösung, die in einer konstanten Zeit läuft, da 1/7 eine unendliche Dezimalzahl zur Basis 5 ist. Eine einfache Lösung wäre die Verwendung von Rückweisungsstichproben, z. B.:

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 besteht eine verschwindend geringe Wahrscheinlichkeit, dass die Schleife ewig läuft.

Answer 3

Ich möchte eine weitere Antwort hinzufügen, zusätzlich zu meine erste Antwort . Mit dieser Antwort wird versucht, die Anzahl der Anrufe bei rand5() pro Anruf an rand7() , um die Nutzung des Zufalls zu maximieren. Das heißt, wenn man den Zufall als kostbare Ressource betrachtet, wollen wir so viel wie möglich davon nutzen, ohne irgendwelche Zufallsbits wegzuwerfen. Diese Antwort hat auch einige Ähnlichkeiten mit der Logik, die in Ivans Antwort .

El Entropie einer Zufallsvariablen ist eine wohldefinierte Größe. Für eine Zufallsvariable, die N Zustände mit gleichen Wahrscheinlichkeiten annimmt (eine Gleichverteilung), ist die Entropie log ₂ N. So, rand5() hat eine Entropie von etwa 2,32193 Bit, und rand7() hat etwa 2,80735 Bits Entropie. Wenn wir hoffen, die Zufälligkeit optimal nutzen zu können, müssen wir alle 2,32193 Bits der Entropie von jedem Aufruf an rand5() und wenden sie an, um 2,80735 Bits Entropie zu erzeugen, die für jeden Aufruf von rand7() . Die grundsätzliche Grenze ist also, dass wir nicht besser als log(7)/log(5) = 1,20906 Anrufe machen können, um rand5() pro Anruf bei rand7() .

Randbemerkung: Alle Logarithmen in dieser Antwort werden zur Basis 2 berechnet, sofern nicht anders angegeben. rand5() wird davon ausgegangen, dass sie Zahlen im Bereich [0, 4] zurückgibt, und rand7() wird davon ausgegangen, dass sie Zahlen im Bereich [0, 6] liefert. Die Anpassung der Bereiche auf [1, 5] bzw. [1, 7] ist trivial.

Und wie machen wir das? Wir erzeugen eine unendlich präzise eine zufällige reelle Zahl zwischen 0 und 1 (tun wir mal so, als ob wir eine solche unendlich genaue Zahl tatsächlich berechnen und speichern könnten - wir werden das später klären). Wir können eine solche Zahl erzeugen, indem wir ihre Ziffern zur Basis 5 generieren: Wir wählen die Zufallszahl 0. a ₁ a ₂ a ₃ ..., wobei jede Ziffer a _{<code>i</code>} wird durch einen Aufruf von rand5() . Wenn unser RNG zum Beispiel eine _{<code>i</code>} = 1 für alle i Wenn man die Tatsache ignoriert, dass dies nicht sehr zufällig ist, würde dies der realen Zahl 1/5 + 1/5 entsprechen. 2 + 1/5 3 + ... = 1/4 (Summe einer geometrischen Reihe).

Ok, wir haben also eine reelle Zufallszahl zwischen 0 und 1 gewählt. Ich behaupte nun, dass eine solche Zufallszahl gleichmäßig verteilt ist. Intuitiv ist dies leicht zu verstehen, da jede Ziffer gleichmäßig gewählt wurde und die Zahl unendlich genau ist. Ein formaler Beweis dafür ist jedoch etwas komplizierter, da wir es jetzt mit einer kontinuierlichen Verteilung statt mit einer diskreten Verteilung zu tun haben, also müssen wir beweisen, dass die Wahrscheinlichkeit, dass unsere Zahl in einem Intervall [ a , b ] ist gleich der Länge des Intervalls, b - a . Der Beweis wird als Übung für den Leser überlassen =).

Da wir nun eine reelle Zufallszahl haben, die gleichmäßig aus dem Bereich [0, 1] ausgewählt wurde, müssen wir sie in eine Reihe von gleichmäßig zufälligen Zahlen im Bereich [0, 6] umwandeln, um die Ausgabe von rand7() . Wie machen wir das? Indem wir sie in eine unendlich genaue Dezimalzahl zur Basis 7 umwandeln, und dann entspricht jede Ziffer zur Basis 7 einer Ausgabe von rand7() .

Nehmen wir das Beispiel von vorhin: Wenn unsere rand5() einen unendlichen Strom von 1en erzeugt, dann ist unsere reelle Zufallszahl 1/4. Wenn wir 1/4 in die Basis 7 umwandeln, erhalten wir die unendliche Dezimalzahl 0,15151515..., so dass wir als Ausgabe 1, 5, 1, 5, 1, 5, usw. erhalten.

Ok, wir haben also die Grundidee, aber wir haben noch zwei Probleme: Wir können eine unendlich genaue reelle Zahl weder berechnen noch speichern, wie gehen wir also mit nur einem endlichen Teil von ihr um? Zweitens: Wie konvertieren wir sie tatsächlich in die Basis 7?

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

1. Multiplizieren mit 7
2. Der ganzzahlige Teil des Ergebnisses ist die nächste Ziffer zur Basis 7
3. Subtrahieren Sie den ganzzahligen Teil, so dass nur der gebrochene Teil übrig bleibt.
4. Gehe zu Schritt 1

Um das Problem der unendlichen Genauigkeit zu lösen, berechnen wir ein Teilergebnis und speichern auch eine Obergrenze für das mögliche Ergebnis. Das heißt, nehmen wir an, wir haben rand5() zweimal, und beide Male wurde 1 zurückgegeben. Die Zahl, die wir bisher erzeugt haben, ist 0,11 (Basis 5). Was auch immer der Rest der unendlichen Reihe von Aufrufen an rand5() produzieren, wird die zufällige reelle Zahl, die wir generieren, 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 maximalen Wert, den sie jemals annehmen könnte, im Auge behalten, konvertieren wir beide Zahlen zur Basis 7. Wenn sie sich auf die erste Zahl einigen k Ziffern, dann können wir sicher die nächste k Ziffern - unabhängig davon, wie der unendliche Strom von Ziffern zur Basis 5 aussieht, werden sie sich niemals auf die nächste k Ziffern der Basis-7-Darstellung!

Und das ist der Algorithmus - um die nächste Ausgabe von rand7() erzeugen wir nur so viele Ziffern von rand5() da wir sicherstellen müssen, dass wir den Wert der nächsten Ziffer bei der Umrechnung der reellen Zufallszahl in die Basis 7 mit Sicherheit kennen. Hier ist eine Python-Implementierung mit einem Test-Kabelbaum:

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)

なお rand7_gen() gibt einen Generator zurück, da er über einen internen Zustand verfügt, der die Umwandlung der Zahl in die Basis 7 beinhaltet. Der Test-Kabelbaum ruft next(r7) 10000 Mal, um 10000 Zufallszahlen zu erzeugen, und misst dann deren Verteilung. Es wird nur ganzzahlige Mathematik verwendet, so dass die Ergebnisse genau richtig sind.

Beachten Sie auch, dass die Zahlen hier sehr groß, sehr schnell. Potenzen von 5 und 7 wachsen schnell. Daher wird die Leistung nach der Erzeugung vieler Zufallszahlen aufgrund der Bignum-Arithmetik merklich abnehmen. Aber bedenken Sie, dass mein Ziel darin bestand, die Verwendung von Zufallsbits zu maximieren, nicht die Leistung zu steigern (obwohl das ein sekundäres Ziel ist).

In einem Durchlauf habe ich 12091 Aufrufe an rand5() für 10000 Anrufe an rand7() und erreichte das Minimum von log(7)/log(5)-Aufrufen im Durchschnitt auf 4 signifikante Stellen, und die resultierende Ausgabe war einheitlich.

Um diesen Code auf eine Sprache zu portieren, die keine beliebig großen Ganzzahlen eingebaut hat, müssen Sie die Werte von pow5 y pow7 auf den Maximalwert Ihres nativen Integraltyps - wenn sie zu groß werden, setzen Sie alles zurück und beginnen von vorne. Dies erhöht die durchschnittliche Anzahl der Aufrufe von rand5() pro Anruf bei rand7() sehr geringfügig, aber hoffentlich sollte sie auch bei 32- oder 64-Bit-Ganzzahlen nicht zu stark ansteigen.

Answer 4

(Ich habe gestohlen Adam Rosenfelds Antwort und machte es etwa 7% schneller).

Nehmen wir an, dass rand5() eines von {0,1,2,3,4} mit gleicher Verteilung zurückgibt und das Ziel ist, {0,1,2,3,4,5,6} mit gleicher Verteilung zurückzugeben.

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 halten den größten Wert fest, den die Schleife in der Variablen max . Wenn das bisherige Ergebnis zwischen max%7 und max-1 liegt, wird das Ergebnis gleichmäßig in diesem Bereich verteilt. Ist dies nicht der Fall, verwenden wir den Rest, der zufällig zwischen 0 und max%7-1 liegt, und einen weiteren Aufruf von rand(), um eine neue Zahl und einen neuen Höchstwert zu erhalten. Dann beginnen wir erneut.

Bearbeiten: Die erwartete Anzahl der Aufrufe von rand5() 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()

Answer 5

Algorithmus:

7 kann durch eine Folge von 3 Bits dargestellt werden

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

wenn das Ergebnis 1 oder 2 ist, wird das Bit mit 0 aufgefüllt
wenn das Ergebnis 4 oder 5 ist, fülle das Bit mit 1
Wenn das Ergebnis 3 ist, ignorieren Sie es und wiederholen Sie es (Ablehnung).

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

EDIT。 Dies scheint die einfachste und effizienteste Lösung zu sein, daher hier etwas 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;
        }
    }
}