生成所有的五张扑克牌手牌

Question

这个问题乍一看似乎很简单，但实际上比看起来复杂得多。目前我还被困住了。

从52张扑克牌中选择5张牌的方法有52c5 = 2,598,960种。然而，在扑克中，由于花色是可互换的，其中许多手牌是等价的 - 如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

有没有人能提供更好的方法来生成不重复的手牌，或者指出我在尝试中哪里出了问题？

- Nick Johnson

---

好问题，你需要它做什么？如果你想用它来计算一手牌对另一手牌的胜率，你可以使用蒙特卡罗方法。 - dfens

我正在预先计算所有的对决。蒙特卡罗方法是给那些没有足够计算能力的人用的。 ;) - Nick Johnson

你关心手牌的重要排名还是实际排列顺序？例如，如果你的前两张牌不是同一花色，那么你就没有可能组成同花顺，可以在该子树的其余部分中忽略花色。我认为通过仙人掌 Kev 只有大约 7500 种独特的扑克牌手牌等级。让我看看能否找到链接。 - Nick Larsen

@davidchambers 你说得对，按等级顺序生成它们是消除手动排列的最简单方法。每张新卡牌的有效花色集确实会像你描述的那样增加，但有效集取决于所有先前的卡牌 - 例如，如果前两张卡牌是同一花色，则第三张卡牌只有两种可能性。这是我最初使用DFS的方式，但我仍然最终生成了同构手牌。 :/ - Nick Johnson

@NickLarsen 我不关心排名 - 只关心不同的手牌。排名是一个独立的问题。 - Nick Johnson

Answer 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]

供参考，以下是我的解决方案（在查看您的解决方案之前开发）。我使用了深度优先搜索而不是广度优先搜索。此外，我编写了一个函数来检查手牌是否为规范形式，而不是编写一个将手牌转换为规范形式的函数。如果它不是规范形式，我就跳过它。我定义了rank = card％13和suit = card / 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

- Daniel Stutzbach

---

谢谢！你能简要描述一下规范测试是如何工作的吗？我大致明白基本概念，但有一个描述会更好。 - Nick Johnson

@Nick：好的，我已经在我的答案中为canonical函数添加了文档字符串。 - Daniel Stutzbach

非常好的答案，谢谢！实际上，生成规范手牌而不仅仅是测试它是有原因的：有些手牌比其他手牌具有更多的同构性，知道有多少个同构体对应于每个“真实”的手牌是很重要的。 - Nick Johnson

Answer 2

这里有一个Python解决方案，使用numpy生成规范化的发牌组合以及它们的数量。我使用Python的itertools模块创建4种花色的所有24个可能排列，然后迭代遍历所有2598960个5张牌的发牌组合。每个发牌组合只需要5行代码就可以将其排列并转换为规范id。循环仅经过10次迭代即可覆盖所有发牌组合，非常快速，并且只需管理内存需求。除了使用itertools.combinations之外，numpy高效地完成了所有繁重的工作。遗憾的是直接在numpy中不支持这个功能。

import numpy as np
import itertools

# all 24 permutations of 4 items
s4 = np.fromiter(itertools.permutations(range(4)), dtype='i,i,i,i').view('i').reshape(-1,4)

c_52_5 = 2598960 # = binomial(52,5) : the number of 5-card deals in ascending card-value order
block_n = c_52_5/10
def all5CardDeals():
    '''iterate over all possible 5-card deals in 10 blocks of 259896 deals each'''
    combos = itertools.combinations(range(52),5)
    for i in range(0, c_52_5, block_n):
        yield np.fromiter(combos, dtype='i,i,i,i,i', count=block_n).view('i').reshape(-1,5)

canon_id = np.empty(c_52_5, dtype='i')
# process all possible deals block-wise.
for i, block in enumerate(all5CardDeals()):
    rank, suit = block/4, block%4     # extract the rank and suit of each card
    d = rank[None,...]*4 + s4[:,suit] # generate all 24 permutations of the suits
    d.sort(2)                         # re-sort into ascending card-value order
    # convert each deal into a unique integer id
    deal_id = d[...,0]+52*(d[...,1]+52*(d[...,2]+52*(d[...,3]+52*d[...,4])))
    # arbitrarily select the smallest such id as the canonical one 
    canon_id[i*block_n:(i+1)*block_n] = deal_id.min(0)
# find the unique canonical deal ids and the index into this list for each enumerated hand
unique_id, indices = np.unique(canon_id, return_inverse=True)
print len(unique_id) # = 134459
multiplicity = np.bincount(indices)
print multiplicity.sum() # = 2598960 = c_52_5

- JohnLock

Answer 3

