Rozwiń losowy zakres od 1–5 do 1–7

692

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?
Roger Pate
źródło
Okazało się to nieoczekiwanie interesującym problemem, wciąż myślę, jak 1) zrobić to w ustalonym czasie i 2) nie zepsuć jednolitego rozkładu (jeśli był)
eugensk
Mieliśmy podobny problem przy wyborze jednego gracza na 5 z kośćmi. Rzucaliśmy kostkami po kolei, wybrany jest ten, kto uzyska maksymalną liczbę punktów. Jednorodność została osiągnięta, ale nie stałość czasu :)
eugensk
Czy zostałbym odrzucony, gdybym opublikował odpowiedź mówiącą, że problem nie wymaga, abyś użył danej funkcji i napisał taką, która zwraca 1-7 losowo?
Doctor Blue,
Co 7 * rand5() / 5?
kiwixz
@kiwixz, który da „między 1 a 7”, ale nie dostaniesz 3 lub 6: {1: 19,96, 2: 20,02, 4: 20,01, 5: 19,99, 7: 20,02} testowania ręcznego. 7 * .2, 7 * .4, 7 * .6, 7 * .8, 7 * 1.
pythonlarry 18.04.16

Odpowiedzi:

572

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. :)

Rob McAfee
źródło
5
Zrozumiałem logikę tego rozwiązania, ale nie mogę pojąć, jak to skutkuje jednolitym prawdopodobieństwem? Czy ktoś może wyjaśnić matematykę?
user1071840,
6
@ user1071840 - jeśli rand5jest jednolity, każda komórka w valssiatce ma jednakowe prawdopodobieństwo pobrania. Siatka zawiera dokładnie trzy kopie każdej liczby całkowitej w przedziale [1, 7] oraz cztery zera. Tak więc „nieprzetworzony” strumień wyników prowadzi do równomiernej mieszanki wartości [1, 7] plus niektórych zer, które występują odrobinę częściej niż jakakolwiek pojedyncza dozwolona wartość. Ale to nie ma znaczenia, ponieważ zera są usuwane, pozostawiając tylko równomierną mieszankę wartości [1, 7].
Daniel Earwicker
3
Skrót do rozwiązania problemu: jeśli wywołujesz rand5 () tylko raz, masz tylko 5 możliwych wyników. Nie ma oczywiście sposobu, aby zmienić to w więcej niż 5 możliwych wyników bez dodania większej liczby losowości.
Daniel Earwicker,
1
Dłuższa wersja: rand5 () może mieć tylko wartości (1, 2, 3, 4, 5). Dlatego rand5 () * 5 może mieć tylko wartości (5, 10, 15, 20, 25), co nie jest tym samym co pełny zakres (1 ... 25). Gdyby tak było, odjęcie 4 dałoby wynik (-3 ... 21), ale w tym przypadku staje się (1, 6, 11, 16, 21), więc punkty końcowe są prawidłowe, ale istnieją cztery duże dziury: ( 2..5), (7..10), (12..15), (17..21). Na koniec robisz mod 7 i dodajesz 1, dając (2, 7, 5, 3, 1). Zatem ani 4, ani 6 nigdy nie występują. Ale (patrz powyższy skrót) wiedzieliśmy, że w wynikowym zakresie może być tylko 5 liczb przez cały czas, więc musiały być dwie luki.
Daniel Earwicker,
1
Ach, ponieważ mamy tylko rand5 (), a nie rand2 () :-)
gzak
353

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.

