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

c'est l'équivalent de la solution D'Adam Rosenfield, mais peut-être un peu plus clair pour certains lecteurs. Il suppose rand5() est une fonction qui renvoie un entier statistiquement aléatoire dans l'intervalle 1 à 5 inclusivement.

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 à cela comme ceci: imaginez l'impression de ce tableau de double dimension sur le papier, en l'accrochant à une planche à fléchettes et au hasard jeter des fléchettes à elle. Si vous frappez une valeur non nulle, c'est une valeur aléatoire statistiquement entre 1 et 7, puisqu'il y a un nombre égal de valeurs non nulles à choisir. Si vous touchez un zéro, continuez à lancer la fléchette jusqu'à ce que vous touchiez un non-zéro. C'est ce que fait ce code: les index i et j sélectionnent au hasard un emplacement sur le tableau de fléchettes, et si nous n'obtenons pas un bon résultat, nous continuons à lancer des fléchettes.

comme dit Adam, cela peut durer éternellement dans le pire des cas, mais statistiquement le pire des cas ne se produit jamais. :)

il n'y a pas de solution (exactement correcte) qui fonctionnera dans un temps constant, puisque 1/7 est une décimale infinie en base 5. Une solution simple consisterait à 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

ceci a une durée d'exécution prévue de 25/21 = 1.19 itérations de la boucle, mais il y a une infinité de petites probabilités de boucle pour toujours.

j'aimerais 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 l'appel à rand7() , afin de maximiser l'utilisation de l'aléatoire. C'est, si vous envisagez de l'aléatoire pour être une ressource précieuse, nous voulons utiliser autant que possible, sans jeter tout de bits aléatoires. Cette réponse présente également quelques similitudes avec la logique présentée dans réponse D'Ivan .

le entropie d'une variable aléatoire est une quantité bien définie. Pour une variable aléatoire qui prend sur N états avec des probabilités égales (une distribution uniforme), l'entropie est log ₂ N. ainsi, rand5() a environ 2.32193 bits d'entropie, et rand7() a environ 2.80735 bits d'entropie. Si nous voulons optimiser notre utilisation de l'aléatoire, nous devons utiliser toutes les 2.32193 bits d'entropie de chaque appel rand5() , et les appliquer à la génération 2.80735 bits d'entropie nécessaire pour chaque appel à rand7() . La limite fondamentale, donc, est que nous ne pouvons pas faire mieux que log(7)/log(5) = 1.20906 appels à rand5() par appel à rand7() .

Side notes: tous les logarithmes dans cette réponse seront base 2 sauf indication contraire. rand5() sera supposé retourner des nombres dans la gamme [0, 4], et rand7() sera supposé retourner des nombres dans l'intervalle [0, 6]. Ajuster les plages à [1, 5] et [1, 7] respectivement est trivial.

