Biorąc pod uwagę funkcję, która generuje losową liczbę całkowitą z zakresu od 1 do 5, napisz funkcję, która generuje losową liczbę całkowitą z zakresu od 1 do 7.

1. Jakie jest proste rozwiązanie?
2. Jakie jest skuteczne rozwiązanie w celu zmniejszenia zużycia pamięci lub uruchomienia na wolniejszym procesorze?

Jest to odpowiednik rozwiązania Adama Rosenfielda, ale dla niektórych czytelników może być nieco bardziej jasne. Zakłada, że ​​rand5 () jest funkcją, która zwraca statystycznie losową liczbę całkowitą z zakresu od 1 do 5 włącznie.

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;
}

Jak to działa? Pomyśl o tym w ten sposób: wyobraź sobie wydrukowanie tej dwuwymiarowej tablicy na papierze, przyczepienie jej do planszy i losowe rzucanie w nią rzutkami. Jeśli osiągniesz wartość niezerową, jest to statystycznie losowa wartość od 1 do 7, ponieważ istnieje taka sama liczba wartości niezerowych do wyboru. Jeśli osiągniesz zero, po prostu rzucaj strzałką, aż osiągniesz wartość niezerową. Tak właśnie działa ten kod: indeksy i i losowo wybierają lokalizację na planszy, a jeśli nie uzyskamy dobrego wyniku, będziemy rzucać rzutkami.

Jak powiedział Adam, może to trwać wiecznie w najgorszym przypadku, ale statystycznie najgorszy przypadek nigdy się nie zdarza. :)

Nie ma (dokładnie poprawnego) rozwiązania, które działałoby w stałym czasie, ponieważ 1/7 to nieskończona liczba dziesiętna w podstawie 5. Jednym prostym rozwiązaniem byłoby użycie próbkowania odrzucenia, np .:

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

Oczekiwany czas działania wynosi 25/21 = 1,19 iteracji pętli, ale istnieje nieskończenie małe prawdopodobieństwo zapętlenia na zawsze.

Chciałbym dodać kolejną odpowiedź, oprócz mojej pierwszej odpowiedzi . Ta odpowiedź próbuje zminimalizować liczbę połączeń do rand5()każdego połączenia rand7(), aby zmaksymalizować wykorzystanie losowości. Oznacza to, że jeśli uważasz przypadkowość za cenny zasób, chcemy wykorzystać jego jak najwięcej, bez wyrzucania losowych elementów. Ta odpowiedź ma również pewne podobieństwa z logiką przedstawioną w odpowiedzi Iwana .

Entropia zmiennej losowej jest dobrze określona wielkość. Dla zmiennej losowej, która przyjmuje N stanów z jednakowymi prawdopodobieństwami (rozkład równomierny), entropia wynosi log ₂ N. Zatem rand5()ma około 2,32193 bitów entropii i rand7()około 2,80735 bitów entropii. Jeśli mamy nadzieję zmaksymalizować wykorzystanie przypadkowości, musimy użyć wszystkich 2,32193 bitów entropii z każdego wywołania rand5()i zastosować je do wygenerowania 2.80735 bitów entropii potrzebnych dla każdego wywołania do rand7(). Podstawowym ograniczeniem jest zatem to, że nie możemy zrobić nic lepszego niż log (7) / log (5) = 1,20906 wywołań rand5()na połączenie z rand7().

Dodatkowe uwagi: wszystkie logarytmy w tej odpowiedzi będą podstawą 2, chyba że określono inaczej. rand5()zakłada się, że zwracają liczby z zakresu [0, 4] i rand7()przyjmowane są, że zwracają liczby z zakresu [0, 6]. Dostosowanie zakresów odpowiednio do [1, 5] i [1, 7] jest banalne.