Adam Rosenfield
źródło
7
-1 nie jest potrzebne, jeśli> 21 jest przestawiony na> 26 b / c, nie ma znaczenia, gdzie są dolne granice map,
BCS
26
Wyjaśniam, dlaczego jest to poprawne: Powiedz, że chcę napisać program, który generuje strumień jednolitych liczb losowych od 1 do 25; za to po prostu zwrócę 5 * (rand5 () - 1) + rand5 () jak w kodzie w odpowiedzi. Teraz, jeśli chcę zbudować strumień jednolitych liczb losowych od 1 do 21, jeśli po prostu użyję pierwszego strumienia, ale przefiltruję go, aby liczby w [22, 25] zostały odrzucone, mogę również zbudować ten strumień. Następnie, jeśli wezmę ten strumień i przefiltruję go, aby dla każdego elementu x wyprowadziłem x% 7 + 1, mam strumień o jednolitych liczbach losowych od 1 do 7! Całkiem proste, prawda? : D
Paggas
6
I masz rację, że sprowadza się to do tego, czy chcesz mieć idealną dystrybucję z nieograniczonym najgorszym środowiskiem uruchomieniowym, czy niedoskonałą dystrybucję z ograniczonym środowiskiem uruchomieniowym. Jest to konsekwencja faktu, że wszystkie potęgi 5 nie dzielą się przez 7, lub równoważnie, jeśli masz 5 ^ n jednakowo prawdopodobnie sekwencji o długości n, nie ma sposobu, aby przypisać do każdej sekwencji liczbę od 1 do 7, tak aby każda z 1..7 jest równie prawdopodobne.
Adam Rosenfield
5
@Jules Olléon: Załóżmy, że istnieje rozwiązanie działające w stałym czasie, które w najgorszym przypadku gwarantowało wykonywanie jedynie Npołączeń rand5(). Następnie istnieje 5 ^ N możliwych wyników sekwencji wywołań rand5, z których każde ma wynik 1-7. Tak więc, jeśli dodasz wszystkie możliwe sekwencje wywołań, których wyjście jest kdla każdego 1≤k≤7, prawdopodobieństwo, że wyjście będzie wynosiło km / 5 ^ N, gdzie m jest liczbą takich sekwencji. Zatem m / 5 ^ N = 1/7, ale nie ma możliwych rozwiązań liczb całkowitych (N, m) dla tej ==> sprzeczności.
Adam Rosenfield
4
@paxdiablo: Mylisz się. Szansa, że ​​prawdziwy RNG wygeneruje nieskończoną sekwencję 5, wynosi dokładnie 0, przy użyciu podobnego rozumowania do faktu, że rzut monetą nieskończoną liczbę razy gwarantuje, że nie wygeneruje nieskończonej liczby kolejnych głów . Oznacza to również, że szansa na zapętlenie tego kodu na zawsze wynosi dokładnie 0 (chociaż istnieje dodatnia szansa, że ​​zapętli się dla dowolnej dowolnej liczby iteracji).
BlueRaja - Danny Pflughoeft
153

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 2 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. a1 a2 a3 ..., 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 2 + 1/5 3 + ... = 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.

Adam Rosenfield
źródło
7
+1 za naprawdę interesującą odpowiedź. Czy byłoby możliwe, zamiast resetowania przy określonej wartości, po prostu przesunąć bity, które zostały wykorzystane, i przesunąć inne bity w górę, i zasadniczo zachować tylko te bity, które będą używane? A może coś mi brakuje?
Chris Lutz
1
Nie jestem w 100% pewien, ale wierzę, że jeśli to zrobisz, bardzo nieznacznie wypaczyłbyś rozkład (chociaż wątpię, aby takie pochylenie można było zmierzyć bez trylionów prób).
Adam Rosenfield
FTW! Próbowałem zmniejszyć bignum, ale nie da się tego zrobić, ponieważ żadna potęga 5 nie ma czynników wspólnych z siłą 7! Również dobre użycie słowa kluczowego wydajności. Bardzo dobrze zrobione.
Eyal
2
Bardzo dobrze! Czy możemy zachować dodatkową entropię bez rozwijania stanu? Sztuką jest zauważenie, że zarówno górna, jak i dolna granica są zawsze liczbami wymiernymi. Możemy je dodawać, odejmować i mnożyć bez utraty precyzji. Jeśli zrobimy to wszystko w bazie 35, jesteśmy prawie na miejscu. Resztę (pomnożenie przez siedem i zachowanie części ułamkowej) pozostawia się jako ćwiczenie.
Ian
@adam Musisz odwoływać się do „ogranicz wartości pow5 i pow7 do maksymalnej wartości swojego rodzimego typu całki”. Po drugie, wierzysz, że to wypaczy rozkład, przynajmniej jeśli zrobisz to naiwnie.
katalizator
36