alors comment on fait? Nous générons un infiniment précis nombre aléatoire réel entre 0 et 1 (prétendre pour le moment que nous pourrions effectivement calculer et stocker un tel nombre infiniment précis -- nous allons corriger cela plus tard). Nous pouvons générer un tel nombre en générant ses chiffres en base 5: nous choisissons le nombre aléatoire 0. a ₁ a ₂ a ₃ ..., où chaque chiffre d'un _i est choisi par un appel à rand5() . Par exemple, si notre RNG a choisi _i = 1 pour tous i , en ignorant le fait que ce n'est pas très aléatoire, cela correspondrait au nombre réel 1/5 + 1/5 ² + 1/5 ³ + ... = 1/4 (somme d'une série géométrique).

Ok, donc nous avons choisi au hasard un nombre réel entre 0 et 1. J'ai maintenant affirmer qu'un tel nombre aléatoire uniformément distribuée. 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é, puisque maintenant nous avons affaire à une distribution continue au lieu d'une distribution discrète, donc nous devons prouver que la probabilité que notre nombre se trouve dans un intervalle [ a , b ] égale la longueur de cet intervalle, b - a . La preuve est laissée en exercice pour le lecteur =).

maintenant que nous avons un nombre réel aléatoire sélectionné uniformément à partir de la gamme [0, 1], nous devons le convertir en une série de nombres aléatoires uniformes dans la gamme [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 chiffre correspondra à une sortie de rand7() .

en prenant l'exemple de plus tôt, si notre rand5() produit un flux infini de 1's, alors notre nombre réel aléatoire sera 1/4. En convertissant 1/4 en base 7, on obtient la décimale infinie 0.151515... et donc , nous allons produire 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 pouvons-nous traiter qu'une partie limitée de celui-ci? Deuxièmement, comment le convertir en base 7?

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

1. multiplier par 7
2. la partie intégrante du résultat est la base suivante 7 chiffres
3. soustraire de la partie intégrale, ne laissant que la partie fractionnaire
4. passez à l'étape 1

pour traiter le problème de la précision infinie, nous calculons un résultat partiel, et nous stockons également une limite supérieure sur ce que le résultat pourrait être. C'est-à-dire, supposons que nous ayons appelé rand5() deux fois et qu'elle soit revenue une fois. Le nombre que nous avons généré jusqu'à présent est 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,11 xyz... < 0.12.

donc, en tenant compte du nombre actuel jusqu'à présent, et de la valeur maximale qu'il pourrait jamais prendre, nous convertissons les deux nombres à la base 7. S'ils sont d'accord sur les premiers k chiffres, alors nous pouvons en toute sécurité sortir les prochains k chiffres -- indépendamment de ce que le flux infini de base 5 chiffres sont, ils ne seront jamais affecter la prochaine 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() que nous avons besoin de s'assurer que nous savons avec certitude la valeur du prochain chiffre dans la conversion du nombre réel aléatoire en 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. Le tester harnais appelle next(r7) 10000 fois pour produire 10000 nombres aléatoires, puis il mesure leur distribution. Seuls les nombres entiers sont utilisés, de sorte que les résultats sont exactement corrects.

aussi noter que les nombres ici obtiennent très grand, très rapide. Les pouvoirs de 5 et 7 croissent rapidement. Par conséquent, la performance commencera à se dégrader sensiblement après avoir généré beaucoup de nombres aléatoires, en raison de l'arithmétique de bignum. Mais rappelez-vous ici, mon but était de maximiser l'utilisation des 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) appels en moyenne à 4 chiffres significatifs, et le résultat était uniforme.

pour porter ce code à un langage qui n'a pas arbitrairement de grands entiers intégrés, vous devrez capter les valeurs de pow5 et pow7 à la valeur maximale de votre type intégral natif -- si elles deviennent trop grandes, puis Réinitialiser tout et recommencer. Cela augmentera le nombre moyen d'appels à rand5() par appel à rand7() très légèrement, mais avec un peu de chance il ne devrait pas augmenter trop même pour les entiers de 32 ou 64 bits.

(j'ai volé la réponse D'Adam Rosenfeld et l'ai fait courir environ 7% plus vite.)

suppose que rand5() retourne un de {0,1,2,3,4} avec une distribution égale et le but est le 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 reult jusqu'à présent est entre max%7 et max-1, alors le résultat sera uniformément distribuée dans cette gamme. Si non, nous utilisons le reste, qui est aléatoire entre 0 et max%7-1, et un autre appel à rand() pour créer un nouveau numéro et un nouveau max. Puis nous repartons.

Edit: Attendez un certain nombre de fois d'appeler rand5() est 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()

algorithme:

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

utilisez rand (5) pour remplir au hasard chaque bit avec 0 ou 1.

For E. G: call rand( 5) et

si le résultat est 1 ou 2, remplir le bit avec 0

si le résultat est 4 ou 5, remplir le bit avec 1

si le résultat est 3, alors ignorer et le faire à nouveau (rejet)

de cette façon nous pouvons remplir 3 bits au hasard avec 0/1 et ainsi obtenir un nombre de 1-7.

EDIT: Ce qui semble être la plus simple et la plus efficace de répondre, 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;
        }
    }
}

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

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

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

Edit: ce n'est pas tout à fait. Il est éteint d'environ 2 parties en 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 remplaçant la 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 des 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 les numéros output=x peuvent arriver étant donné n appelle à 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]

produit suivant 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 illisible, 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;
}    

les problèmes de devoirs sont-ils permis ici?

cette fonction fait des mathématiques brutes de base 5 pour générer un nombre entre 0 et 6.

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

si nous considérons la contrainte supplémentaire d'essayer de donner la réponse la plus efficace I. e celui qui a donné un flux d'entrée, I , d'entiers uniformément distribués de longueur m de 1-5 sorties un flux O , d'entiers uniformément distribués de 1-7 de la plus longue longueur relative à m , dire L(m) .

