产生所有5张牌手

https://stackoverflow.com/questions/3829457

26-09-2019
|

题

这问题听起来很简单，乍看之下，但事实证明是很复杂得多，它似乎。这让我困难的时刻。

有52c5=2,598,960方式选择5张卡片从52张牌。然而，由于诉讼是可以互换的扑克，许多的这些都是同等的手2H2C3H3S4D相当于2D2S3D3C4小时-只是换衣服左右。根据维基百科, 有134,459不同的5张手一旦你的帐户可能的适应recolorings.

问题是，我们如何有效地产生所有这些可能的手中？我不希望产生的所有手，然后消除重复，因为我想要应用问题的更大的数字卡片，且数量的手评估快速的失去控制。我当前的尝试围绕两产生深度优先，并跟踪的当前产生的卡片来确定什么最适合和排的有效期为下一张卡片，或广度优先，产生的所有可能的下一个卡片，然后去除重复通过转换的各个方面，一个"通用"的版本，通过重新着色.这是我试图在一个广度优先方案，在蟒蛇：

# 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

任何人都可以建议一种更好的方式产生仅仅是不同的手中，或指出在哪里我已经错我尝试？

解决方案

您整体方式是声音。我敢肯定，问题在于你make_canonical功能。你可以尝试设置为3或4，寻找换算公式，你已经错过NUM_CARDS打印出的手。

我发现之一，但可以有更多：

# 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

其他提示

下面是一个Python溶液，使得使用numpy的，并产生规范化的交易以及它们的多重性。我使用Python的迭代工具创建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

你的问题听起来很有意思，因此我简单试图实现它的通过只是循环的所有可能的手在一个有序的方式。我不看着你的代码中的细节，但看来我的实现是相当不同于你的。你猜怎么着数的手我的脚本中发现：160537

我的手总是排，例如2 3 4 4D
如果有2等于卡，色彩也是排(颜色都只是称为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)

我不是一个扑克选手，所以手的优先细节超出了我。不过好像问题是，你是从甲板上，当你要遍历的“不同的扑克手”的空间。

发电机组穿越的“套5张牌”的空间

不同的手的空间将需要一个新的语法。最重要的是捕捉准确，是有关手的优先级的信息。例如，有4只手属于皇家刷新，所以，这些手可以在俱乐部被描述为符号“RF”加西装指示符，如“RFC”为皇家齐平。 10高心脏冲洗可能是“FLH10”（不知道是否有刷新的其他优先特征，但我认为这是所有你需要知道的）。一只手是“2C 2S AH 10C 5D”将是一个较长的表情，像“PR2 10 5”如果我已了解您最初的问题陈述。

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

你可以简单地得到所有人的规范订购的价值(A至K)，然后分配抽象适的字母根据他们的第一次出现顺序。

例如：JH4C QD9C3D将转换为3a4b9b Jc Qa。

代工作最好应该以动态的程序：

开始设置的一个方面就是空的，
做一个新的设置：
- 对于每个方面在旧的设定，生成每个可能方面通过增添一个剩余的卡
- 规范化的所有新的手
- 删除重复

最初输入：

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和recurse。

总数的衣抽象的手可能是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;
        }
    }
}

我们希望它被破坏了足以容易地可以理解的。

这是一个简单和直接的算法用于减少手来规范一个基于适应permutatoins.

转换方面，四位集，每套装代表卡西装
排序位集
换位集回到手

这是什么样的算法看起来像是在C++，有一些暗示的满足和CardSet课程。注意返回的声明转换方面通过连接的bitstrings.

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);
}

看 Pokersource 。这个问题变得更糟，当你正在考虑在完成手给出了一些卡已经绘制。

后面PokerStove的人确实在该方向上非常出色，但所公开的来源。

生成等价类5分的手是不容易的事。当我需要这个，我通常使用 http://www.vpgenius.com/ 网页。在 http://www.vpgenius.com/video-poker/games/ 你可以选择各种你需要的扑克游戏，并在“程序选项卡”，你有“独特的套装模式”的部分。因此，只要是复制和加载到程序可能会比试图生成自己更容易。

看看这里：

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

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

这些认为有5张牌（和7张牌），为整数，总和的各个卡，它是独立的西装。正是你需要的。

这是快速排序方案的一部分7-和5张手，用Objective-C和Java。

如果你只是有兴趣的手这一结果在不同的手的排名，其实有只有7462是必须要考虑不同的手类（见的维基百科）。

通过与每个类的实例创建表及其伴随的多样性，您可以检查所有相关的手与他们的概率加权相当快。也就是说，假定没有卡是已知的，因此预先固定了。

有可能到头来你真的要产生不同的手数，在不等价的意义。在这种情况下，根据维基百科的文章有7462手可能。这里是一个Python代码片段将一一列举所有。

的逻辑很简单：有一个手队伍的每个5组;此外，如果所有的行列是不同的，另外，不同种类的手可以通过使所有的服匹配来形成。

count = 0 

for i in range(0,13):
    for j in range (i,13):
        for k in range(j,13):
            for l in range(k,13):
                for m in range(l,13):
                    d = len(set([i,j,k,l,m])) # number of distinct ranks
                    if d == 1: continue    # reject nonsensical 5-of-a-kind
                    count += 1
                    # if all the ranks are distinct then 
                    # count another hand with all suits equal
                    if d == 5: count += 1

print count   # 7462

许可以下： CC-BY-SA 和归因

不隶属于 StackOverflow