(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()
Eyal
źródło
2
Wyniki skatalogowane w 1 000 000 prób: 1 = 47216; 2 = 127444; 3 = 141407; 4 = 221453; 5 = 127479; 6 = 167536; 7 = 167465. Jak widać, brakuje rozkładu w odniesieniu do szans na zdobycie 1.
Robert K
2
@ The Wicked Flea: Myślę, że się mylisz. Czy jesteś pewien, że wejście rand5 (), którego użyłeś do testu, wygenerowało 0-4 zamiast 1-5, jak określono w tym rozwiązaniu?
Adam Rosenfield
5
dodanie liczb równomiernie rozłożonych nie powoduje uzyskania liczby równomiernie rozłożonej. W rzeczywistości wystarczy zsumować 6 takich równomiernie rozłożonych zmiennych, aby uzyskać rozsądne przybliżenie do rozkładu normalnego.
Mitch Wheat
2
@MitchWheat - Dodanie dwóch równomiernie rozłożonych liczb całkowitych powoduje w rzeczywistości równomiernie rozłożoną losową liczbę całkowitą, pod warunkiem że każdą możliwą sumę można wygenerować dokładnie w jeden sposób. Tak się dzieje w wyrażeniu 5 * rand5() + rand5().
Ted Hopp,
28

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;
        }
    }
}
Lance Roberts
źródło
1
Zawsze występowało słabe widmo problemu zatrzymania, ponieważ słaby generator liczb losowych mógł w pewnym momencie wygenerować wiele trójek.
Alex North-Keys,
„jeśli wynikiem jest 1 lub 2, wypełnij bit 0, jeśli wynikiem jest 4 lub 5, wypełnij bit 1” Jaka jest logika, według której 1,2,4,5 zostały zaakceptowane, a 3 zostało odrzucone? Czy możesz to wyjaśnić?
gkns,
@gkns Nie ma logiki, możesz mieć 1 i 2 średnie wypełnienie 0 bitami, a 3 i 4 średnie wypełnienie 1. Ważną rzeczą jest to, że każda opcja ma 50% szans na wystąpienie, co gwarantuje losowość twojej funkcji co najmniej tak losowa jak oryginalna funkcja rand (5). To świetne rozwiązanie!
Mo Beigi,
To nie jest ani proste, ani skuteczne. Liczba klientów do random_5 na random_7 wynosi co najwyżej 3, zwykle więcej. Inne rozwiązania na tej stronie są bliżej najlepszych, czyli około 2,2.
Eyal
1
Nieważne, brakowało mi części „while returnValue == 0”
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.
źródło
2
Prawidłowe rozwiązanie, wykonujące średnio 30/7 = 4,29 wywołań do rand5 () na wywołanie do rand7 ().
Adam Rosenfield
17
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]
BCS
źródło
8
To nie jest jednolity rozkład. Jest bardzo zbliżony do munduru, ale nie idealnie jednolity.
Adam Rosenfield
Ach! Kości i siódemki. Jeśli zamierzasz powiedzieć, że się mylę, nie powinieneś zostawiać dowodu jako ćwiczenia dla czytelnika.
BCS,
45
Dowód, że nie jest jednolity, jest prosty: istnieje 5 ^ 7 możliwych sposobów losowości, a ponieważ 5 ^ 7 nie jest wielokrotnością 7, nie jest możliwe, aby wszystkie 7 sum były jednakowo prawdopodobne. (Zasadniczo sprowadza się do liczby 7, która jest względnie pierwsza do liczby 5 lub równoważnie 1/7 nie jest zakończeniem dziesiętnym w podstawie 5.) W rzeczywistości nie jest to nawet „najbardziej jednorodny” możliwy przy tym ograniczeniu: bezpośrednie obliczenia pokazują, że 5 ^ 7 = 78125 sum, liczba otrzymanych wartości od 1 do 7 wynosi {1: 11145, 2: 11120, 3: 11120, 4: 11145, 5: 11190, 6: 11215, 7: 11190}.
ShreevatsaR
@ShreevatsaR Co z tego, jeśli zamiast sumy rand5 () siedem razy, zrobilibyśmy 5 * 7 ujęć - czy to nie zadziałałoby? 35 ^ 7% 7 = 35 ^ 5% 7 = 0.
kba
4
@KristianAntonsen: Ile razy robisz rand5 (), nie uzyskasz jednolitego rozkładu. Jeśli zrobisz to N razy, będzie 5 ^ N możliwych wyników, których nie da się podzielić przez 7. (Jeśli zrobisz to 35 razy, będzie 5 ^ 35, a nie 35 ^ 7). Będziesz coraz bliżej ujednolicić większą liczbę wywołań, których używasz (i może to być dowolny numer, nie musi być podzielny przez 7), ale IMHO zamiast używać bardzo dużej liczby wywołań do rand (), równie dobrze możesz użyć probabilisty algorytm w najlepszych odpowiedziach, który daje dokładny jednolity rozkład i którego spodziewana liczba wywołań do rand () jest niewielka.
ShreevatsaR
15
int ans = 0;
while (ans == 0) 
{
     for (int i=0; i<3; i++) 
     {
          while ((r = rand5()) == 3){};
          ans += (r < 3) >> i
     }
}
Nescio
źródło
2
Prawidłowe rozwiązanie, wykonujące średnio 30/7 = 4,29 wywołań do rand5 () na wywołanie do rand7 ().
Adam Rosenfield
3
Aby algorytm działał, należy go zostawić na zmianę :ans += (r < 3) << i
woolfie
13

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;
}    
Jason
źródło
2
Prawidłowe rozwiązanie (które stawia Cię daleko przed zakrętem), choć niezbyt wydajne. To sprawia, że ​​średnio 25/6 = 4,17 połączeń do random_5_mod_2 na rzetelną monetę, dla łącznej średniej 100/7 = 14,3 połączeń z random_5 () na połączenie z random_7 ().
Adam Rosenfield
Zaletą tego rozwiązania w porównaniu z innymi jest to, że można go łatwo rozszerzyć w celu uzyskania dowolnego innego równomiernie rozłożonego zakresu. Po prostu losowo wybierz każdy z bitów, ponownie wykorzystując nieprawidłowe wartości (np. Wartość 0 w naszym obecnym rozwiązaniu, które daje 8 liczb).
DenTheMan
1
możliwe nieskończone pętle itp.
robermorales
1
@robermorales: Niezwykle mało prawdopodobne.
jason
13
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)
Thirlan
źródło
1
Ten generator jest dokładny, ale nie idealnie jednolity. Aby to zobaczyć, weź pod uwagę fakt, że jednolity generator w [0,15624] ma 15625 możliwych wyników, których nie można podzielić przez 7. To wprowadza błąd w stosunku do liczby 0 (która ma szansę 2233/15625, a pozostałe tylko 2232/15625). W końcu, chociaż małe twierdzenie Fermata może wydawać się poprawne na pierwszy rzut oka, mówi, że (5 ^ 6)% 7 = 1, a nie (5 ^ 6)% 7 = 0. To ostatnie jest oczywiście niemożliwe dla żadnego wykładnika, ponieważ 5 i 7 są liczbami pierwszymi. Myślę, że nadal jest to akceptowalne rozwiązanie i zredagowałem twój post, aby to odzwierciedlić.
lotnik
12

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;
}
Will Hartung
źródło
3
Prawidłowe rozwiązanie (które stawia Cię daleko przed zakrętem), choć niezbyt wydajne. To daje średnio 5 wywołań do rnd5 () dla każdego wywołania do rnd7 ().
Adam Rosenfield
Potrzebuję więcej wyjaśnień
Barry
1
@Barry - Po pierwsze, nie możesz po prostu dodać razem dwóch liczb losowych, nie otrzymujesz liniowego rozwiązania (rozważ parę kości). Rozważmy teraz „Bazę 5”: 00, 01, 02, 03, 04, 10, 11. To 0-6 w bazie 5. Musimy po prostu wygenerować 2 cyfry numeru bazy 5 i dodawać je, aż otrzymamy zdobądź taki, który jest w zasięgu. Tak właśnie działa R2 * 5 + R1. Pętla r2> 1 istnieje, ponieważ nigdy nie chcielibyśmy wysokiej cyfry> 1.
Czy Hartung
To rozwiązanie nie generuje jednolitego rozkładu. Liczby 1 i 7 można wygenerować tylko w jeden sposób, ale każdy z 2 do 6 można wygenerować na dwa sposoby: z r1 równym liczbie minus 1 i r2 równym 0 lub z r1 równym liczbie minus 2 i r2 równej 1. Zatem 2 do 6 będą zwracane średnio dwa razy częściej niż 1 lub 7.
Ted Hopp
12

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ę.