Więc jak to zrobimy? Generujemy nieskończenie precyzyjną losową liczbę rzeczywistą z przedziału od 0 do 1 (udawajmy, że możemy faktycznie obliczyć i zapisać tak nieskończenie dokładną liczbę - naprawimy to później). Możemy wygenerować taki numer, generując jego cyfry w bazie 5: wybieramy losową liczbę 0. a₁ a₂ a₃ ..., gdzie każda cyfra a _ijest wybierana przez wywołanie do rand5(). Na przykład, jeśli nasz RNG wybrał _idla wszystkich wartość a = 1 i, to ignorując fakt, że nie jest to zbyt losowe, odpowiadałoby to rzeczywistej liczbie 1/5 + 1/5 ² + 1/5 ³ + ... = 1/4 (suma szeregu geometrycznego).

Ok, więc wybraliśmy losową liczbę rzeczywistą od 0 do 1. Teraz twierdzę, że taka losowa liczba jest równomiernie rozłożona. Intuicyjnie jest to łatwe do zrozumienia, ponieważ każda cyfra została wybrana jednolicie, a liczba jest nieskończenie dokładna. Jednak formalny dowód na to jest nieco bardziej zaangażowany, ponieważ teraz mamy do czynienia z rozkładem ciągłym zamiast rozkładem dyskretnym, więc musimy udowodnić, że prawdopodobieństwo, że nasza liczba leży w przedziale [ a, b] jest równe długości że interwał b - a. Dowód pozostaje jako ćwiczenie dla czytelnika =).

Teraz, gdy mamy losową liczbę rzeczywistą wybraną równomiernie z zakresu [0, 1], musimy przekonwertować ją na serię równomiernie losowych liczb z zakresu [0, 6], aby wygenerować wynik rand7(). Jak to robimy? Po prostu odwrotność tego, co właśnie zrobiliśmy - konwertujemy go na nieskończenie dokładny dziesiętny w podstawie 7, a następnie każda podstawowa cyfra 7 odpowiada jednemu wyjściu rand7().

Biorąc przykład z wcześniejszego, jeśli nasz rand5()wytworzy nieskończony strumień 1, nasza losowa liczba rzeczywista wyniesie 1/4. Konwertując 1/4 na podstawę 7, otrzymujemy nieskończoną liczbę dziesiętną 0,15151515 ..., więc będziemy produkować jako dane wyjściowe 1, 5, 1, 5, 1, 5 itd.

Ok, więc mamy główny pomysł, ale pozostały nam dwa problemy: nie jesteśmy w stanie obliczyć ani zapisać nieskończenie dokładnej liczby rzeczywistej, więc jak sobie z tym poradzić? Po drugie, jak faktycznie przekonwertować go na bazę 7?

Jednym ze sposobów konwersji liczby od 0 do 1 na bazę 7 jest:

1. Pomnóż przez 7
2. Integralną częścią wyniku jest następna podstawowa 7 cyfra
3. Odejmij część integralną, pozostawiając tylko część ułamkową
4. Idź do kroku 1

Aby poradzić sobie z problemem nieskończonej precyzji, obliczamy wynik częściowy, a także przechowujemy górną granicę możliwego wyniku. To znaczy, załóżmy, że zadzwoniliśmy rand5()dwa razy i wrócił 1 razy. Dotychczas wygenerowaliśmy liczbę 0,11 (podstawa 5). Niezależnie od reszty nieskończonej serii wywołań do rand5()wygenerowania, losowa liczba rzeczywista, którą generujemy, nigdy nie będzie większa niż 0,12: zawsze jest prawdą, że 0,11 ≤ 0,11xyz ... <0,12.

Tak więc, śledząc do tej pory bieżącą liczbę i maksymalną wartość, jaką kiedykolwiek mogła przyjąć, konwertujemy obie liczby na bazę 7. Jeśli zgadzają się co do pierwszych kcyfr, możemy bezpiecznie wyprowadzić kolejne kcyfry - niezależnie od tego, co nieskończony strumień podstawowych cyfr 5, nigdy nie wpłyną one na kolejne kcyfry reprezentacji podstawowej 7!

I to jest algorytm - aby wygenerować następny wynik rand7(), generujemy tylko tyle cyfr, rand5()ile potrzebujemy, aby upewnić się, że znamy z pewnością wartość następnej cyfry w przeliczeniu losowej liczby rzeczywistej na bazę 7. Oto implementacja Python z testową wiązką:

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)