您的问题听起来很有趣，所以我尝试了一下按照排序的方式循环遍历所有可能的手牌来实现它。我没有详细查看您的代码，但是我的实现与您的实现似乎非常不同。猜猜我的脚本找到的手牌数量是多少：160537。

以下是我的实现规则：

• 我的手牌总是排好序的，例如 2 3 4 4 D。
• 如果有两张相等的牌，颜色也会排序（颜色只称为 0、1、2、3）。
• 第一张牌的颜色始终为 0，第二张牌的颜色为 0 或 1。
• 一张牌只能有前一张牌的颜色或下一张更大的数字的颜色，例如如果牌 1+2 的颜色为 0，则第三张牌只能有颜色 0 或 1。

您确定维基百科上的数字是正确的吗？

count = 0
for a1 in range(13):
    c1 = 0
    for a2 in range(a1, 13):
        for c2 in range(2):
            if a1==a2 and c1==c2:
                continue
            nc3 = 2 if c1==c2 else 3
            for a3 in range(a2, 13):
                for c3 in range(nc3):
                    if (a1==a3 and c1>=c3) or (a2==a3 and c2>=c3):
                        continue
                    nc4 = nc3+1 if c3==nc3-1 else nc3
                    for a4 in range(a3, 13):
                        for c4 in range(nc4):
                            if (a1==a4 and c1>=c4) or (a2==a4 and c2>=c4) or (a3==a4 and c3>=c4):
                                continue
                            nc5 = nc4+1 if (c4==nc4-1 and nc4!=4) else nc4
                            for a5 in range(a4, 13):
                                for c5 in range(nc5):
                                    if (a1==a5 and c1>=c5) or (a2>=a5 and c2>=c5) or (a3==a5 and c3>=c5) or (a4==a5 and c4>=c5):
                                        continue
                                    #print([(a1,c1),(a2,c2),(a3,c3),(a4,c4),(a5,c5)])
                                    count += 1
print("result: ",count)

- Florianx

---

相当确定。这篇论文《列举起始扑克牌手牌》（http://www.math.sfu.ca/~alspach/comp42.pdf）利用了一些我不敢自称完全理解的组合数学方法，得出了与维基百科相同的数字。（请参阅“五张牌抽”部分） - Nick Johnson

我真的很喜欢这个配色方案，想得很周到！ - Matthieu M.

我发现了一个产生重复的情况：(B0, B1, B2, B3, D0) 和 (B0, B1, B2, B3, D1) 相等。 - Florianx

Answer 4

这里有一个基于花色排列的简单直接的算法，用于将手牌缩减为规范形式。

1. 将手牌转换为四个位集，每个位集代表该花色的牌
2. 对位集进行排序
3. 将位集转换回手牌

以下是C++中的算法示例，其中包含一些隐含的Suit和CardSet类。请注意，返回语句通过连接位字符串来转换手牌。

CardSet CardSet::canonize () const
{
  int smasks[Suit::NUM_SUIT];
  int i=0;
  for (Suit s=Suit::begin(); s<Suit::end(); ++s)
    smasks[i++] = this->suitMask (s);

  sort (smasks, smasks+Suit::NUM_SUIT);

  return CardSet(
    static_cast<uint64_t>(smasks[3])                        |
    static_cast<uint64_t>(smasks[2]) << Rank::NUM_RANK      |
    static_cast<uint64_t>(smasks[1]) << Rank::NUM_RANK*2    |
    static_cast<uint64_t>(smasks[0]) << Rank::NUM_RANK*3);
}

- Andrew Prock

Answer 5

初始输入：

H 0 0 0 0 0 0 0 0 0 0 0 0 0
C 1 0 0 0 0 0 0 0 0 0 0 0 0
D 1 0 0 0 0 0 0 0 0 0 0 0 0
S 1 1 0 0 0 0 0 0 0 0 0 0 0
+ A 2 3 4 5 6 7 8 9 T J Q K

步骤1：对于每个等级，大于或等于已使用的最高等级，将该等级中的所有花色设置为0。您只需要检查更高的牌，因为低组合将由较低的起始点检查。

H 0 0 0 0 0 0 0 0 0 0 0 0 0
C 1 0 0 0 0 0 0 0 0 0 0 0 0
D 1 0 0 0 0 0 0 0 0 0 0 0 0
S 1 0 0 0 0 0 0 0 0 0 0 0 0
+ A 2 3 4 5 6 7 8 9 T J Q K

步骤2：合并为不同的行

0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0
A 2 3 4 5 6 7 8 9 T J Q K

步骤3：向上爬，确定与每个不同行匹配的第一个花色，并选择与不同行匹配的花色（由*标识）

H 0 * 0 0 0 0 0 0 0 0 0 0 0
C 1 0 0 0 0 0 0 0 0 0 0 0 0
D 1 * 0 0 0 0 0 0 0 0 0 0 0
S 1 1 0 0 0 0 0 0 0 0 0 0 0
+ A 2 3 4 5 6 7 8 9 T J Q K

