2

我需要从加权集中选择几个随机项目。重量较高的物品更有可能被选中。我决定在抽签后对此进行建模。我觉得我的解决方案可以制作出好的 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 中工作，所以我创建了自己的累积（）。它的工作方式与 Python 3 中的 accumulate() 不同（我认为更好）。我的版本可以从基于 add 函数的元组迭代中累积。

  • 我也有特殊的知识，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

感谢大家的帮助！

4

3 回答 3

4

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

于 2012-06-05T17:51:21.117 回答
2

这个怎么样？

def lottery(participant_and_ticket_count, number_of_winners):
    # Creates list where each person is represented multiple times based on the number of tickets they have.
    population = [person for (person, count) in participant_and_ticket_count for i in range(count)]

    winners = []

    for i in range(number_of_winners):
        try:
            winner = random.choice(population)
        except IndexError:
            # There aren't enough people in the lottery, so return the results early.
            return winners
        winners.append(winner)

        # Remove the winner from the lottery to prevent duplication.
        population = [person for person in population if person != winner]

    return winners

样品运行：

>>> foo = [('Alex', 5),
           ('Betty', 1),
           ('Carl', 2),
           ('Daniella', 10)]
>>> lottery(foo, 2)
['Daniella', 'Alex']
>>> lottery(foo, 2)
['Alex', 'Daniella']
>>> lottery(foo, 2)
['Daniella', 'Betty']
>>> lottery(foo, 9)
['Daniella', 'Alex', 'Carl', 'Betty']
于 2012-06-05T16:15:00.433 回答
0 
>>> from random import shuffle, choice
>>> 
>>> def lottery_winners(players, win_number):
    choosefrom = sum(([name] * count for name, count in players), [])
    shuffle(choosefrom)
    winners = []
    while len(winners) < win_number:
        choice = choosefrom.pop()
        if choice not in winners:
            winners.append(choice)
    return winners

>>> players = [('Alex', 5),
           ('Betty', 1),
           ('Carl', 2),
           ('Daniella', 10)]
>>> lottery_winners(players, 3)
['Alex', 'Carl', 'Daniella']
>>> lottery_winners(players, 3)
['Daniella', 'Alex', 'Carl']
>>> lottery_winners(players, 3)
['Carl', 'Betty', 'Daniella']
>>> lottery_winners(players, 2)
['Alex', 'Daniella']
>>> lottery_winners(players, 2)
['Carl', 'Daniella']
>>>
于 2012-06-05T17:30:51.003 回答