Ivan
źródło
+2 (gdybym mógł) - to była jedyna dobra odpowiedź (w przeciwieństwie do po prostu wystarczającej). Masz drugą najlepszą odpowiedź, która zmieści się w 32-bitowych liczbach całkowitych.
Rex Kerr
10

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.

James James McMahon
źródło
Nie, to bardzo różni się od mojej odpowiedzi. Zapętlasz 21 razy i odrzucasz wyniki pierwszych 20 iteracji. Używasz również rand4 () i rand5 () jako danych wejściowych, co oczywiście łamie zasady używania tylko rand5 (). Na koniec produkujesz nierównomierny rozkład.
Adam Rosenfield
Przepraszam za to. Byłem dość zmęczony, kiedy przejrzałem to pytanie, wystarczająco zmęczony, że całkowicie błędnie odczytałem twój algorytm. Wrzuciłem to do Pythona, ponieważ nie mogłem zrozumieć, dlaczego zapętlałeś 21 razy. Teraz ma o wiele więcej sensu. Zrobiłem przypadkowe. Zalecenie (1, 4) jako skrót, ale myślę, że masz rację, jest to sprzeczne z duchem pytania. Poprawiłem kod.
James McMahon
@robermorales - Jak wyjaśnił Adam Rosenfeld w swojej odpowiedzi , każde rozwiązanie, które daje prawdziwie jednolity rozkład na [1, 7], będzie wymagało pewnego rodzaju pętli akceptacji-odrzucenia, która jest potencjalnie nieskończona. (Jeśli jednak rand5()jest przyzwoity PRNG, to pętla nie będzie nieskończona, ponieważ ostatecznie 5*(rand5() - 1) + rand5()będzie na pewno <= 21.)
Ted Hopp
10

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.

