[算法] 随机选择取样问题

2013 九月 06 周五 Zoey Young 算法&数据结构笔试面试

问题:

输入: 包含两个整数m和n, 其中m<n.

输出: 0~n-1范围内的m个随机整数的有序列表, 不允许重复.

从概率的角度说, 希望得到没有重复的有序选择, 其中每个选择出现的概率相等.

一种解决方案:

from random import randint

times = 10000
N = 200
M = 20
a = [0]*N

# 算法的运行时间跟n成正比
def genknuth(m, n):
    for i in range(n):
        if randint(0, n-i-1) < m:
            a[i] += 1
            m -= 1
            if m == 0:
                break

for i in range(times):
    genknuth(M, N)
avg = [str(100*i/times) + '%' for i in a]
print(avg)

输出:

['10%', '10%', '10%', '10%', '10%', '10%', '10%', '10%', '10%', '10%', '9%', '10%', '9%', '9%', '10%', '9%', '10%', '10%', '9%', '9%', '10%', '10%', '9%', '9%', '10%', '9%', '10%', '9%', '10%', '10%', '9%', '10%', '10%', '10%', '10%', '10%', '10%', '9%', '10%', '9%', '10%', '9%', '9%', '9%', '10%', '10%', '10%', '10%', '10%', '10%', '9%', '9%', '10%', '10%', '10%', '10%', '9%', '9%', '10%', '9%', '9%', '9%', '10%', '9%', '9%', '10%', '10%', '10%', '10%', '9%', '9%', '10%', '9%', '10%', '9%', '10%', '9%', '9%', '9%', '9%', '9%', '10%', '9%', '9%', '9%', '10%', '9%', '9%', '10%', '10%', '9%', '9%', '9%', '10%', '9%', '10%', '10%', '10%', '9%', '9%', '10%', '10%', '9%', '10%', '9%', '9%', '10%', '9%', '9%', '10%', '10%', '10%', '10%', '9%', '10%', '9%', '10%', '9%', '10%', '9%', '9%', '10%', '9%', '10%', '9%', '9%', '10%', '9%', '10%', '10%', '10%', '9%', '9%', '9%', '10%', '9%', '9%', '9%', '9%', '10%', '10%', '9%', '9%', '10%', '10%', '10%', '10%', '10%', '10%', '10%', '10%', '10%', '9%', '9%', '10%', '10%', '9%', '9%', '9%', '10%', '9%', '9%', '9%', '10%', '10%', '9%', '10%', '10%', '9%', '10%', '10%', '10%', '9%', '10%', '10%', '9%', '9%', '9%', '10%', '9%', '10%', '10%', '10%', '10%', '9%', '9%', '9%', '9%', '10%', '9%', '10%', '10%', '9%', '10%', '9%', '10%', '10%', '10%', '9%', '9%']

即当M=20, N=200时, 每个数被选中的概率均约为10%, 即M/N.

使用集合:

def genset(m, n):
    s = set()
    while len(s) < m:
        s.add(randint(0, n-1))
    for i in s:
        a[i] += 1
    return s

打乱数组, 互换位置法:

def genshuf(m, n):
    a = [i for i in range(n)]
    for i in range(m):
        j = randint(i, n-1)
        a[i], a[j] = a[j], a[i]
    sorted(a[:m])
    return a[:m]

这个算法需要O(n)的时间和空间.

这个问题还有一个注意点为: m与n的取值, 当m远大于n-m时, 应该选择n-m个数作为排除项, 而非选择m个数.

在N = 2000000, M = 1000000时, 测试三种算法:

import cProfile
cProfile.run('genknuth(M, N)')  # 15.075 seconds 15.209 seconds 15.686 seconds
cProfile.run('genset(M, N)')  # 13.766 seconds 14.178 seconds 13.466 seconds
cProfile.run('genshuf(M, N)')  # 11.416 seconds 12.057 seconds 10.459 seconds

习题:

《编程珠玑》第十二章：取样问题

问题: 已知有个rand7()的函数, 回1到7随机自然数, 让利用这个rand7()构造rand10(), 随机1~10.

思路:

一次随机只能构造7种情况, 能想到至少要构造两次随机.

通过式子(r1-1)*7+r2, 可构造出均匀分布在1-49的随机数:

>>> l = [(r1-1)*7+r2 for r1 in range(1,8) for r2 in range(1,8)]
>>> l
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49]

49种情况再转换成10种情况

可以将41～49这样的随机数剔除掉, 得到的数1-40仍然是均匀分布在1-40的, 这是因为每个数都可以看成一个独立事件.

from random import randint

def rand7():
    return randint(1, 7)

def rand10():
    while True:
        r1 = rand7()
        r2 = rand7()
        r = (r1-1)*7+r2
        if r <= 40: break
    return r%10+1 # (r-1)/4 + 1 两个都可以. 前面略快点.

seq = [rand10() for i in range(10000000)]
from collections import Counter
cnt = Counter(seq)
print(cnt)

测试了几次效果:

Counter({9: 1001920, 2: 1000687, 1: 1000384, 10: 999874, 5: 999781, 8: 999772, 6: 999718, 7: 999574, 3: 999270, 4: 999020})
Counter({1: 1001749, 3: 1001048, 4: 1000671, 2: 999915, 7: 999811, 10: 999783, 6: 999431, 8: 999296, 5: 999231, 9: 999065})
Counter({5: 1000897, 7: 1000782, 3: 1000596, 2: 1000015, 1: 999929, 10: 999900, 8: 999892, 9: 999541, 4: 999483, 6: 998965})
Counter({4: 1000671, 8: 1000606, 10: 1000393, 2: 1000262, 3: 1000011, 7: 999800, 1: 999791, 9: 999708, 5: 999502, 6: 999256})
Counter({1: 1001850, 7: 1000861, 3: 1000659, 10: 1000632, 6: 1000218, 5: 1000086, 2: 999399, 8: 999035, 9: 998689, 4: 998571})

[算法] 随机选择 取样问题

[算法] 随机选择取样问题