给定一个函数,它产生的是1到5之间的随机整数,写一个函数,它产生的是1到7之间的随机整数。
当前回答
就是这样,均匀分布,零rand5调用。
def rand7:
seed += 1
if seed >= 7:
seed = 0
yield seed
需要事先播种。
其他回答
面对这么复杂的答案,我觉得自己很蠢。
为什么不能:
int random1_to_7()
{
return (random1_to_5() * 7) / 5;
}
?
这里我们使用约定的rand(n) -> [0, n - 1]
从我读到的许多答案中,它们要么提供了一致性,要么提供了暂停保证,但不能同时提供(adam rosenfeld的第二个答案可能)。
然而,这样做是可能的。我们基本上有这样的分布:
这给[0-6]上的分布留下了一个漏洞:5和6没有 发生的概率。想象一下,现在我们试图通过移动 概率分布和求和。
事实上,我们可以把初始分布平移1,然后 重复将得到的分布与移位的初始分布相加 2,然后3,以此类推,直到7,不包括在内(我们涵盖了整个范围)。 如下图所示。颜色的顺序,对应 步骤,是蓝色->绿色->青色->白色->品红->黄色->红色。
因为每个插槽由7个移位分布中的5个覆盖(移位从 0到6),因为我们假设随机数是独立于1的 Ran5()呼叫另一个,我们获得
p(x) = 5 / 35 = 1 / 7 for all x in [0, 6]
这意味着,给定来自ran5()的7个独立随机数,我们可以 计算一个在[0-6]范围内具有均匀概率的随机数。 实际上是ran5()概率 分布甚至不需要均匀,只要样本是均匀的 独立(所以每次试验的分布保持不变) 同样,这也适用于5和7之外的其他数字。
这为我们提供了以下python函数:
def rand_range_transform(rands):
"""
returns a uniform random number in [0, len(rands) - 1]
if all r in rands are independent random numbers from the same uniform distribution
"""
return sum((x + i) for i, x in enumerate(rands)) % len(rands) # a single modulo outside the sum is enough in modulo arithmetic
可以这样使用:
rand5 = lambda : random.randrange(5)
def rand7():
return rand_range_transform([rand5() for _ in range(7)])
如果我们调用rand7() 70000次,我们可以得到:
max: 6 min: 0 mean: 2.99711428571 std: 2.00194697049
0: 10019
1: 10016
2: 10071
3: 10044
4: 9775
5: 10042
6: 10033
这很好,尽管远非完美。事实上,我们的一个假设是 在这个实现中很可能是false:我们使用一个PRNG,因此,结果 的值依赖于上一个结果。
也就是说,使用一个真正随机的数字来源,输出也应该是 真正随机的。这个算法在任何情况下都终止。
但这是有代价的:我们需要为一个rand7()调用7次rand5() 调用。
通过使用滚动总数,您可以同时
保持平均分配;而且 不需要牺牲随机序列中的任何元素。
这两个问题都是简单的rand(5)+rand(5)…类型的解决方案。下面的Python代码展示了如何实现它(其中大部分是证明发行版)。
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)
这个输出显示了结果:
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%)
一个简单的rand(5)+rand(5),忽略那些返回大于6的情况,其典型变化为18%,是上面所示方法的100倍:
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%)
并且,根据Nixuz的建议,我已经清理了脚本,所以您可以提取并使用rand7…材料:
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)
假设rand(n)在这里表示“从0到n-1均匀分布的随机整数”,下面是使用Python的randint的代码示例,它具有这种效果。它只使用randint(5)和常量来产生randint(7)的效果。其实有点傻
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
如果有人能就这一点给我反馈,那就太酷了,我使用了没有assert模式的JUNIT,因为在Eclipse中运行它很容易,也很快速,我也可以只定义一个主方法。顺便说一下,我假设rand5给出的值为0-4,加上1将得到1-5,rand7也是如此……所以讨论应该是解决方案,它的分布,而不是它是从0-4还是1-5…
package random;
import java.util.Random;
import org.junit.Test;
public class RandomTest {
@Test
public void testName() throws Exception {
long times = 100000000;
int indexes[] = new int[7];
for(int i = 0; i < times; i++) {
int rand7 = rand7();
indexes[rand7]++;
}
for(int i = 0; i < 7; i++)
System.out.println("Value " + i + ": " + indexes[i]);
}
public int rand7() {
return (rand5() + rand5() + rand5() + rand5() + rand5() + rand5() + rand5()) % 7;
}
public int rand5() {
return new Random().nextInt(5);
}
}
当我运行它时,我得到这样的结果:
Value 0: 14308087
Value 1: 14298303
Value 2: 14279731
Value 3: 14262533
Value 4: 14269749
Value 5: 14277560
Value 6: 14304037
这似乎是一个非常公平的分配,不是吗?
如果我将rand5()添加更少或更多次(其中次数不能被7整除),分布会清楚地显示偏移量。例如,将rand5()相加3次:
Value 0: 15199685
Value 1: 14402429
Value 2: 12795649
Value 3: 12796957
Value 4: 14402252
Value 5: 15202778
Value 6: 15200250
因此,这将导致以下结果:
public int rand(int range) {
int randomValue = 0;
for(int i = 0; i < range; i++) {
randomValue += rand5();
}
return randomValue % range;
}
然后,我可以更进一步:
public static final int ORIGN_RANGE = 5;
public static final int DEST_RANGE = 7;
@Test
public void testName() throws Exception {
long times = 100000000;
int indexes[] = new int[DEST_RANGE];
for(int i = 0; i < times; i++) {
int rand7 = convertRand(DEST_RANGE, ORIGN_RANGE);
indexes[rand7]++;
}
for(int i = 0; i < DEST_RANGE; i++)
System.out.println("Value " + i + ": " + indexes[i]);
}
public int convertRand(int destRange, int originRange) {
int randomValue = 0;
for(int i = 0; i < destRange; i++) {
randomValue += rand(originRange);
}
return randomValue % destRange;
}
public int rand(int range) {
return new Random().nextInt(range);
}
我尝试用不同的值替换destRange和originRange(甚至ORIGIN为7,DEST为13),我得到了这样的分布:
Value 0: 7713763
Value 1: 7706552
Value 2: 7694697
Value 3: 7695319
Value 4: 7688617
Value 5: 7681691
Value 6: 7674798
Value 7: 7680348
Value 8: 7685286
Value 9: 7683943
Value 10: 7690283
Value 11: 7699142
Value 12: 7705561
从这里我可以得出的结论是,你可以通过求和起始随机“目的地”时间来将任意随机改变为任意随机。这将得到一种高斯分布(中间值更有可能,边缘值更不常见)。然而,目标模量似乎均匀地分布在这个高斯分布中…如果能得到数学家的反馈就太好了……
最酷的是,成本是100%可预测的和恒定的,而其他解决方案导致无限循环的概率很小……