生成所有5张纸牌扑克手

一尘不染

生成所有5张纸牌扑克手

algorithm

乍一看，这个问题听起来很简单，但事实却比看起来复杂得多。现在让我感到难过。

有52c5 = 2,598,960种方法可从52张卡片组中选择5张卡片。但是，由于花色在扑克中是可以互换的，因此其中许多花色是等效的-手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

谁能建议一种更好的方法来只产生不同的牌，或者指出我在尝试中出错的地方？

阅读 336

2020-07-28

共1个答案

一尘不染

您的总体方法是合理的。我很确定问题出在您的make_canonical功能上。您可以尝试将num_cards设置为3或4来打印出双手，并寻找您错过的等效项。

我找到了一个，但可能还有更多：

# The inputs are equivalent and should return the same value
print make_canonical([8, 12 | 1]) # returns [8, 13]
print make_canonical([12, 8 | 1]) # returns [12, 9]

供参考，以下是我的解决方案（在查看您的解决方案之前已开发）。我使用深度优先搜索而不是宽度优先搜索。另外，我没有编写将手形转换为规范形式的函数，而是编写了一个函数以检查手形是否规范。如果不是规范，我将其跳过。我定义的等级=卡％13，套装=卡/13。这些差异都不重要。

import collections

def canonical(cards):
    """
    Rules for a canonical hand:
    1. The cards are in sorted order

    2. The i-th suit must have at least many cards as all later suits.  If a
       suit isn't present, it counts as having 0 cards.

    3. If two suits have the same number of cards, the ranks in the first suit
       must be lower or equal lexicographically (e.g., [1, 3] <= [2, 4]).

    4. Must be a valid hand (no duplicate cards)
    """

    if sorted(cards) != cards:
        return False
    by_suits = collections.defaultdict(list)
    for suit in range(0, 52, 13):
        by_suits[suit] = [card%13 for card in cards if suit <= card < suit+13]
        if len(set(by_suits[suit])) != len(by_suits[suit]):
            return False
    for suit in range(13, 52, 13):
        suit1 = by_suits[suit-13]
        suit2 = by_suits[suit]
        if not suit2: continue
        if len(suit1) < len(suit2):
            return False
        if len(suit1) == len(suit2) and suit1 > suit2:
            return False
    return True

def deal_cards(permutations, n, cards):
    if len(cards) == n:
        permutations.append(list(cards))
        return
    start = 0
    if cards:
        start = max(cards) + 1
    for card in range(start, 52):
        cards.append(card)
        if canonical(cards):
            deal_cards(permutations, n, cards)
        del cards[-1]

def generate_permutations(n):
    permutations = []
    deal_cards(permutations, n, [])
    return permutations

for cards in generate_permutations(5):
    print cards

它生成正确数量的排列：

Cashew:~/$ python2.6 /tmp/cards.py | wc
134459

2020-07-28