Ante
źródło
13
Nie powoduje to równomiernego rozkładu. Daje to liczby 0–6 z prawdopodobieństwem 2/25, 4/25, 5/25, 5/25, 5/25, 3/25, 1/25, co można zweryfikować poprzez zliczenie wszystkich 25 możliwych wyników.
Adam Rosenfield,
8

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
Joshua Fox
źródło
1
@robermorales Ponieważ Python nie ma do ... while. To mogło być 1337, lub 12345, lub dowolną liczbę> 1.
tckmn
8

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.

Dinah
źródło
1
Z pewnością nie ma przypadku bez wartości wyrzucanych - gdyby nie było wyrzucanych wartości, 5 ^ n i 7 ^ m miałyby wspólny czynnik. Ale są (mocami) liczb pierwszych, więc nie.
Rex Kerr
8

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.

Chris Suter
źródło
Powoduje to, że dystrybucja niewiele różni się od innych rozwiązań, ale ma tę dodatkową wadę, że jest niepotrzebnie złożona. Cierpi również na możliwą do udowodnienia niepoprawną niedeterministyczną pętlę na zawsze, jeśli liczby są naprawdę losowe. Nadal uważam, że te, które wytwarzają nieco mniej jednolity rozkład (choć nadal znacznie więcej niż wystarczające), ale gwarantują deterministyczne zachowanie, są lepsze.
paxdiablo
@Pax: Proszę mnie oświecić, jak to powoduje nierównomierny rozkład. Moja analiza kodu, a także własne testy wskazują, że daje to jednolity rozkład. Jak już wspomniano wcześniej, niemożliwe jest zarówno uzyskanie idealnie jednolitego rozkładu, jak i zagwarantowanie stałej górnej granicy czasu działania w stałym czasie.
Adam Rosenfield,
6

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;
}
użytkownik223264
źródło
Twoja dystrybucja nie jest jednolita, przynajmniej przy pierwszym połączeniu. Rzeczywiście, $possibilitieszawsze musi wzrosnąć do 25, aby wyjść z pętli i powrócić. Zatem twoim pierwszym wynikiem jest [0-124] % 7, który nie jest równomiernie rozłożony, ponieważ 125 % 7 != 0(w rzeczywistości jest to 6).
Bernard Paul
6

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;
}
fredoverflow
źródło
To jest zwycięzca. Daje to wszystkie 7 wyników z jednakowym prawdopodobieństwem. 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

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.