Zwróć uwagę, że rand7_gen()zwraca generator, ponieważ ma stan wewnętrzny polegający na konwersji liczby na bazę 7. Wiązka testowa wywołuje next(r7)10000 razy w celu wygenerowania 10000 liczb losowych, a następnie mierzy ich rozkład. Używana jest tylko matematyka liczb całkowitych, więc wyniki są dokładnie poprawne.

Zauważ też, że liczby tutaj stają się bardzo duże, bardzo szybkie. Moce 5 i 7 rosną szybko. Dlatego wydajność zacznie się zauważalnie obniżać po wygenerowaniu wielu liczb losowych z powodu arytmetyki bignum. Pamiętaj jednak, że moim celem było maksymalne wykorzystanie losowych bitów, a nie maksymalizacja wydajności (chociaż jest to cel drugorzędny).

W jednym z nich wykonałem 12091 wywołań rand5()dla 10000 wywołań rand7(), osiągając minimum wywołań log (7) / log (5) średnio do 4 cyfr znaczących, a wynikowy wynik był jednolity.

W celu portu to kod języka, który nie posiada dowolnie duże liczby całkowite wbudowany, musisz cap wartości pow5i pow7maksymalnej wartości swojej rodzimej zintegrowanym typu - jeśli staną się zbyt duże, a następnie zresetować wszystko i zacznij od nowa. Zwiększy rand5()to rand7()bardzo nieznacznie średnią liczbę wywołań na połączenie , ale mam nadzieję, że nie powinno to zbytnio wzrosnąć nawet dla liczb całkowitych 32- lub 64-bitowych.

(Ukradłem odpowiedź Adama Rosenfelda i sprawiłem, że działa o około 7% szybciej).

Załóżmy, że rand5 () zwraca jeden z {0,1,2,3,4} z jednakowym rozkładem, a celem jest return {0,1,2,3,4,5,6} z jednakowym rozkładem.

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);
}

Śledzimy największą wartość, jaką pętla może uzyskać w zmiennej max. Jeśli dotychczasowy wynik mieści się w przedziale od maks.% 7 do maks. 1, wynik będzie równomiernie rozproszony w tym zakresie. Jeśli nie, używamy reszty, która jest losowa między 0 a maks.% 7-1, oraz innego wywołania funkcji rand () w celu utworzenia nowego numeru i nowego maksimum. Potem zaczynamy od nowa.

Edycja: Oczekuj, ile razy wywołanie rand5 () wynosi x w tym równaniu:

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()

Algorytm:

7 można przedstawić w sekwencji 3 bitów

Użyj rand (5), aby losowo wypełnić każdy bit 0 lub 1.
Na przykład: call rand (5) i

jeśli wynik to 1 lub 2, wypełnij bit 0,
jeśli wynik to 4 lub 5, wypełnij bit 1,
jeśli wynik to 3, a następnie zignoruj ​​i zrób to ponownie (odrzucenie)

W ten sposób możemy wypełnić 3 bity losowo 0/1, a tym samym uzyskać liczbę od 1-7.

EDYCJA: To wydaje się być najprostszą i najwydajniejszą odpowiedzią, więc oto dla niej kod:

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;
        }
    }
}

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 );
    }
}

rand7() = (rand5()+rand5()+rand5()+rand5()+rand5()+rand5()+rand5())%7+1

Edycja: To nie do końca działa. Jest wyłączony o około 2 części na 1000 (przy założeniu idealnego rand5). Wiadra otrzymują:

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

Przełączając na sumę

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

wydaje się zyskać rząd wielkości na każde 2 dodane

BTW: powyższa tabela błędów nie została wygenerowana przez próbkowanie, ale przez następującą relację powtarzalności:

p[x,n]Czy liczba sposobów output=xmoże zdarzyć podane nwywołań 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]

