Question Étendre une plage aléatoire de 1-5 à 1-7


Étant donné une fonction qui produit un entier aléatoire compris entre 1 et 5, écris une fonction qui produit un entier aléatoire compris entre 1 et 7.

  1. Qu'est-ce qu'une solution simple?
  2. Qu'est-ce qu'une solution efficace pour réduire l'utilisation de la mémoire ou s'exécuter sur un processeur plus lent?

652


origine


Réponses:


Ceci est équivalent à la solution d'Adam Rosenfield, mais peut-être un peu plus clair pour certains lecteurs. Il suppose que rand5 () est une fonction qui renvoie un entier statistiquement aléatoire compris entre 1 et 5 inclus.

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

Comment ça marche? Pensez-y comme ceci: imaginez que vous imprimiez ce tableau double dimension sur papier, que vous l'accrochiez à un jeu de fléchettes et que vous jetiez des fléchettes au hasard. Si vous atteignez une valeur non nulle, il s'agit d'une valeur statistiquement aléatoire comprise entre 1 et 7, car il existe un nombre égal de valeurs non nulles à choisir. Si vous frappez un zéro, continuez à lancer la fléchette jusqu'à ce que vous atteigniez un zéro. C'est ce que fait ce code: les index i et j sélectionnent aléatoirement un emplacement sur le jeu de fléchettes, et si nous n'obtenons pas un bon résultat, nous continuons à lancer des fléchettes.

Comme Adam l'a dit, cela peut durer éternellement dans le pire des cas, mais statistiquement, le pire des cas n'arrive jamais. :)


530



Il n'y a pas de solution (exactement exacte) qui fonctionnera dans un laps de temps constant, puisque 1/7 est une décimale infinie dans la base 5. Une solution simple serait d'utiliser un échantillonnage de rejet, par exemple:


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

Cela a un temps d'exécution attendu de 25/21 = 1,19 itérations de la boucle, mais il y a une probabilité infinitésimale de boucle pour toujours.


328



Je voudrais ajouter une autre réponse, en plus de ma première réponse. Cette réponse tente de minimiser le nombre d'appels à rand5() par appel à rand7(), pour maximiser l'utilisation de l'aléatoire. Autrement dit, si vous considérez l'aléatoire comme une ressource précieuse, nous voulons en utiliser autant que possible, sans jeter de bits aléatoires. Cette réponse a également quelques similitudes avec la logique présentée dans La réponse d'Ivan.

le entropie d'une variable aléatoire est une quantité bien définie. Pour une variable aléatoire qui prend N états avec des probabilités égales (une distribution uniforme), l'entropie est log2 N. Ainsi, rand5() a environ 2.32193 bits d'entropie, et rand7() a environ 2.80735 bits d'entropie. Si nous espérons maximiser notre utilisation de l'aléatoire, nous devons utiliser tous les 2.32193 bits d'entropie de chaque appel à rand5()et les appliquer pour générer 2.80735 bits d'entropie nécessaires pour chaque appel à rand7(). La limite fondamentale, alors, est que nous ne pouvons pas faire mieux que log (7) / log (5) = 1.20906 appels à rand5() par appel à rand7().

Notes de côté: tous les logarithmes de cette réponse seront de base 2, sauf indication contraire. rand5() sera supposé renvoyer des nombres dans l'intervalle [0, 4], et rand7() sera supposé renvoyer des nombres dans l'intervalle [0, 6]. Ajuster les plages à [1, 5] et [1, 7] respectivement est trivial.

Alors comment le fait-on? Nous générons un infiniment précisnombre réel aléatoire entre 0 et 1 (prétendre pour le moment que nous pourrions réellement calculer et stocker un tel nombre infiniment précis - nous réglerons cela plus tard). On peut générer un tel nombre en générant ses chiffres en base 5: on choisit le nombre aléatoire 0.a1a2a3..., où chaque chiffrei est choisi par un appel à rand5(). Par exemple, si notre RNG a choisi uni = 1 pour tous i, puis en ignorant le fait que ce n'est pas très aléatoire, cela correspondrait au nombre réel 1/5 + 1/52 + 1/53 + ... = 1/4 (somme d'une série géométrique).

Ok, donc nous avons choisi un nombre réel aléatoire entre 0 et 1. Je prétends maintenant qu'un tel nombre aléatoire est uniformément distribué. Intuitivement, cela est facile à comprendre, puisque chaque chiffre a été choisi uniformément, et le nombre est infiniment précis. Cependant, une preuve formelle de ceci est un peu plus impliquée, puisqu'il s'agit maintenant d'une distribution continue au lieu d'une distribution discrète, nous devons donc prouver que la probabilité que notre nombre se trouve dans un intervalle [a, b] est égal à la longueur de cet intervalle, b - a. La preuve est laissée comme un exercice pour le lecteur =).

Maintenant que nous avons un nombre réel aléatoire sélectionné uniformément à partir de la plage [0, 1], nous devons le convertir en une série de nombres uniformément aléatoires dans la plage [0, 6] pour générer la sortie de rand7(). Comment faisons-nous cela? Juste l'inverse de ce que nous venons de faire - nous le convertissons en une décimale infiniment précise en base 7, puis chaque base 7 chiffres correspondra à une sortie de rand7().

Prenant l'exemple de plus tôt, si notre rand5() produit un flux infini de 1, alors notre nombre réel aléatoire sera 1/4. En convertissant 1/4 en base 7, nous obtenons l'infini décimal 0.15151515 ..., donc nous produirons en sortie 1, 5, 1, 5, 1, 5, etc.