la manière la plus simple d'analyser ceci est de traiter les flux I et O comme des nombres 5-ary et 7-ary respectivement. Ceci est réalisé par l'idée de la réponse principale de prendre le ruisseau a1, a2, a3,... -> a1+5*a2+5^2*a3+.. et de même pour le ruisseau O .

alors si nous prenons une section du flux d'entrée de longueur m choose n s.t. 5^m-7^n=c où c>0 et est aussi petit que possible. Puis il y a une carte uniforme du flux d'entrée de la longueur m aux entiers de 1 à 5^m et une autre carte uniforme des entiers de 1 à 7^n au flux de sortie de la longueur n où nous pouvons avoir à perdre quelques cas du flux d'entrée lorsque l'entier mappé dépasse 7^n .

ce qui donne une valeur pour L(m) d'environ m (log5/log7) qui est approximativement .82m .

la difficulté avec l'analyse ci-dessus est l'équation 5^m-7^n=c qui n'est pas facile à résoudre exactement et le cas où la valeur uniforme de 1 à 5^m dépasse 7^n et nous perdons l'efficacité.

la question Est de savoir dans quelle mesure la valeur de m (log5/log7) peut être atteinte. Par exemple lorsque ce nombre se rapproche d'un entier pouvons-nous trouver un moyen d'atteindre cet exact nombre entier de valeurs de sortie?

Si 5^m-7^n=c puis, à partir du flux d'entrée nous avons effectivement générer un nombre aléatoire uniforme de 0 à (5^m)-1 et ne pas utiliser toutes les valeurs supérieures à 7^n . Cependant, ces valeurs peuvent être sauvés et utilisés de nouveau. Ils génèrent effectivement une séquence uniforme de nombres de 1 à 5^m-7^n . Nous pouvons donc essayer de les utiliser et les convertir en nombres de 7 ary pour créer plus de valeurs de sortie.

si nous laissons T7(X) être la longueur moyenne de la séquence de sortie de random(1-7) entiers dérivés d'une entrée uniforme de taille X , et en supposant que 5^m=7^n0+7^n1+7^n2+...+7^nr+s, s<7 .

Puis T7(5^m)=n0x7^n0/5^m + ((5^m-7^n0)/5^m) T7(5^m-7^n0) puisque nous avons une longueur pas de séquence avec Probabilité 7^n0 / 5^m avec un résidu de longueur 5^m-7^n0 avec Probabilité (5^m-7^n0)/5^m) .

si nous continuons à remplacer nous obtenons:

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

D'où

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

une autre façon de mettre ceci est:

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)

le meilleur cas possible est mon original ci-dessus où 5^m=7^n+s , où s<7 .

puis T7(5^m) = nx(7^n)/(7^n+s) = n+o(1) = m (Log5/Log7)+o(1) comme avant.

le pire, c'est quand on ne trouve que k et S. t 5^m = kx7+S.

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

D'autres cas se situent quelque part entre les deux. Il serait intéressant de voir comment on peut faire pour un très grand m, c'est à dire bon comment pouvons-nous obtenir le terme d'erreur:

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

il semble impossible d'atteindre e(m) = o(1) en général, mais nous espérons pouvoir prouver e(m)=o(m) .

tout repose alors sur le distribution des 7 chiffres ary de 5^m pour différentes valeurs de m .

je suis sûr qu'il y a beaucoup de théorie là-bas qui couvre ce que je peux avoir un coup d'oeil et le rapport de retour à un certain point.

Voici une implémentation en python de réponse D'Adam .

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

j'aime lancer des algorithmes que je regarde en Python pour pouvoir jouer avec eux, j'ai pensé le poster ici dans l'espoir qu'il soit utile à quelqu'un là-bas, non pas qu'il ait fallu longtemps à jeter ensemble.

pourquoi pas simple?

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

les chances d'obtenir 1 et 7 dans cette solution est plus faible en raison du modulo, cependant, si vous voulez juste une solution rapide et lisible, c'est la voie à suivre.

en supposant que rand(n) signifie Ici "nombre entier aléatoire dans une distribution uniforme de 0 à n-1 ", voici un échantillon de code utilisant le randint de Python, qui a cet effet. Il utilise seulement randint (5) , et constantes, pour produire l'effet de randint(7) . Un peu bête, en fait

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

la prémisse derrière la réponse correcte D'Adam Rosenfield est:

• x = 5^N (dans son cas: n =2)
• manipule les appels n rand5 pour obtenir un numéro y dans la plage [1, x]
• z = ((int) (x / 7)) * 7
• si y > z, essayez de nouveau. sinon retour y % 7 + 1