int ans = 0;
while (ans == 0) 
{
     for (int i=0; i<3; i++) 
     {
          while ((r = rand5()) == 3){};
          ans += (r < 3) >> i
     }
}

Poniżej przedstawiono rozkład równomierny na {1, 2, 3, 4, 5, 6, 7} przy użyciu generatora liczb losowych, wytwarzając rozkład równomierny na {1, 2, 3, 4, 5}. Kod jest niechlujny, ale logika jest jasna.

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;
}    

int rand7() {
    int value = rand5()
              + rand5() * 2
              + rand5() * 3
              + rand5() * 4
              + rand5() * 5
              + rand5() * 6;
    return value%7;
}

W przeciwieństwie do wybranego rozwiązania algorytm będzie działał w stałym czasie. Wykonuje jednak 2 połączenia z rand5 więcej niż średni czas działania wybranego rozwiązania.

Pamiętaj, że ten generator nie jest doskonały (liczba 0 ma o 0,0064% większą szansę niż jakakolwiek inna liczba), ale dla większości praktycznych celów gwarancja stałego czasu prawdopodobnie przewyższa tę niedokładność.

Wyjaśnienie

To rozwiązanie wywodzi się z faktu, że liczba 15 624 jest podzielna przez 7, a zatem jeśli możemy losowo i jednolicie wygenerować liczby od 0 do 15 624, a następnie wziąć mod 7, możemy uzyskać prawie jednolity generator rand7. Liczby od 0 do 15 624 można równomiernie wygenerować, rzucając 6 razy 6 rand i używając ich do utworzenia cyfr liczby podstawowej 5 w następujący sposób:

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

Właściwości mod 7 pozwalają jednak nieco uprościć równanie:

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

Więc

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

staje się

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

Teoria

Liczba 15,624 nie została wybrana losowo, ale można ją odkryć za pomocą małego twierdzenia Fermata, które stwierdza, że ​​jeśli p jest liczbą pierwszą, to

a^(p-1) = 1 mod p

To daje nam

(5^6)-1 = 0 mod 7

(5 ^ 6) -1 jest równe

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

Jest to liczba w postaci podstawowej 5, dlatego możemy zobaczyć, że ta metoda może być użyta do przejścia z dowolnego generatora liczb losowych do dowolnego innego generatora liczb losowych. Chociaż przy zastosowaniu wykładnika p-1 zawsze pojawia się niewielkie odchylenie w kierunku 0.

Aby uogólnić to podejście i być bardziej dokładnym, możemy mieć taką funkcję:

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)

Czy dozwolone są tutaj zadania domowe?

Ta funkcja wykonuje surową matematykę „base 5”, aby wygenerować liczbę od 0 do 6.

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

Jeśli weźmiemy pod uwagę dodatkowe ograniczenie związane z próbą udzielenia najskuteczniejszej odpowiedzi, tj. Taką, która poda strumień wejściowy I, o równomiernie rozłożonych liczbach całkowitych o długości mod 1-5, wyprowadza strumień O, o równomiernie rozłożonych liczbach całkowitych od 1-7 o najdłuższej długości względnej do m, powiedzmy L(m).

Najprostszym sposobem na analizę tego jest traktowanie strumieni I i Oodpowiednio liczb 5-arylowych i 7-arytowych. Osiąga się to dzięki głównej odpowiedzi na pomysł pobrania strumienia a1, a2, a3,... -> a1+5*a2+5^2*a3+..i podobnie do strumienia O.

Jeśli weźmiemy część strumienia wejściowego o długości, m choose n s.t. 5^m-7^n=cgdzie c>0i jest tak mała, jak to możliwe. Następnie istnieje jednolita mapa od strumienia wejściowego o długości m do liczb całkowitych od 1do 5^mi kolejna jednolita mapa od liczb całkowitych od 1 do 7^nstrumienia wyjściowego o długości n, w którym możemy być zmuszeni stracić kilka przypadków ze strumienia wejściowego, gdy odwzorowana liczba całkowita przekracza 7^n.

Daje to wartość L(m)około, m (log5/log7)która jest w przybliżeniu .82m.

