2

加重セットからランダムなアイテムをいくつか選ぶ必要があります。重量が大きいアイテムは、選択される可能性が高くなります。抽選でモデル化することにしました。私のソリューションは良いC++になると思いますが、良いpythonにはならないでしょう。

これを行うためのPythonの方法は何ですか？

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のコメントに基づいた最終的な解決策があると思います

ノート

  • 私はPython2.7で作業しているので、独自のaccumulate（）を作成しました。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 に答える