我需要从加权集中选择几个随机项目。重量较高的物品更有可能被选中。我决定在抽签后对此进行建模。我觉得我的解决方案可以制作出好的 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
感谢大家的帮助!