Trudność z powyższą analizą stanowi równanie, 5^m-7^n=cktóre nie jest łatwe do dokładnego rozwiązania, oraz przypadek, w którym jednorodna wartość od 1do 5^mprzekracza 7^ni tracimy wydajność.

Pytanie brzmi, jak blisko najlepszej możliwej wartości m (log5 / log7) można osiągnąć. Na przykład, kiedy liczba ta zbliża się do liczby całkowitej, czy możemy znaleźć sposób na osiągnięcie tej dokładnej całkowitej liczby wartości wyjściowych?

Jeśli 5^m-7^n=cnastępnie ze strumienia wejściowego skutecznie generujemy jednolitą liczbę losową od 0do (5^m)-1i nie używamy żadnych wartości wyższych niż 7^n. Wartości te można jednak uratować i wykorzystać ponownie. Skutecznie generują jednolitą sekwencję liczb od 1 do 5^m-7^n. Możemy więc spróbować ich użyć i przekonwertować na liczby 7-arytowe, abyśmy mogli stworzyć więcej wartości wyjściowych.

Jeśli pozwolimy T7(X)być średnią długością sekwencji wyjściowej random(1-7)liczb całkowitych uzyskanych z jednolitego wejścia wielkości X, i zakładając, że 5^m=7^n0+7^n1+7^n2+...+7^nr+s, s<7.

Zatem, T7(5^m)=n0x7^n0/5^m + ((5^m-7^n0)/5^m) T7(5^m-7^n0)ponieważ mamy długość bez sekwencji z prawdopodobieństwem 7 ^ n0 / 5 ^ m z resztą długości 5^m-7^n0z prawdopodobieństwem (5^m-7^n0)/5^m).

Jeśli po prostu będziemy zastępować, otrzymamy:

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

W związku z tym

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

Innym sposobem na przedstawienie tego jest:

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)

Najlepszy możliwy przypadek to mój oryginalny powyżej, gdzie 5^m=7^n+s, gdzie s<7.

Tak T7(5^m) = nx(7^n)/(7^n+s) = n+o(1) = m (Log5/Log7)+o(1)jak poprzednio.

Najgorszym przypadkiem jest, gdy możemy znaleźć tylko k i st 5 ^ m = kx7 + s.

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

Inne przypadki są gdzieś pomiędzy. Interesujące byłoby zobaczyć, jak dobrze możemy sobie radzić z bardzo dużym m, tj. Jak dobrze możemy uzyskać warunek błędu:

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

e(m) = o(1)Ogólnie wydaje się to niemożliwe, ale mamy nadzieję, że możemy to udowodnić e(m)=o(m).

Całość opiera się na rozkładzie 7-arytowych cyfr 5^mdla różnych wartości m.

Jestem pewien, że istnieje wiele teorii, które to obejmują. W pewnym momencie mogę się przyjrzeć i zdać relację.

Oto działająca implementacja odpowiedzi Adama na język Python .

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

Lubię wrzucać algorytmy, na które patrzę, do Pythona, aby móc się nimi bawić, pomyślałem, że opublikuję to tutaj w nadziei, że przyda się komuś tam, a nie, że zajęło to dużo czasu.

Dlaczego nie zrobić tego prosto?

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

Szanse na uzyskanie 1 i 7 w tym rozwiązaniu są niższe z powodu modulo, jednak jeśli chcesz tylko szybkiego i czytelnego rozwiązania, jest to dobra droga.

Zakładając, że rand (n) oznacza tutaj „losową liczbę całkowitą w jednolitym rozkładzie od 0 do n-1 ”, oto przykładowy kod wykorzystujący randinta Pythona, który ma taki efekt. Używa tylko randinta (5) i stałych, aby uzyskać efekt randinta (7) . Właściwie to trochę głupie

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

Prawidłowa odpowiedź Adama Rosenfielda jest następująca:

• x = 5 ^ n (w jego przypadku: n = 2)
• manipuluj wywołaniami n rand5, aby uzyskać liczbę y w zakresie [1, x]
• z = ((int) (x / 7)) * 7
• jeśli y> z, spróbuj ponownie. w przeciwnym razie zwróci y% 7 + 1