现在显示排名3的重复内容

H 0 0 0 0 0 0 0 0 0 0 0 0 0
C 1 0 0 0 0 0 0 0 0 0 0 0 0
D 1 0 0 0 0 0 0 0 0 0 0 0 0
S 1 1 0 0 0 0 0 0 0 0 0 0 0
+ A 2 3 4 5 6 7 8 9 T J Q K

0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0 0 0 0
A 2 3 4 5 6 7 8 9 T J Q K

H 0 0 * 0 0 0 0 0 0 0 0 0 0
C 1 0 0 0 0 0 0 0 0 0 0 0 0
D 1 0 * 0 0 0 0 0 0 0 0 0 0
S 1 1 * 0 0 0 0 0 0 0 0 0 0
+ A 2 3 4 5 6 7 8 9 T J Q K

步骤4：一旦有5个单元格设置为1，将总可能的花色抽象手数计数增加1并递归上升。

可能的花色抽象手数总数为134,459。这是我编写的测试代码：

using System;
using System.Collections.Generic;
using System.Linq;

namespace ConsoleApplication20
{
    struct Card
    {
        public int Suit { get; set; }
        public int Rank { get; set; }
    }
    
    class Program
    {
        static int ranks = 13;
        static int suits = 4;
        static int cardsInHand = 5;

        static void Main(string[] args)
        {
            List<Card> cards = new List<Card>();
            //cards.Add(new Card() { Rank = 0, Suit = 0 });
            int numHands = GenerateAllHands(cards);
    
            Console.WriteLine(numHands);
            Console.ReadLine();
        }
  
        static int GenerateAllHands(List<Card> cards)
        {
            if (cards.Count == cardsInHand) return 1;
    
            List<Card> possibleNextCards = GetPossibleNextCards(cards);
    
            int numSubHands = 0;
    
            foreach (Card card in possibleNextCards)
            {
                List<Card> possibleNextHand = cards.ToList(); // copy list
                possibleNextHand.Add(card);
                numSubHands += GenerateAllHands(possibleNextHand);
            }
    
            return numSubHands;
        }
    
        static List<Card> GetPossibleNextCards(List<Card> hand)
        {
            int maxRank = hand.Max(x => x.Rank);
            
            List<Card> result = new List<Card>();
    
            // only use ranks >= max
            for (int rank = maxRank; rank < ranks; rank++)
            {
                List<int> suits = GetPossibleSuitsForRank(hand, rank);
                var possibleNextCards = suits.Select(x => new Card { Rank = rank, Suit = x });
                result.AddRange(possibleNextCards);
            }
    
            return result;
        }
    
        static List<int> GetPossibleSuitsForRank(List<Card> hand, int rank)
        {
            int maxSuit = hand.Max(x => x.Suit);
    
            // select number of ranks of different suits
            int[][] card = GetArray(hand, rank);
    
            for (int i = 0; i < suits; i++)
            {
                card[i][rank] = 0;
            }
    
            int[][] handRep = GetArray(hand, rank);
    
            // get distinct rank sets, then find which ranks they correspond to
            IEnumerable<int[]> distincts = card.Distinct(new IntArrayComparer());
    
            List<int> possibleSuits = new List<int>();
    
            foreach (int[] row in distincts)
            {
                for (int i = 0; i < suits; i++)
                {
                    if (IntArrayComparer.Compare(row, handRep[i]))
                    {
                        possibleSuits.Add(i);
                        break;
                    }
                }
            }
    
            return possibleSuits;
        }
    
        class IntArrayComparer : IEqualityComparer<int[]>
        {
            #region IEqualityComparer<int[]> Members
    
            public static bool Compare(int[] x, int[] y)
            {
                for (int i = 0; i < x.Length; i++)
                {
                    if (x[i] != y[i]) return false;
                }
    
                return true;
            }
    
            public bool Equals(int[] x, int[] y)
            {
                return Compare(x, y);
            }
    
            public int GetHashCode(int[] obj)
            {
                return 0;
            }

            #endregion
        }

        static int[][] GetArray(List<Card> hand, int rank)
        {
            int[][] cards = new int[suits][];
            for (int i = 0; i < suits; i++)
            {
                cards[i] = new int[ranks];
            }

            foreach (Card card in hand)
            {
                cards[card.Suit][card.Rank] = 1;
            }
    
            return cards;
        }
    }
}

希望它分解得足够清晰易懂。

- Nick Larsen

---

你的数字与维基百科和我链接的论文不符 - 你明显生成的手牌太少了。 - Nick Johnson

你说得对，我是用最低的牌来初始化它的。一旦使用空手初始化，它会生成134,459个结果。 - Nick Larsen