Kugel
źródło
5

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

philcolbourn
źródło
Prawdopodobnie powinieneś spojrzeć na korelację sekwencyjną. Myślę, że jeśli weźmiesz kolejne pary (każda „losowa” liczba w połączeniu z jej poprzednikiem), możesz znaleźć zaskakujące rzeczy. Nie wyjaśniłeś DLACZEGO, w każdym razie powinien on zachować jednolitość dystrybucji. Działający program zwykle powinien zaczynać się od wyjaśnienia, dlaczego działa.
Ian
Czy korelacja sekwencyjna miałaby zastosowanie do wielu z tych rozwiązań?
philcolbourn
Czy korelacja sekwencyjna miałaby zastosowanie do wielu z tych rozwiązań? Minęło trochę czasu, odkąd próbowałem tego i myślałem, że to wyjaśniłem. Patrząc na to teraz, wygląda na to, że gromadzę losowe bity w puli od rand5, upewniając się, że zgromadzono wystarczającą ilość, zanim wycofam wystarczająco dużo, aby utworzyć liczbę rand7 i upewniając się, że nie przepełniam mojego akumulatora.
philcolbourn
4

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.

Ashwin
źródło
podobnie jak wiele innych, takie podejście może zająć dowolnie długo na wywołanie R7, ponieważ można uzyskać długi ciąg siódemek z R8.
Alex North-Keys,
4

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

Rex Kerr
źródło
3

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)
paxdiablo
źródło
2
Err, pozwól mi to przeformułować. Biorąc pod uwagę, że określony x został wytworzony w pewnym momencie sekwencji, tylko 5 z 7 liczb może być wygenerowanych dla następnej liczby w sekwencji. Prawdziwy RNG sprawiłby, że wszystkie próbki byłyby od siebie niezależne, ale w tym przypadku wyraźnie nie są.
Adam Rosenfield
3
Prawdą jest, że pierwotne pytanie nie określa, czy funkcje wejściowe i wyjściowe wytwarzają niezależne i identycznie rozmieszczone próbki (iid), ale myślę, że uzasadnione jest oczekiwanie, że jeśli wejściowy rand5 () jest iid, to wyjściowy rand7 () powinien być również. Jeśli uważasz, że to nie jest rozsądne, baw się dobrze, używając swojego non-iid RNG.
Adam Rosenfield
1
Jakie jest zatem słowo matematyków z uniwersytetu?
Adam Rosenfield,
1
To rozwiązanie jest wyraźnie zepsute. Oczywiste jest, że musisz dzwonić do rand5 (średnio) więcej niż raz na połączenie z rand7, a to rozwiązanie nie. Dlatego wyniki nie mogą być losowe przy żadnej rozsądnej definicji losowości.
Chris Suter
1
@Pax Przy każdej iteracji twojej funkcji może zwrócić tylko jedną z pięciu różnych wartości (aczkolwiek w zakresie 0-6). Pierwsza iteracja może zwrócić tylko liczbę z zakresu 0-4. Powinno więc być jasne, że chociaż twoja funkcja może mieć jednolity rozkład, próbki nie są niezależne, tj. Są skorelowane, co nie jest czymś pożądanym w generatorze liczb losowych.
Chris Suter
3

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