Kiedy n jest równe 2, masz 4 możliwości wyrzucenia: y = {22, 23, 24, 25}. Jeśli użyjesz n równa się 6, masz tylko 1 rzut z autu: y = {15625}.

5 ^ 6 = 15625
7 * 2232 = 15624

Dzwonisz do rand5 więcej razy. Masz jednak znacznie mniejszą szansę na uzyskanie wartości wyrzucenia (lub nieskończonej pętli). Jeśli istnieje sposób, aby uzyskać żadną możliwą wartość odrzucenia dla y, jeszcze jej nie znalazłem.

Oto moja odpowiedź:

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);
  }
}

Jest to trochę bardziej skomplikowane niż inne, ale uważam, że minimalizuje połączenia z rand5. Podobnie jak w przypadku innych rozwiązań, istnieje małe prawdopodobieństwo, że może zapętlić się przez długi czas.

Prosty i wydajny:

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

(Zainspirowany swoją ulubioną kreskówką „programistą”? ).

Dopóki nie ma już siedmiu możliwości do wyboru, narysuj kolejną liczbę losową, która pomnaża liczbę możliwości przez pięć. W Perlu:

$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;
}

Nie lubię zakresów zaczynających się od 1, więc zacznę od 0 :-)

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;
}

Proszę bardzo, jednolita dystrybucja i zerowe połączenia rand5.

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

Musisz wcześniej ustawić ziarno.

Wiem, że odpowiedź została udzielona, ​​ale czy to wydaje się działać poprawnie, ale nie mogę powiedzieć, czy ma tendencyjność. Moje „testowanie” sugeruje, że jest to co najmniej uzasadnione.

Być może Adam Rosenfield byłby na tyle uprzejmy, aby skomentować?

Mój (naiwny?) Pomysł jest taki:

Kumuluj rand5, dopóki nie będzie wystarczającej liczby losowych bitów, aby utworzyć rand7. To zajmuje najwyżej 2 rand5. Aby uzyskać liczbę rand7, używam skumulowanej wartości mod 7.

Aby uniknąć przepełnienia akumulatora, a ponieważ akumulator ma mod 7, biorę mod 7 z akumulatora:

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

Funkcja rand7 () wygląda następująco:

(Pozwoliłem, aby zakres rand5 wynosił 0-4, a rand7 również 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;
}

Edycja: Dodano wyniki dla 100 milionów prób.

'Prawdziwe' funkcje randa mod 5 lub 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

Mój rand7

Średnia wygląda dobrze, a rozkłady liczb też wyglądają dobrze.

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

Istnieją eleganckie algorytmy cytowane powyżej, ale jest na to jeden sposób, choć może to być rondo. Zakładam wartości wygenerowane z 0.

R2 = generator liczb losowych podający wartości mniejsze niż 2 (przestrzeń próbki = {0, 1})
R8 = generator liczb losowych podający wartości mniejsze niż 8 (przestrzeń próbek = {0, 1, 2, 3, 4, 5, 6, 7 })

Aby wygenerować R8 z R2, uruchomisz R2 trzy razy i użyjesz połączonego wyniku wszystkich 3 przebiegów jako liczby binarnej z 3 cyframi. Oto zakres wartości, gdy R2 jest uruchamiany trzy razy:

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

Teraz, aby wygenerować R7 z R8, po prostu uruchamiamy R7 ponownie, jeśli zwraca 7:

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

Rozwiązaniem ronda jest wygenerowanie R2 z R5 (tak jak wygenerowaliśmy R7 z R8), następnie R8 z R2, a następnie R7 z R8.

