Все возможные комбинации карт/покерных комбинаций для набора игроков

Я ищу элегантную (быструю) функцию Python, которая создает каждую комбинацию из следующих двух массивов.

cards = ["8H", "8S", "8C", "8D", "9H", "9S", "9C", "9D", "10H", "10S", "10C", "10D", "AH", "AS", "AC", "AD"]
players = ["_1", "_1", "_1", "_2", "_2", "_2", "_3", "_3", "_3", "_4", "_4", "_4", "_To", "_To", "_To", "_Tc"]

Комбинация будет выглядеть так:

[('8H', '_1'), ('8S', '_1'), ('8C', '_1'), ('8D', '_2'), ('9H', '_2'), ('9S', '_2'), ('9C', '_3'), ('9D', '_3'), ('10H', '_3'), ('10S', '_4'), ('10C', '_4'), ('10D', '_4'), ('AH', '_To'), ('AS', '_To'), ('AC', '_To'), ('AD', '_Tc')]

Но! без равных, что я имею в виду. Пример:

Если бы карты были:

["a", "b", "c", "d"]

Если бы игроки были:

["1", "1", "2", "2"]

Результат:

[1a, 1b, 2c, 2d]
[1a, 1c, 2b, 2d]
[1a, 1d, 2b, 2c]
[1b, 1c, 2a, 2d]
[1b, 1d, 2a, 2c]
[1c, 1d, 2a, 2b]

Не например:

[1a, 1b, 2d, 2c]

Игрок 2, имеющий (c и d), равен (d и c)

Я пробовал функцию itertools, например combinations и permutations, но безуспешно. Отказ от равенства после получения всех комбинаций на самом деле не вариант из-за взрыва пространства состояний.

Я надеюсь, что у кого-то есть решение, потому что поиск Google для этой конкретной проблемы не удался.


python combinations permutation playing-cards poker
person Pieter Bosma    schedule 12.03.2014    source источник
comment
Я сделал заголовок и теги более подходящими и актуальными для этого вопроса; предыдущее название не было чем-то, что люди будут искать для этой конкретной (связанной с покером) проблемы. И теги пробела и состояния были подобраны без учета их значения.   -  person Erik Kaplun    schedule 12.03.2014

Ответы (3)


arrow_upward
3
arrow_downward

Я бы предложил использовать рекурсивный алгоритм.

Я использую генераторы для запуска кода в постоянном пространстве, а также для получения результатов как можно скорее, а не огромного результата в конце; см. http://www.dabeaz.com/generators/, если вы раньше не слышали о генераторах .

В качестве примечания, я бы предложил использовать нормализованную структуру данных для хранения вашего списка игроков и размеров рук для начала, так что строка с groupby вообще не нужна... И в любом случае, это обычно хорошая идея, чтобы ваши данные были нормализованы по умолчанию/большую часть времени и использовали только денормализованные/плоские формы, например, для определенных алгоритмов, которые могут потребоваться или работать быстрее с плоскими структурами.

Вот код; не стесняйтесь предлагать очистки/упрощения:

from itertools import combinations, groupby, islice

cards = ["a", "b", "c", "d"]
players = ["1", "1", "2", "2"]

def hand_combinations(players, cards):
    # convert ["1", "1", "2", "2"] into [("1", 2), ("2", 2)]
    players = list((x, len(list(y))) for x, y in groupby(players))

    # sets are faster to operate on in our case
    cards = set(cards)

    def generate(players, cards):
        if not players:
            yield []
        else:
            # pick the first player
            player_name, player_hand_size = players[0]
            # and then walk over all the possible hands for this player
            for player_hand in combinations(cards, player_hand_size):
                # for each hand, use the cards that are left to build all the
                # possible hands for the rest of the players in this iteration
                for tail in generate(players[1:], cards - set(player_hand)):
                    yield [(player_name, player_hand)] + tail

    return generate(players, cards)

# take only the 100 first combinations; otherwise it'll take
# forever with the larger example
combos = islice(hand_combinations(players, cards), 0, 100)

# convert back to the flat structure
flattened = [
    ' '.join(
        player_name + ':' + card
        for player_name, player_cards in combo
        for card in player_cards
    )
    for combo in combos
]

from pprint import pprint
pprint(flattened)

Результаты:

['1:a 1:c 2:b 2:d',
 '1:a 1:b 2:c 2:d',
 '1:a 1:d 2:c 2:b',
 '1:c 1:b 2:a 2:d',
 '1:c 1:d 2:a 2:b',
 '1:b 1:d 2:a 2:c']

или с более крупным примером:

['_1:AS _1:9H _1:8H _2:AC _2:10H _2:AD _3:10S _3:10C _3:9C _4:8C _4:9D _4:8D _To:AH _To:9S _To:10D _Tc:8S',
 '_1:AS _1:9H _1:8H _2:AC _2:10H _2:AD _3:10S _3:10C _3:9C _4:8C _4:9D _4:8D _To:AH _To:9S _To:8S _Tc:10D',
 '_1:AS _1:9H _1:8H _2:AC _2:10H _2:AD _3:10S _3:10C _3:9C _4:8C _4:9D _4:8D _To:AH _To:10D _To:8S _Tc:9S',
 '_1:AS _1:9H _1:8H _2:AC _2:10H _2:AD _3:10S _3:10C _3:9C _4:8C _4:9D _4:8D _To:9S _To:10D _To:8S _Tc:AH',
 '_1:AS _1:9H _1:8H _2:AC _2:10H _2:AD _3:10S _3:10C _3:9C _4:8C _4:9D _4:10D _To:AH _To:9S _To:8D _Tc:8S',
 '_1:AS _1:9H _1:8H _2:AC _2:10H _2:AD _3:10S _3:10C _3:9C _4:8C _4:9D _4:10D _To:AH _To:9S _To:8S _Tc:8D',
 '_1:AS _1:9H _1:8H _2:AC _2:10H _2:AD _3:10S _3:10C _3:9C _4:8C _4:9D _4:10D _To:AH _To:8D _To:8S _Tc:9S',
 '_1:AS _1:9H _1:8H _2:AC _2:10H _2:AD _3:10S _3:10C _3:9C _4:8C _4:9D _4:10D _To:9S _To:8D _To:8S _Tc:AH',
 '_1:AS _1:9H _1:8H _2:AC _2:10H _2:AD _3:10S _3:10C _3:9C _4:8C _4:9D _4:AH _To:8S _To:9S _To:10D _Tc:8D',
 '_1:AS _1:9H _1:8H _2:AC _2:10H _2:AD _3:10S _3:10C _3:9C _4:8C _4:9D _4:AH _To:8S _To:9S _To:8D _Tc:10D',
 '_1:AS _1:9H _1:8H _2:AC _2:10H _2:AD _3:10S _3:10C _3:9C _4:8C _4:9D _4:AH _To:8S _To:10D _To:8D _Tc:9S',
 '_1:AS _1:9H _1:8H _2:AC _2:10H _2:AD _3:10S _3:10C _3:9C _4:8C _4:9D _4:AH _To:9S _To:10D _To:8D _Tc:8S',
...
person Erik Kaplun    schedule 12.03.2014
comment
@ user3411641: может быть, я что-то упускаю, но я действительно не вижу, где можно что-то оптимизировать... код должен работать в постоянном пространстве, если вы не выполняете жадную оценку, и выдает результаты, как только вы его запускаете. - person Erik Kaplun; 12.03.2014
comment
Ну, скорее, чтобы не было переполнения памяти. - person Pieter Bosma; 12.03.2014
comment
@user3411641 user3411641: приведенный выше код никогда не переполнит/заполнит память, если вы используете возвращаемое значение правильно (т.е. лениво). см. предоставленную ссылку о генераторах для получения дополнительной информации о том, как в полной мере использовать генераторы/лень. - person Erik Kaplun; 12.03.2014

arrow_upward
1
arrow_downward

Итак, что вы на самом деле хотите:

set(tuple(zip(p, players)) for p in it.permutations(cards))

Но это занимает слишком много времени. Так что давайте попробуем.

cards = set(["8H", "8S", "8C", "8D", "9H", "9S", "9C", "9D", "10H", "10S", "10C", "10D", "AH", "AS", "AC", "AD"])

def deals(cards, players, cards_per_player):
    if not cards:
        yield []
        return
    for hand in it.combinations(cards, cards_per_player[0]):
        hand = set(hand)
        for deal in deals(cards - hand, players[1:], cards_per_player[1:]):
            yield zip([players[0]]*len(hand), hand) + deal

> for deal in deals(cards, ['_1', '_2', '_3', '_4', '_Tc', '_To'], [3,3,3,3,1,3]):
      print deal

Что по-прежнему занимает много времени, но это множество способов раздачи карт.

person U2EF1    schedule 12.03.2014
comment
В результате получается только одна комбинация, мне нужны все комбинации. Как пример abcd. Глядя на функцию продукта сейчас. - person Pieter Bosma; 12.03.2014
comment
@ user3411641 Хорошо, я понимаю, что вы имели в виду. Обновлено. - person U2EF1; 12.03.2014

arrow_upward
0
arrow_downward

Вы можете использовать массив карточек для каждого человека и расположить карточки по порядку, чтобы при сопоставлении двух массивов они были одинаковыми. Вы можете использовать кортеж (размер 2) для каждой карты, где первый элемент может представлять значение в диапазоне (13), а второй элемент будет цветом (также представленным числом в диапазоне (4)). Вы можете легко сгенерировать колоду с двойным циклом for, может быть как словарь и после раздачи карт, вы можете удалить те, которые вы уже использовали, чтобы не было дубликатов, а когда вы раздали все руки (если у вас есть код будет легко модифицировать под разное количество игроков) вы можете заказать раздачи, сравнить с уже имеющейся базой данных и не сохранять ее если есть совпадение, также вы можете сохранить остаток колоды, чтобы сделать некоторую статистику, если хотите, тогда вы можете иметь все возможные сделки для каждой ситуации, что в любом случае будет огромной базой данных. Таким образом, у вас будут все возможности, без дубликатов в руках или в руках игроков. (у первого игрока рука второго игрока в другой раздаче и наоборот) Надеюсь, это помогло вам или кому-то еще. Я не привожу примеры кода, потому что этот вопрос больше похож на то, как решить эту проблему, а другие дали вам советы по кодированию. Также этот подход можно использовать, даже если вы только что запустили python и до сих пор выполняли только несколько руководств. Удачи ;)

person Csongor    schedule 11.02.2016