Lorsque n égal à 2, vous avez 4 possibilités de jeter: y = {22, 23, 24, 25}. Si vous utilisez n = 6, Vous n'avez qu'un jet: y = {15625}.

5^6 = 15625

7 * 2232 = 15624

tu appelles rand5 plus de fois. Cependant, vous avez beaucoup moins de chance d'obtenir une contre-valeur (ou une boucle infinie). S'il y a un moyen de ne pas avoir de valeur à jeter pour y, Je ne l'ai pas encore trouvé.

voici ma réponse:

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

c'est un peu plus compliqué que les autres, mais je crois que ça minimise les appels à rand5. Comme avec d'autres solutions, Il ya une faible probabilité qu'il pourrait boucle pendant une longue période.

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

contrairement à la solution choisie, l'algorithme s'exécute en temps constant. Il fait cependant 2 appels de plus à rand5 que la durée moyenne d'exécution de la solution choisie.

notez que ce générateur n'est pas parfait (le nombre 0 a 0.0064% plus de chance que tout autre nombre), mais pour la plupart des buts pratiques la garantie de temps constant l'emporte probablement sur cette inexactitude.

explication

cette solution est dérivée du fait que le nombre 15.624 est divisible par 7 et donc si nous pouvons au hasard et uniformément générer des nombres de 0 à 15.624 et puis prendre mod 7 Nous pouvons obtenir un générateur de rand7 presque uniforme. Les nombres de 0 à 15 624 peuvent être générés uniformément en faisant rouler rand5 6 fois et en les utilisant pour former les chiffres d'un numéro de base 5 comme suit:

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

propriétés de mod 7 cependant nous permettent de simplifier un peu l'équation:

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

Donc

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

devient

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

théorie

le nombre 15,624 n'a pas été choisi au hasard, mais peut être découvert en utilisant le petit théorème de fermat, qui stipule que si p est un nombre premier alors

a^(p-1) = 1 mod p

Donc, cela nous donne,

(5^6)-1 = 0 mod 7

(5^6)-1 est égal à

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

ce est un nombre dans la forme de base 5 et nous pouvons donc voir que cette méthode peut être utilisée pour passer de n'importe quel générateur de nombres aléatoires à n'importe quel autre générateur de nombres aléatoires. Bien qu'un petit biais vers 0 est toujours introduit en utilisant l'exposant p-1.

aussi longtemps qu'il ne reste pas sept possibilités pour choisir, dessinez un autre nombre aléatoire, qui multiplie le nombre de possibilités par cinq. En Perl:

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

Simple et efficace:

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

(inspiré par Quel Est votre" programmeur " préféré? ).

Je n'aime pas les gammes commençant à 1, donc je vais commencer à 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;
}

voilà, répartition uniforme et aucun appel rand5.

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

Besoin de mettre la graine à l'avance.

je sais qu'il a été répondu, mais cela semble fonctionner ok, mais je ne peux pas vous dire si il a un parti pris. Mon "test" suggère que c'est, au moins, raisonnable.

peut-être Adam Rosenfield serait-il assez aimable pour commenter?

Mon (naïf?) l'idée est la suivante:

accumulent rand5's jusqu'à ce qu'il y ait assez de bits aléatoires pour faire un rand7. Cela prend au maximum 2 rand5. Pour obtenir le numéro rand7 j'utilise le valeur cumulée mod 7.

Pour éviter l'accumulateur de débordement, et depuis l'accumulateur est mod 7 alors je prends le mod 7 de l'accumulateur:

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

la fonction rand7 () suit:

(je laisse la gamme de rand5 être 0-4 et rand7 est également 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;
}

Edit: ajout de résultats pour 100 millions d'essais.

"Réelle" rand fonctions mod 5 ou 7

rand5: avg=1.999802 0:20003944 1:19999889 2:20003690 3:19996938 4:19995539 moyenne=3.000111 0:14282851 1:14282879 2:14284554 3:14288546 4:14292388 5:14288736 6:14280046

Mon rand7

la moyenne semble ok et les distributions de nombres semblent ok aussi.

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

il y a des algorithmes élégants cités ci-dessus, mais voici une façon de l'aborder, bien qu'il puisse être rond-point. Je suppose que les valeurs sont générées à partir de 0.

