algorithm - 运行彩票的 pythonic 方法是什么？

Question

我需要从一个加权集合中随机挑选几个项目。权重较高的项目更有可能被选中。我决定在抽签后对此进行建模。我觉得我的解决方案适用于 C++，但我认为它不适用于 Python。

执行此操作的 pythonic 方式是什么？

def _lottery_winners_by_participants_and_ticket_counts(participants_and_ticket_counts, number_of_winners):
    """
    Returns a list of winning participants in a lottery. In this lottery,
    participant can have multiple tickets, and participants can only win
    once.
    participants_and_ticket_counts is a list of (participant, ticket_count)
    number_of_winners is the maximum number of lottery winners
    """

    if len(participants_and_ticket_counts) <= number_of_winners:
        return [p for (p, _) in participants_and_ticket_counts]

    winners = []

    for _ in range(number_of_winners):
        total_tickets = sum(tc for (_, tc) in participants_and_ticket_counts)
        winner = random.randrange(0, total_tickets)

        ticket_count_offset = 0
        for participant_ticket_count in participants_and_ticket_counts:
            (participant, ticket_count) = participant_ticket_count

            if winner < ticket_count + ticket_count_offset:
                winners.append(participant)
                participants_and_ticket_counts.remove(participant_ticket_count)
                break

            ticket_count_offset += ticket_count

    return winners

---

编辑:抱歉我之前忘记了，但是权重是一个整数，可能以千为单位。

---

编辑:我想我已经根据@Flo 的评论找到了最终的解决方案

注释

• 我在 Python 2.7 中工作，所以我创建了自己的 accumulate()。它的工作方式与 Python 3 中的 accumulate() 不同(我认为更好)。我的版本可以基于添加函数从可迭代的元组中累积。

• 我还特别知道 participants_and_ticket_counts 是一个可变列表，在调用 _lottery_winners_by_participants_and_ticket_counts() 后将不会被使用。这就是为什么我可以 pop() 它。

这是我的解决方案:

def _lottery_winners_by_participants_and_ticket_counts(participants_and_ticket_counts, number_of_winners):
    """
    Returns a list of winning participants in a lottery. In this lottery,
    participant can have multiple tickets, and participants can only win once.
    participants_and_ticket_counts is a list of (participant, ticket_count)
    number_of_winners is the maximum number of lottery winners
    """
    def _accumulate(iterable, func):
        total = 0
        for element in iterable:
            total = func(total, element)
            yield total

    if len(participants_and_ticket_counts) <= number_of_winners:
        return list(winner for (winner, _) in participants_and_ticket_counts)

    winners = list()
    for _ in range(number_of_winners):
        accumulation = list(_accumulate(participants_and_ticket_counts, lambda total, ptc: total + ptc[1]))
        winning_number = random.randrange(0, accumulation[-1])
        index_of_winner = bisect.bisect(accumulation, winning_number)
        (winner, _) = participants_and_ticket_counts.pop(index_of_winner)
        winners.append(winner)
    return winners

感谢大家的帮助!

Answer 1

numpy.random.choice对此有一个很好的解决方案。以下是您可以如何使用它:

>>> import numpy as np
>>> from numpy.random import choice
>>> names = ['Harry', 'Sally', 'Joe', 'Bob', 'Angela', 'Jack', 'Jill', 'Jeff']
>>> weights = [1,4,6,3,5,7,10,14]
>>> p = np.array(weights, dtype=float) / sum(weights)
>>> p
array([ 0.02,  0.08,  0.12,  0.06,  0.1 ,  0.14,  0.2 ,  0.28])

>>> choice(names, size=5, p=p)
array(['Jill', 'Jack', 'Jeff', 'Jeff', 'Angela'], 
      dtype='|S6')
>>> choice(names, size=5, p=p)
array(['Jill', 'Jack', 'Joe', 'Jill', 'Sally'], 
      dtype='|S6')
>>> choice(names, size=5, p=p)
array(['Jack', 'Angela', 'Joe', 'Sally', 'Jill'], 
      dtype='|S6')

不过这个函数是在numpy 1.7中加入的。如果你有旧版本，你可以只复制函数:http://pastebin.com/F5gti0qJ