Эта проблема на первый взгляд звучит просто, но оказывается намного сложнее, чем кажется.Меня это озадачило.
Есть 52c5 = 2 598 960 способов выбрать 5 карт из колоды из 52 карт.Однако, поскольку в покере взаимозаменяемы костюмы, многие из них эквивалентны - рука 2H 2C 3H 3S 4D эквивалентна 2D 2S 3D 3C 4H - просто поменяйте местами костюмы.Согласно Википедии , существует 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
Может кто-нибудь предложить лучший способ генерировать только отличительныеруки, или укажите, где я ошибся в своей попытке?