Python：选择带相关概率的数字

Question

可能的重复问题：
随机加权选择
生成具有特定数值分布的随机数

我有一个包含一系列数字及其对应概率的列表。

prob_list = [[1, 0.5], [2, 0.25], [3, 0.05], [4, 0.01], [5, 0.09], [6, 0.1]]

举个例子，在 prob_list[0] 中，数字1的概率是0.5。这意味着你可以期待数字1出现50%的时间。

我该如何在选择数字时加入权重呢？

注意：列表中的数字数量可以从6个到100个不等。

---

编辑

在这个列表中，我有6个数字和它们的对应概率。我想根据概率选择两个数字。

每个数字只能被选一次。如果选择了“2”，那么它就不能再被选中了。

Answer 1

这里有一个看起来能满足你所有要求的方案（主观上感觉速度也挺快的）。需要注意的是，你要求第二个数字不能和第一个数字相同，这样会影响选择它的概率。下面的代码实际上忽略了这个问题，只是简单地强制执行了这个限制（换句话说，第二个数字的概率不会是prob_list中每个数字的给定概率）。

import random

prob_list = [[1, 0.5], [2, 0.25], [3, 0.05], [4, 0.01], [5, 0.09], [6, 0.1]]

# create a list with the running total of the probabilities
acc = 0.0
acc_list = [acc]
for t in prob_list:
    acc += t[1]
    acc_list.append(acc)

TOLERANCE = .000001
def approx_eq(v1, v2):
    return abs(v1-v2) <= TOLERANCE

def within(low, value, high):
    """ Determine if low >= value <= high (approximately) """
    return (value > low or approx_eq(low, value)) and \
           (value < high or approx_eq(high, value))

def get_selection():
    """ Find which weighted interval a random selection falls in """
    interval = -1
    rand = random.random()
    for i in range(len(acc_list)-1):
        if within(acc_list[i], rand, acc_list[i+1]):
            interval = i
            break
    if interval == -1:
        raise AssertionError('no interval for {:.6}'.format(rand))
    return interval

def get_two_different_nums():
    sel1 = get_selection()
    sel2 = sel1
    while sel2 == sel1:
        sel2 = get_selection()
    return prob_list[sel1][0], prob_list[sel2][0]

Answer 2

我假设这些概率加起来是1。如果不是，你需要调整它们，让它们加起来等于1。

首先，使用 random.random() 生成一个在0到1之间的随机数。然后遍历概率列表，逐步累加这些概率。每当这个累加的和超过你生成的随机数时，就返回对应的数字。这样，如果生成的随机数在(0.5, 0.75]这个范围内，你就会返回2，这样就能确保它有0.25的概率被选中。

import random
import sys
def pick_random(prob_list):
  r, s = random.random(), 0
  for num in prob_list:
    s += num[1]
    if s >= r:
      return num[0]
  print >> sys.stderr, "Error: shouldn't get here"

这里有个测试，证明这个方法有效：

import collections
count = collections.defaultdict(int)
for i in xrange(10000):
  count[pick_random(prob_list)] += 1
for n in count:
  print n, count[n] / 10000.0

输出结果是：

1 0.498
2 0.25
3 0.0515
4 0.0099
5 0.0899
6 0.1007

编辑：刚看到问题的更新。如果你想选择两个不同的数字，可以重复上述过程，直到你选到的第二个数字和第一个不同。不过，如果其中一个数字的概率非常高（比如0.99999999），这样做会非常慢。在这种情况下，你可以把第一个数字从列表中移除，然后重新调整概率，让它们加起来等于1，再选择第二个数字。

Answer 3

这可能正是你想要的。这个内容是对一个解决方案的扩展，原始问题在这里：生成具有特定数值分布的随机数。它的功能是从分布中移除一个选定的项目，更新概率，然后返回选定项目，更新后的分布。虽然没有经过验证，但应该能让你对这个想法有个大致的了解。

def random_distr(l):
    assert l # don't accept empty lists
    r = random.uniform(0, 1)
    s = 0
    for i in xrange(len(l)):
        item, prob = l[i]
        s += prob
        if s >= r:
            l.pop(i) # remove the item from the distribution
            break
    else: # Might occur because of floating point inaccuracies
        l.pop()
    # update probabilities based on new domain
    d = 1 - prob 
    for i in xrange(len(l)):
        l[i][1] /= d
    return item, l

dist = [[1, 0.5], [2, 0.25], [3, 0.05], [4, 0.01], [5, 0.09], [6, 0.1]]
while dist:
    val, dist = random_distr(dist)
    print val