Oto rozwiązanie, które całkowicie pasuje do liczb całkowitych i zawiera się w granicach około 4% wartości optymalnej (tzn. Używa 1,26 liczb losowych w {0..4} dla każdego w {0..6}). Kod jest w Scali, ale matematyka powinna być dość jasna w każdym języku: wykorzystujesz fakt, że 7 ^ 9 + 7 ^ 8 jest bardzo bliskie 5 ^ 11. Więc wybierasz 11-cyfrową liczbę w bazie 5, a następnie interpretujesz ją jako 9-cyfrową liczbę w bazie 7, jeśli jest ona w zakresie (dając 9 liczb 7 liczb podstawowych), lub jako 8-cyfrową liczbę, jeśli jest powyżej 9-cyfrowej liczby itp. .:

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)
  }
}

Jeśli wkleisz test do interpretera (faktycznie REPL), otrzymasz:

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

Rozkład jest ładny i płaski (w granicach około 10k z 1/7 z 10 ^ 8 w każdym przedziale, zgodnie z oczekiwaniami z rozkładu około Gaussa).

Używając ruchomej sumy , możesz jedno i drugie

• utrzymywać równy rozkład; i
• nie trzeba poświęcać żadnego elementu w losowej sekwencji.

Oba te problemy stanowią problem w przypadku uproszczonych rand(5)+rand(5)...rozwiązań. Poniższy kod Pythona pokazuje, jak go zaimplementować (większość z nich potwierdza dystrybucję).

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)

Ten wynik pokazuje wyniki:

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%)

Uproszczenie rand(5)+rand(5), ignorowanie przypadków, w których zwraca więcej niż 6, ma typową wariację 18%, 100 razy większą niż metoda pokazana powyżej:

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%)

I, za radą Nixuz, wyczyściłem skrypt, abyś mógł po prostu wypakować i użyć tych rand7...rzeczy:

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)

Ta odpowiedź jest raczej eksperymentem w uzyskiwaniu jak największej entropii z funkcji Rand5. t jest zatem nieco niejasny i prawie na pewno dużo wolniejszy niż inne implementacje.

Zakładając równomierny rozkład od 0-4 i wynikający z tego równomierny rozkład od 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;
  }
}

Liczba bitów dodanych do bufora na połączenie do Rand5 wynosi obecnie 4/5 * 2, a więc 1,6. Jeśli uwzględniona zostanie wartość prawdopodobieństwa 1/5, to wzrośnie o 0,05, więc 1,65, ale zobacz komentarz w kodzie, w którym musiałem to wyłączyć.

Bity zużywane przez połączenie z Rand7 = 3 + 1/8 * (3 + 1/8 * (3 + 1/8 *) (...
To jest 3 + 3/8 + 3/64 + 3/512 ... więc około 3,42

Wydobywając informacje z siódemek odzyskuję 1/8 * 1/7 bitów na połączenie, czyli około 0,018

Daje to zużycie netto 3,4 bitów na połączenie, co oznacza, że ​​stosunek wynosi 2.125 połączeń do Rand5 dla każdego Rand7. Optymalne powinno być 2.1.

Wyobrażam sobie, że takie podejście jest znacznie wolniejsze niż w przypadku wielu innych tutaj, chyba że koszt połączenia z Rand5 jest wyjątkowo drogi (powiedzmy wywołanie jakiegoś zewnętrznego źródła entropii).

w 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);
}

pętle tworzą losową liczbę między 16 a 127, dzieli przez szesnaście, aby utworzyć liczbę zmiennoprzecinkową między 1 a 7,9375, a następnie zaokrągla w dół, aby uzyskać liczbę całkowitą od 1 do 7. Jeśli się nie mylę, istnieje szansa 16/112 dowolny z 7 wyników.

extern int r5();

int r7() {
    return ((r5() & 0x01) << 2 ) | ((r5() & 0x01) << 1 ) | (r5() & 0x01);
}

Wydaje mi się, że mam cztery odpowiedzi, dwie z dokładnymi rozwiązaniami, takimi jak @Adam Rosenfield, ale bez problemu z nieskończoną pętlą, i dwie z prawie perfekcyjnym rozwiązaniem, ale szybszą implementacją niż pierwsza.

Najlepsze dokładne rozwiązanie wymaga 7 połączeń z rand5, ale przejdźmy dalej, aby zrozumieć.