Ok, donc nous avons l'idée principale, mais il nous reste deux problèmes: nous ne pouvons pas réellement calculer ou stocker un nombre réel infiniment précis, alors comment en traiter seulement une partie finie? Deuxièmement, comment pouvons-nous réellement le convertir en base 7?

Une façon de convertir un nombre compris entre 0 et 1 en base 7 est la suivante:

  1. Multipliez par 7
  2. La partie intégrale du résultat est le prochain chiffre de base 7
  3. Soustraire la partie intégrale en ne laissant que la partie fractionnaire
  4. Aller à l'étape 1

Pour traiter le problème de la précision infinie, nous calculons un résultat partiel, et nous stockons également une borne supérieure sur ce que pourrait être le résultat. Autrement dit, supposons que nous avons appelé rand5() deux fois et il est revenu 1 fois. Le nombre que nous avons généré jusqu'à présent est de 0,11 (base 5). Quel que soit le reste de la série infinie d'appels à rand5() produire, le nombre réel aléatoire que nous générons ne sera jamais plus grand que 0,12: il est toujours vrai que 0,11 ≤ 0,11xyz ... <0,12.

Donc, en gardant une trace du nombre actuel jusqu'à présent, et la valeur maximale qu'il pourrait jamais prendre, nous convertissons tous les deux numéros à la base 7. S'ils sont d'accord sur le premier k chiffres, alors nous pouvons en toute sécurité la sortie suivante kchiffres - quel que soit le flux infini des chiffres de base 5, ils n'affecteront jamais le prochain k chiffres de la représentation de base 7!

Et c'est l'algorithme - pour générer la prochaine sortie de rand7(), nous générons seulement autant de chiffres de rand5() Comme nous devons nous assurer que nous savons avec certitude la valeur du chiffre suivant dans la conversion du nombre réel aléatoire à la base 7. Voici une implémentation Python, avec un harnais de test:

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)

Notez que rand7_gen() renvoie un générateur, car il a un état interne impliquant la conversion du nombre en base 7. Les appels de harnais de test next(r7) 10000 fois pour produire 10000 nombres aléatoires, puis il mesure leur distribution. Seuls les maths entiers sont utilisés, donc les résultats sont exactement corrects.

Notez également que les chiffres obtenus ici très gros, très vite. Les pouvoirs de 5 et 7 se développent rapidement. Par conséquent, les performances vont commencer à se dégrader sensiblement après avoir généré beaucoup de nombres aléatoires, en raison de l'arithmétique bignum. Mais rappelez-vous ici, mon objectif était de maximiser l'utilisation de bits aléatoires, pas de maximiser la performance (bien que ce soit un objectif secondaire).

En une seule fois, j'ai fait 12091 appels à rand5() pour 10000 appels à rand7(), atteignant le minimum de log (7) / log (5) appelle en moyenne 4 chiffres significatifs, et la sortie qui en résulte est uniforme.

Afin de porter ce code à un langage qui n'a pas incorporé arbitrairement de grands entiers, vous devrez limiter les valeurs de pow5 et pow7 à la valeur maximale de votre type intégral natif - s'ils deviennent trop gros, réinitialisez tout et recommencez. Cela augmentera le nombre moyen d'appels à rand5() par appel à rand7() très légèrement, mais j'espère qu'il ne devrait pas augmenter trop même pour les entiers de 32 ou 64 bits.


145



(J'ai volé La réponse d'Adam Rosenfeld et l'a fait courir environ 7% plus vite.)

Supposons que rand5 () renvoie l'un de {0,1,2,3,4} avec une distribution égale et le but est de retour {0,1,2,3,4,5,6} avec une distribution égale.

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

Nous gardons trace de la plus grande valeur que la boucle peut faire dans la variable max. Si le résultat est jusqu'ici compris entre max 7 et max-1, alors le résultat sera uniformément distrubué dans cette plage. Sinon, nous utilisons le reste, qui est aléatoire entre 0 et max% 7-1, et un autre appel à rand () pour faire un nouveau nombre et un nouveau maximum. Ensuite, nous recommençons.

Edit: Attendez-vous à ce que nombre de fois appeler rand5 () soit x dans cette équation:

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

35



Algorithme:

7 peut être représenté dans une séquence de 3 bits

Utilisez rand (5) pour remplir aléatoirement chaque bit avec 0 ou 1.
Par exemple: appel rand (5) et

si le résultat est 1 ou 2, remplissez le bit avec 0
si le résultat est 4 ou 5, remplissez le bit avec 1
si le résultat est 3, alors ignorez et recommencez (rejet)

De cette façon, nous pouvons remplir aléatoirement 3 bits avec 0/1 et ainsi obtenir un nombre de 1-7.

MODIFIER:  Cela semble être la réponse la plus simple et la plus efficace, alors voici un peu de code:

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

25



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

19



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

15



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

Edit: Ça ne marche pas vraiment. C'est parti par environ 2 parts dans 1000 (en supposant un rand5 parfait). Les seaux obtiennent:

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

En passant à une somme de

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

semble gagner un ordre de grandeur pour chaque 2 ajouté

BTW: le tableau d'erreurs ci-dessus n'a pas été généré par échantillonnage mais par la relation de récurrence suivante:

p[x,n] est le nombre de façons output=x peut arriver donné n appels à 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]

15



Ce qui suit produit une distribution uniforme sur {1, 2, 3, 4, 5, 6, 7} en utilisant un générateur de nombres aléatoires produisant une distribution uniforme sur {1, 2, 3, 4, 5}. Le code est en désordre, mais la logique est claire.

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

13