R2 = générateur de nombres aléatoires donnant des valeurs inférieures à 2 (Espace d'échantillonnage = {0, 1})

R8 = générateur de nombres aléatoires donnant des valeurs inférieures à 8 (espace d'échantillonnage = {0, 1, 2, 3, 4, 5, 6, 7})

afin de générer R8 à partir de R2, vous exécuterez R2 trois fois, et utilisez le combiné résultat de tous les 3 fonctionne comme un nombre binaire avec 3 chiffres. Voici la gamme de valeurs lorsque R2 est exécuté trois fois:

0 0 0 --> 0

.

.

1 1 1 --> 7

maintenant pour générer R7 à partir de R8, nous exécutons R7 à nouveau si elle retourne 7:

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

la solution du rond-point est de générer R2 à partir de R5( tout comme nous avons généré R7 à partir de R8), puis R8 à partir de R2 et R7 à partir de R8.

Voici une solution qui s'adapte entièrement à des entiers et est à environ 4% de optimal (i.e. utilise 1.26 nombres aléatoires dans {0..4} pour chaque personne dans {0..6}). Le code est en Scala, mais le calcul devrait être raisonnablement clair dans n'importe quelle langue: vous profitez du fait que 7^9 + 7^8 est très proche de 5^11. Vous choisissez donc un nombre à 11 chiffres dans la base 5, puis vous l'interprétez comme un nombre à 9 chiffres dans la base 7 Si c'est dans la gamme (donnant 9 numéros de la base 7), ou comme un nombre à 8 chiffres si c'est plus de 9 nombre de chiffre, etc.:

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

si vous collez un test dans l'interpréteur (REPL en fait), vous obtenez:

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

la distribution est belle et plate (environ 10k De 1/7 de 10^8 dans chaque bac, comme prévu d'une distribution approximativement gaussienne).

en utilisant un total roulant , vous pouvez tous les deux

• maintenir une distribution égale; et
• ne doit sacrifier aucun élément dans la séquence aléatoire.

ces deux problèmes sont un problème avec les solutions simplistes de type rand(5)+rand(5)... . Le code Python suivant montre comment l'implémenter (la plus grande partie de cela est de tester la distribution).

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)

et cette sortie montre les résultats:

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

a simplistic rand(5)+rand(5) , ignorant les cas où cela retourne plus de 6 a une variation typique de 18%, 100 fois celle de la méthode indiquée ci-dessus:

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

et, sur le Conseil de Nixuz, j'ai nettoyé le script pour que vous puissiez juste extraire et utiliser le rand7... truc:

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)

cette réponse est plus une expérience pour obtenir le plus d'entropie possible à partir de la fonction Rand5. t est donc quelque peu imprécis et presque certainement beaucoup plus lent que les autres implémentations.

en supposant une distribution uniforme à partir de 0-4 et une distribution uniforme à partir de 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;
  }
}

le nombre de bits ajoutés au tampon par appel à Rand5 est actuellement de 4/5 * 2 so 1.6. Si la valeur de probabilité de 1/5 est incluse que augmente de 0,05 afin de 1,65 mais voir le commentaire dans le code où j'ai dû désactiver cette.

Bits consommés par appel à Rand7 = 3 + 1/8 * (3 + 1/8 * (3 + 1/8 * (...

C'est 3 + 3/8 + 3/64 + 3/512 ... so environ 3,42

en extrayant des informations des sept je réclame 1/8 * 1/7 bits par appel donc environ 0,018

cela donne une consommation nette de 3,4 bits par appel ce qui signifie que le rapport est de 2,125 appels à Rand5 pour chaque Rand7. L'optimum devrait être 2.1.

j'imagine que cette approche est significativement plus lent que beaucoup d'autres ici à moins que le coût de L'appel à Rand5 est extrêmement cher (dire appel à une source externe d'entropie).

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

boucles pour produire un nombre aléatoire entre 16 et 127, divise par seize pour créer un flotteur entre 1 et 7.9375, puis ronds vers le bas pour obtenir un int entre 1 et 7. si Je ne me trompe pas, il y a une chance 16/112 d'obtenir l'un des 7 résultats.

extern int r5();

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

la fonction dont vous avez besoin est rand1_7 () , j'ai écrit rand1_5() pour que vous puissiez le tester et le tracer.

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

mettez à l'échelle votre sortie de votre première fonction

0) you have a number in range 1-5
1) subtract 1 to make it in range 0-4
2) multiply by (7-1)/(5-1) to make it in range 0-6
3) add 1 to increment the range: Now your result is in between 1-7