Эта проблема кажется простой на первый взгляд, но оказывается намного сложнее, чем кажется. На этот раз меня насторожило.
Есть 52c5 = 2 598 960 способов выбрать 5 карт из колоды из 52 карт. Однако, поскольку костюмы взаимозаменяемы в покере, многие из них эквивалентны - рука 2H 2C 3H 3S 4D эквивалентна 2D 2S 3D 3C 4H - просто меняйте костюмы вокруг. Согласно wikipedia, есть 134,459 отдельных 5-карточных рук, когда вы учитываете возможные перекраски костюма.
Вопрос в том, как мы эффективно генерируем все эти возможные руки? Я не хочу генерировать все руки, а затем удалять дубликаты, поскольку я хочу применить проблему к большему количеству карт, а количество рук - для оценки быстрых спиралей из-под контроля. Мои текущие попытки сосредоточились вокруг либо генерации глубины, и отслеживания созданных в настоящее время карточек, чтобы определить, какие костюмы и ранги действительны для следующей карты, или в ширину, генерируя все возможные следующие карты, а затем удаляя дубликаты, преобразовывая каждый ручную к "канонической" версии путем повторного окрашивания. Здесь моя попытка решения с шириной в Python:
# A card is represented by an integer. The low 2 bits represent the suit, while
# the remainder represent the rank.
suits = 'CDHS'
ranks = '23456789TJQKA'
def make_canonical(hand):
suit_map = [None] * 4
next_suit = 0
for i in range(len(hand)):
suit = hand[i] & 3
if suit_map[suit] is None:
suit_map[suit] = next_suit
next_suit += 1
hand[i] = hand[i] & ~3 | suit_map[suit]
return hand
def expand_hand(hand, min_card):
used_map = 0
for card in hand:
used_map |= 1 << card
hands = set()
for card in range(min_card, 52):
if (1 << card) & used_map:
continue
new_hand = list(hand)
new_hand.append(card)
make_canonical(new_hand)
hands.add(tuple(new_hand))
return hands
def expand_hands(hands, num_cards):
for i in range(num_cards):
new_hands = set()
for j, hand in enumerate(hands):
min_card = hand[-1] + 1 if i > 0 else 0
new_hands.update(expand_hand(hand, min_card))
hands = new_hands
return hands
К сожалению, это создает слишком много рук:
>>> len(expand_hands(set([()]), 5))
160537
Может ли кто-нибудь предложить лучший способ генерировать только отдельные руки или указать, где я ошибся в своей попытке?