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

Sind Hausaufgaben hier erlaubt?

Diese Funktion führt grobe "Basis 5"-Mathematik durch, um eine Zahl zwischen 0 und 6 zu erzeugen.

function rnd7() {
    do {
        r1 = rnd5() - 1;
        do {
            r2=rnd5() - 1;
        } while (r2 > 1);
        result = r2 * 5 + r1;
    } while (result > 6);
    return result + 1;
}

Answer 2

Wenn wir die zusätzliche Einschränkung berücksichtigen, dass wir versuchen, die effizienteste Antwort zu geben, d.h. eine, die einen Eingabestrom ergibt, I aus gleichmäßig verteilten ganzen Zahlen der Länge m von 1-5 einen Strom ausgibt O aus gleichmäßig verteilten ganzen Zahlen von 1-7 mit der längsten Länge im Verhältnis zu m sagen L(m) .

Die einfachste Art, dies zu analysieren, ist die Behandlung der Ströme I und O als 5-stellige bzw. 7-stellige Zahlen. Dies wird durch die Idee der Hauptantwort erreicht, den Strom zu nehmen a1, a2, a3,... -> a1+5*a2+5^2*a3+.. und in ähnlicher Weise für Stream O .

Wenn wir dann einen Abschnitt des Eingangsstroms der Länge m choose n s.t. 5^m-7^n=c donde c>0 und ist so klein wie möglich. Dann gibt es eine einheitliche Abbildung des Eingabestroms der Länge m auf ganze Zahlen aus 1 à 5^m und eine weitere einheitliche Abbildung von ganzen Zahlen von 1 bis 7^n in den Ausgabestrom der Länge n zu übertragen, wobei wir möglicherweise einige Fälle aus dem Eingabestrom verlieren, wenn die zugeordnete ganze Zahl größer ist als 7^n .

Daraus ergibt sich also ein Wert für L(m) von etwa m (log5/log7) was ungefähr .82m .

Die Schwierigkeit bei der obigen Analyse ist die Gleichung 5^m-7^n=c was nicht leicht zu lösen ist, und der Fall, in dem der einheitliche Wert aus 1 à 5^m übersteigt 7^n und wir verlieren an Effizienz.

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

Si 5^m-7^n=c dann wird aus dem Eingabestrom tatsächlich eine einheitliche Zufallszahl aus 0 à (5^m)-1 und verwenden Sie keine höheren Werte als 7^n . Diese Werte können jedoch gerettet und wieder verwendet werden. Sie erzeugen effektiv eine einheitliche Folge von Zahlen von 1 bis 5^m-7^n . Wir können also versuchen, diese zu verwenden und sie in 7-stellige Zahlen umzuwandeln, damit wir mehr Ausgabewerte erzeugen können.

Wenn wir die T7(X) ist die durchschnittliche Länge der Ausgangssequenz von random(1-7) Ganzzahlen, die von einer einheitlichen Eingabe der Größe X und unter der Annahme, dass 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) da wir eine Folge der Länge no mit einer Wahrscheinlichkeit von 7^n0/5^m mit einem Rest der Länge 5^m-7^n0 mit hoher Wahrscheinlichkeit (5^m-7^n0)/5^m) .

Wenn wir einfach weiter substituieren, 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)

Man kann es auch anders ausdrücken:

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 der oben beschriebene, in dem 5^m=7^n+s , donde s<7 .

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

Der schlimmste Fall ist, wenn wir nur k und s.t 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 bei sehr großen m abschneiden, d. h. wie gut wir den Fehlerterm erhalten können:

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

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

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

Ich bin mir sicher, dass es viele Theorien gibt, die sich mit diesem Thema befassen, und ich werde sie mir vielleicht einmal ansehen und darüber berichten.

Answer 3

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 zu werfen, die ich in Python betrachte, damit ich mit ihnen herumspielen kann. Ich dachte, ich würde es hier posten, in der Hoffnung, dass es für jemanden da draußen nützlich ist, nicht dass es lange gedauert hat, um es zusammenzuwerfen.

Answer 4

Warum nicht einfach machen?

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

Die Wahrscheinlichkeit, bei dieser Lösung 1 und 7 zu erhalten, ist aufgrund des Modulos geringer, aber wenn Sie nur eine schnelle und lesbare Lösung wollen, ist dies der richtige Weg.

Answer 5

Unter der Annahme, dass Rand(n) bedeutet hier "zufällige ganze Zahl in einer Gleichverteilung aus 0 à n-1 "Hier ist ein Codebeispiel, das Python's randint verwendet, was diesen Effekt hat. Es verwendet nur randint(5) und Konstanten, um die Wirkung von randint(7) . Ein bisschen albern, eigentlich

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