给定一个函数，它产生的是1到5之间的随机整数，写一个函数，它产生的是1到7之间的随机整数。
当前回答
这个答案更像是一个从Rand5函数中获得最大熵的实验。因此，T有点不清楚，几乎可以肯定比其他实现慢得多。
假设0-4为均匀分布，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;
}
}
每次调用Rand5添加到缓冲区的比特数目前是4/5 * 2，所以是1.6。 如果包括1/5的概率值，则增加0.05，因此增加1.65，但请参阅代码中的注释，我不得不禁用它。
调用Rand7消耗的比特数= 3 + 1/8 *(3 + 1/8 *(3 + 1/8 *(… 这是3 + 3/8 + 3/64 + 3/512…大约是3.42
通过从7中提取信息，我每次调用回收1/8*1/7位，大约0.018
这使得每次调用的净消耗为3.4比特，这意味着每一次Rand7调用到Rand5的比率为2.125。最优值应该是2.1。
我可以想象这种方法比这里的许多其他方法都要慢得多，除非调用Rand5的代价非常昂贵(比如调用一些外部熵源)。
其他回答
PHP解决方案
<?php
function random_5(){
return rand(1,5);
}
function random_7(){
$total = 0;
for($i=0;$i<7;$i++){
$total += random_5();
}
return ($total%7)+1;
}
echo random_7();
?>
简单的解决方案已经被很好地覆盖了:为一个random7结果取两个random5样本，如果结果超出了产生均匀分布的范围，就重新做一次。如果你的目标是减少对random5的调用次数，这是非常浪费的——对于每个random7输出，对random5的平均调用次数是2.38，而不是2，这是由于丢弃样本的数量。
你可以通过使用更多的random5输入一次生成多个random7输出来做得更好。对于使用31位整数计算的结果，最优结果是使用12次调用random5生成9个random7输出，平均每个输出调用1.34次。它是高效的，因为244140625个结果中只有2018983个需要废弃，或者不到1%。
Python演示:
def random5():
return random.randint(1, 5)
def random7gen(n):
count = 0
while n > 0:
samples = 6 * 7**9
while samples >= 6 * 7**9:
samples = 0
for i in range(12):
samples = samples * 5 + random5() - 1
count += 1
samples //= 6
for outputs in range(9):
yield samples % 7 + 1, count
samples //= 7
count = 0
n -= 1
if n == 0: break
>>> from collections import Counter
>>> Counter(x for x,i in random7gen(10000000))
Counter({2: 1430293, 4: 1429298, 1: 1428832, 7: 1428571, 3: 1428204, 5: 1428134, 6: 1426668})
>>> sum(i for x,i in random7gen(10000000)) / 10000000.0
1.344606
Python:有一个简单的两行答案，它使用空间代数和模量的组合。这不是直观的。我对它的解释令人困惑，但却是正确的。
知道5*7=35 7/5 = 1余数为2。如何保证余数之和始终为0?5*[7/5 = 1余数2]——> 35/5 = 7余数0
想象一下，我们有一条丝带，缠在一根周长为7的杆子上。丝带需要35个单位才能均匀地缠绕。随机选择7个色带片段len=[1…5]。忽略换行的有效长度与将rand5()转换为rand7()的方法相同。
import numpy as np
import pandas as pd
# display is a notebook function FYI
def rand5(): ## random uniform int [1...5]
return np.random.randint(1,6)
n_trials = 1000
samples = [rand5() for _ in range(n_trials)]
display(pd.Series(samples).value_counts(normalize=True))
# 4 0.2042
# 5 0.2041
# 2 0.2010
# 1 0.1981
# 3 0.1926
# dtype: float64
def rand7(): # magic algebra
x = sum(rand5() for _ in range(7))
return x%7 + 1
samples = [rand7() for _ in range(n_trials)]
display(pd.Series(samples).value_counts(normalize=False))
# 6 1475
# 2 1475
# 3 1456
# 1 1423
# 7 1419
# 4 1393
# 5 1359
# dtype: int64
df = pd.DataFrame([
pd.Series([rand7() for _ in range(n_trials)]).value_counts(normalize=True)
for _ in range(1000)
])
df.describe()
# 1 2 3 4 5 6 7
# count 1000.000000 1000.000000 1000.000000 1000.000000 1000.000000 1000.000000 1000.000000
# mean 0.142885 0.142928 0.142523 0.142266 0.142704 0.143048 0.143646
# std 0.010807 0.011526 0.010966 0.011223 0.011052 0.010983 0.011153
# min 0.112000 0.108000 0.101000 0.110000 0.100000 0.109000 0.110000
# 25% 0.135000 0.135000 0.135000 0.135000 0.135000 0.135000 0.136000
# 50% 0.143000 0.142000 0.143000 0.142000 0.143000 0.142000 0.143000
# 75% 0.151000 0.151000 0.150000 0.150000 0.150000 0.150000 0.151000
# max 0.174000 0.181000 0.175000 0.178000 0.189000 0.176000 0.179000
我想到了一个解决这个问题的有趣方法，想和大家分享一下。
function rand7() {
var returnVal = 4;
for (var n=0; n<3; n++) {
var rand = rand5();
if (rand==1||rand==2){
returnVal+=1;
}
else if (rand==3||rand==4) {
returnVal-=1;
}
}
return returnVal;
}
我构建了一个测试函数，循环rand7() 10,000次，将所有返回值相加，然后除以10,000。如果rand7()工作正常，我们计算的平均值应该是4 -例如，(1+2+3+4+5+6+7 / 7)= 4。在做了多次测试后，平均值确实是4:)
什么是简单的解决方案?(rand5() + rand5()) % 7 + 1 减少内存使用或在较慢的CPU上运行的有效解决方案是什么?是的，这是有效的，因为它只调用rand5()两次，空间复杂度为O(1)
考虑rand5()给出从1到5(包括)的随机数。 (1 + 1) % 7 + 1 = 3 (1 + 2) % 7 + 1 = 4 (1 + 3) % 7 + 1 = 5 (1 + 4) % 7 + 1 = 6 (1 + 5) % 7 + 1 = 7
(2 + 1) % 7 + 1 = 4 (2 + 2) % 7 + 1 = 5 (2 + 3) % 7 + 1 = 6 (2 + 4) % 7 + 1 = 7 (2 + 5) % 7 + 1 = 1 .
(5 + 1) % 7 + 1 = 7 (5 + 2) % 7 + 1 = 1 (5 + 3) % 7 + 1 = 2 (5 + 4) % 7 + 1 = 3 (5 + 5) % 7 + 1 = 4 .
等等