ShuggyCoUk
źródło
Twoje rozwiązanie wydaje się poprawne, pomijając kilka prostych błędów: „if (count> 1)” powinno być „if (count <= 1)”, a „i ++”, które pojawia się wkrótce potem, powinno znajdować się w nawiasach klamrowych, które go poprzedzają. Nie jestem pewien, czy BitsSet () jest poprawny, ale jest to nieco nieistotne.
Adam Rosenfield
Ogólnie jednak twoja funkcja jest bardzo trudna do zrozumienia. To robi nieco lepsze wykorzystanie entropii niż to inaczej może, kosztem większej komplikacji. Nie ma również powodu, aby początkowo wypełniać bufor 35 losowymi bitami przy pierwszym wywołaniu, gdy 3 wystarczyłoby.
Adam Rosenfield
Poprawiłem <= dzięki, i ++ naprawdę powinien tam być. Powinno tak się zdarzyć w przypadku zero i 1 (dodanie odpowiednio 1 lub zera do bufora). To absolutnie nie to sugerowałbym użycie, jest to strasznie skomplikowane. Byłem tylko zainteresowany, jak blisko mogłem zbliżyć się do teoretycznych limitów entropii związanych z problemem ... Dziękuję za informację zwrotną. Jak na ironię, wypełnienie bufora przy pierwszym wywołaniu miało ułatwić pisanie :)
ShuggyCoUk
Przerobiłem to, aby było łatwiejsze do zrozumienia (kosztem prędkości), ale również poprawiłem. Nie jest jeszcze optymalny, z jakiegoś powodu bity 1/5 powodują problemy, mimo że są jednolite pod względem liczby.
ShuggyCoUk
3

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.

dqhendricks
źródło
chociaż prawdopodobnie jest łatwiejsza odpowiedź podobna do tej bez użycia pętli warunkowej i modulo zamiast floor. po prostu nie mogę teraz zgnieść liczb.
dqhendricks
3
extern int r5();

int r7() {
    return ((r5() & 0x01) << 2 ) | ((r5() & 0x01) << 1 ) | (r5() & 0x01);
}
maxchengcn
źródło
problem: zwraca nierównomiernie zakres 0–7, a nie 0–6. Rzeczywiście, można mieć 7 = 111bzp(7) = 8 / 125
Bernard paulus
3

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ć.

Shambho
źródło
1
Nie znam R, ale chyba, że ​​nie rozumiem, jak one działają, to metoda 1 nie jest dokładna. Ma (5 ^ 6) ^ 7 = 5 ^ 42 możliwych wyników, a nie (5 ^ 6) * 7; 5 ^ 42 nie jest podzielne przez 7. Podobnie metoda 3 nie jest dokładna. Ma 5 ^ 7 możliwych wyników, a nie 5 * 7. (Ostatnia iteracja pętli w metodzie 3 i=7również nie ma żadnego efektu, ponieważ dodanie 7*rand5()do rnie zmienia wartości rmod 7.)
Adam Rosenfield
2

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
Andrea Ambu
źródło