旧的线程，我知道，但是这段代码使用原样会产生一个错误，因为初始卡没有被填充（第49行无效操作）。然后，如果你填充了该卡，你会得到错误的数字。 - Dave Johnson

我复制了这段代码，但无法得到正确的134,459计数。相反，得到了175,123。 - Jim Mc

Answer 6

我不是扑克牌手，所以对于手牌优先级的细节超出了我的理解范围。但问题似乎在于您正在通过从牌堆中生成集合来遍历“五张牌的集合”空间，而您应该遍历“不同扑克牌手”的空间。

不同手牌的空间将需要一个新的语法。重要的是要准确捕捉与手牌优先级相关的信息。例如，只有四种手牌是皇家同花顺，因此这些手牌可以描述为符号“RF”加上一种花色标识符，例如“RFC”表示草花皇家同花顺。一个10高的红心同花顺可以是“FLH10”（不确定是否还有其他同花顺的优先级特征，但我认为这就是你需要知道的全部）。如果我理解您最初的问题陈述，那么一个“2C 2S AH 10C 5D”的手牌将是一个更长的表达式，类似于“PR2 A 10 5”。

一旦您定义了不同手牌的语法，您就可以将其表示为正则表达式，这将告诉您如何生成整个不同手牌的空间。听起来很有趣！

- Bill Gribble

---

你误解了 - 我不是在尝试枚举结果（对子，两对等等），而是在尝试枚举所有独特的5张牌组合，无需考虑花色重新分配。排名是完全不同的问题。AC AD 2C 3C 4C 和 AC AD 2H 3H 4H 排名相同，但它们是不同的手牌，因为你不能通过交换花色将一个转换成另一个。 - Nick Johnson

我明白了。无论如何，相同的技术适用，但我的例子不好。首先，确定您想要遍历的空间中唯一项的语法；将其编写为正则表达式；然后通过扩展正则表达式来遍历该空间。 - Bill Gribble

当然可以 - 但找到枚举唯一元素的方法才是我问题的重点。 - Nick Johnson

Answer 7

你可以简单地给所有手牌一个规范的排序（从A到K），然后根据它们在该顺序中首次出现的顺序分配抽象花色字母。

例如：JH 4C QD 9C 3D 将转换为 3a 4b 9b Jc Qa。

生成最好使用动态编程：

• 从一个空的单手牌集合开始，
• 创建一个新的集合：
  • 对于旧集合中的每个手牌，通过添加剩余的一张牌来生成每个可能的手牌
  • 规范化所有新手牌
  • 删除重复项

- Svante

---

您所描述的过程正是我在代码片段中所做的 - 但它仍然生成了比应该存在的更多的手牌，因此我显然做错了些什么。 - Nick Johnson

我在你的片段中没有看到任何排序程序，并通过位运算完成所有操作并不利于代码。我的猜测是，您没有正确将相等价值的牌规范化，因此 3D 4H 5D 5H 可以变成 3a 4b 5a 5b 和 3a 4b 5b 5a。 - Svante

排序过程在"min_card"参数中表达，它不会生成低于该值的级别，从而确保按级别排序。您似乎对规范化是正确的，不过您能提出修复的建议吗？ - Nick Johnson

Answer 8

请看这里：

http://specialk-coding.blogspot.com/

http://code.google.com/p/specialkpokereval/

这些将一个5张牌手牌（和一个7张牌手牌）视为一个整数，即个别牌的总和，与花色无关。这正是你所需要的。

这是快速排列7张和5张牌手牌的方案的一部分，使用Objective-C和Java编写。

- Ken

Answer 9

如果你只对不同手牌排名的结果感兴趣，实际上只有7462个不同的手牌类别需要考虑（参见维基百科）。

通过创建一个包含每个类别及其相应重复次数示例的表格，您可以快速检查所有相关手牌及其概率加权。这是在没有已知卡牌且已经固定的情况下进行的。

- Thies Heidecke

Answer 10

生成五张牌的等价类并不是一件容易的事情。 当我需要这个的时候，我通常使用 http://www.vpgenius.com/ 网页。在 http://www.vpgenius.com/video-poker/games/ 上，您可以选择所需的扑克游戏种类，并在 "编程选项卡" 中找到 "独特花色模式" 部分。因此，只需复制并加载该部分进入程序，可能比尝试生成自己的更容易。

- Rok

---

这仅适用于视频扑克，与仅生成独特的手牌完全不同。 - Nick Johnson

如果您使用Jacks-or-better类型，您将拥有相同的不同手牌。 - Rok

所以，这似乎是一个合理的方法。不过我更愿意看到如何生成所有花色等价类的描述 - 之后，生成每个类中的所有手牌应该相对容易。 - Nick Johnson