如何在Python中从已知百分比的列表中选择项

Question

我想从一个列表中随机选择一个单词，每个单词都有一个已知的概率，比如：

水果和概率

橙子 0.10
苹果 0.05
芒果 0.15
等等

那么，最好的实现方法是什么呢？我实际使用的列表最多有100个项目，而且这些概率的总和并不一定是100%，因为有些项目的出现概率非常低，所以总和会少于100%。我希望能从一个CSV文件中读取这些数据，因为我把这些信息存储在那儿。这项任务并不紧急。

谢谢你们提供的任何建议，帮助我更好地进行下去。

Answer 1

lst = [ ('Orange', 0.10), ('Apple', 0.05), ('Mango', 0.15), ('etc', 0.69) ]

x = 0.0
lst2 = []
for fruit, chance in lst:
    tup = (x, fruit)
    lst2.append(tup)
    x += chance

tup = (x, None)
lst2.append(tup)

import random

def pick_one(lst2):
    if lst2[0][1] is None:
        raise ValueError, "no valid values to choose"
    while True:
        r = random.random()
        for x, fruit in reversed(lst2):
            if x <= r:
                if fruit is None:
                    break  # try again with a different random value
                else:
                    return fruit

pick_one(lst2)

这个过程是创建一个新的列表，里面的数字是从小到大排列的，表示选择水果的范围；然后，pick_one() 会从列表的后面开始查找，寻找一个小于等于当前随机值的数字。我们在列表的最后加了一个“哨兵”值；如果列表里的值没有达到1.0，就有可能出现一个随机值不应该匹配任何东西，但它会匹配到这个哨兵值，然后被拒绝。random.random() 会返回一个在 [0.0, 1.0) 范围内的随机值，所以最终它一定会匹配到列表中的某个值。

这里的好处是，你可以有一个匹配概率为0.000001的值，它实际上会以这个频率匹配；而其他的解决方案，比如把每个项目重复放入列表中，然后用 random.choice() 来选择一个，就需要一个包含一百万个项目的列表来处理这种情况。

Answer 2

你想要做的是从一个多项分布中抽取数据。假设你有两个物品列表和对应的概率，并且这些概率加起来等于1（如果不等于1，你可以加一些默认值来补齐差额）：

def choose(items,chances):
    import random
    p = chances[0]
    x = random.random()
    i = 0
    while x > p :
        i = i + 1
        p = p + chances[i]
    return items[i]

Answer 3

你可以通过给每个物品分配一个与其概率成比例的数字范围，来根据加权概率选择物品。然后随机选择一个介于零和这些范围总和之间的数字，找到与这个数字匹配的物品。下面的类就是这样实现的：

from random import random

class WeightedChoice(object):
    def __init__(self, weights):
        """Pick items with weighted probabilities.

            weights
                a sequence of tuples of item and it's weight.
        """
        self._total_weight = 0.
        self._item_levels = []
        for item, weight in weights:
            self._total_weight += weight
            self._item_levels.append((self._total_weight, item))

    def pick(self):
        pick = self._total_weight * random()
        for level, item in self._item_levels:
            if level >= pick:
                return item

接下来，你可以使用csv模块加载CSV文件，并将其传递给WeightedChoice类：

import csv

weighed_items = [(item,float(weight)) for item,weight in csv.reader(open('file.csv'))]
picker = WeightedChoice(weighed_items)
print(picker.pick())