Metoda 1 - Dokładnie

Siła odpowiedzi Adama polega na tym, że zapewnia on idealnie równomierny rozkład i istnieje bardzo duże prawdopodobieństwo (21/25), że potrzebne będą tylko dwa wywołania funkcji rand5 (). Jednak najgorszym przypadkiem jest nieskończona pętla.

Pierwsze rozwiązanie poniżej zapewnia również idealną jednolitą dystrybucję, ale wymaga w sumie 42 połączeń z rand5. Brak nieskończonych pętli.

Oto implementacja R:

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

Dla osób niezaznajomionych z R dostępna jest uproszczona wersja:

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
}

Dystrybucja rand5zostanie zachowana. Jeśli wykonamy matematykę, każda z 7 iteracji pętli ma 5 ^ 6 możliwych kombinacji, więc całkowita liczba możliwych kombinacji to (7 * 5^6) %% 7 = 0. W ten sposób możemy podzielić wygenerowane liczby losowe na równe grupy po 7. Patrz metoda druga, aby uzyskać więcej dyskusji na ten temat.

Oto wszystkie możliwe kombinacje:

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 

Myślę, że łatwo jest pokazać, że metoda Adama będzie działać znacznie szybciej. Prawdopodobieństwo, że rand5w rozwiązaniu Adama jest 42 lub więcej wywołań , jest bardzo małe ( (4/25)^21 ~ 10^(-17)).

Metoda 2 - Nie jest dokładna

Teraz druga metoda, która jest prawie jednolita, ale wymaga 6 wywołań w celu rand5:

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

Oto uproszczona wersja:

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

Jest to w zasadzie jedna iteracja metody 1. Jeśli wygenerujemy wszystkie możliwe kombinacje, oto wynikowe liczby:

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

Jedna liczba pojawi się ponownie w 5^6 = 15625próbach.

Teraz, w metodzie 1, dodając 1 do 6, przenosimy liczbę 2233 do każdego kolejnego punktu. Tak więc łączna liczba kombinacji będzie się zgadzać. Działa to, ponieważ 5 ^ 6 %% 7 = 1, a następnie robimy 7 odpowiednich odmian, więc (7 * 5 ^ 6 %% 7 = 0).

Metoda 3 - Dokładnie

Jeśli argument metody 1 i 2 jest zrozumiany, następuje metoda 3 i wymaga tylko 7 wywołań do rand5. W tym momencie uważam, że jest to minimalna liczba połączeń potrzebnych do uzyskania dokładnego rozwiązania.

Oto implementacja R:

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

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

Dla osób niezaznajomionych z R dostępna jest uproszczona wersja:

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

Dystrybucja rand5zostanie zachowana. Jeśli wykonamy matematykę, każda z 7 iteracji pętli ma 5 możliwych wyników, więc całkowita liczba możliwych kombinacji to (7 * 5) %% 7 = 0. W ten sposób możemy podzielić generowane losowo liczby na równe grupy po 7. Patrz metoda pierwsza i druga, aby uzyskać więcej dyskusji na ten temat.

Oto wszystkie możliwe kombinacje:

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 

Myślę, że łatwo jest pokazać, że metoda Adama nadal będzie działać szybciej. Prawdopodobieństwo, że rand5w rozwiązaniu Adama jest 7 lub więcej wywołań , jest wciąż małe ( (4/25)^3 ~ 0.004).

Metoda 4 - Nie jest dokładna

Jest to niewielka odmiana drugiej metody. Jest prawie jednolity, ale wymaga 7 wywołań rand5, co stanowi dodatkowe uzupełnienie metody 2:

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

Oto uproszczona wersja:

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

Jeśli wygenerujemy wszystkie możliwe kombinacje, oto liczby wynikowe:

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

Dwie liczby pojawią się raz mniej w 5^7 = 78125próbach. W większości przypadków mogę z tym żyć.

Potrzebną funkcją jest rand1_7 () , napisałem rand1_5 (), abyś mógł ją przetestować i wykreślić.

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