生成所有5张牌扑克牌
这个问题乍一看听起来很简单，但是看起来比现在复杂得多。 这让我难以忍受。
有52c5 = 2,598,960种方式从52张牌组中select5张牌。 然而，由于套装在扑克中是可以互换的，其中许多是等价的 – 手牌2H 2C 3H 3S 4D相当于2D 2S 3D 3C 4H – 简单地交换套装。 根据维基百科 ，一旦你考虑可能的西装颜色，有134459个不同的5张牌。
问题是，我们如何有效地产生所有这些可能的手？ 我不希望产生所有的手，然后消除重复，因为我想将问题应用到更大数量的牌上，并且手的数量要评估快速螺旋失控。 我目前的尝试主要集中在深度优先生成和跟踪当前生成的卡片上，以确定下一张卡片或宽度优先的卡片和行列是否有效，生成所有可能的下一张卡片，然后通过转换每个卡片来删除重复通过重新着色来达到“规范”版本。 以下是我在Python中的广度优先解决scheme的尝试：
# 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
任何人都可以build议一个更好的方法来产生不同的手，或者指出我的错误在哪里？
你的总体方法是健全的。 我很确定问题在于你的make_canonical函数。 您可以尝试用num_cards设置为3或4来打印双手，并查找您已经错过的等价物。
我find了一个，但可能会有更多：
# 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]
作为参考，以下是我的解决scheme（开发之前看你的解决scheme）。 我使用了深度优先search而不是广度优先search。 另外，我写了一个函数来检查一个手是否是规范的，而不是写一个把手转换成规范forms的函数。 如果不是规范的话，我可以跳过它。 我定义了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 (eg, [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解决scheme，利用numpy，并生成规范交易以及它们的多样性。 我使用Python的itertools模块来创build所有24种可能的4种套装的排列，然后遍历所有2,598,960种可能的5张牌交易。 每一笔交易都被排列并转换成5行的规范编号。 这是非常快的，因为循环只经过了10次迭代来覆盖所有的交易，只需要pipe理内存需求。 除了使用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
你的问题听起来很有趣，所以我简单地试图通过循环遍历所有可能的手中实现它。 我没有详细看过你的代码，但是看起来我的实现和你的完全不同。 猜猜我的脚本发现了多less手：160537
- 我的手总是sorting，例如2 3 4 4 D
- 如果有两张相同的牌，颜色也被分类（颜色只被称为0,1,2,3）
- 第一张牌总是颜色0，第二种颜色是0或1
- 一张卡片只能有以前卡片的颜色或下一个较大的数字，例如，如果卡片1 + 2的颜色为0，则卡片3只能有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只手是皇家冲洗，所以这些手可以被称为“射频”，加上一个西装指示符，如俱乐部皇家同花顺的“RFC”。 一个10高的心脏冲洗可能是“FLH10”（不知道是否有其他优先的特点冲洗，但我认为这是你所需要知道的）。 “2C 2S AH 10C 5D”的手是一个更长的expression，如果我解开你最初的问题陈述，就像“PR2 A 10 5”。
一旦你定义了不同的手的语法，你可以expression它作为正则expression式，并会告诉你如何产生不同的手的整个空间。 听起来很好玩！
您可以简单地给所有的手一个规范的价值sorting（A到K），然后根据它们的顺序第一次出现顺序分配抽象的适合的信件。
例如：JH 4C QD 9C 3D将转换为3a 4b 9b Jc Qa。
一代人应该最好的dynamic编程：
- 从一组空单手开始，
- 做一个新的集合：
- 对于旧套装中的每只手，通过添加剩余的牌中的一个来产生每个可能的牌
- 规范所有新手
- 删除重复项
初始input：
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 TJQK
步骤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 TJQK
第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 TJQK
步骤3：爬上确定匹配每个不同行的第一套服装，并select匹配不同行的套装（由*标识）
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 TJQK
现在显示重复等级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 TJQK 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 TJQK 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 TJQK
步骤4：一旦有5个单元格设置为1，将总计可能的花色提取手数加1并递增。
提起诉讼的总数可能是134459。 这是我写的testing代码：
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; } } }
希望它被分解得足够容易理解。
这里是一个简单而直接的algorithm，以手套为基础的规范的permutatoins。
- 将手转换成四个比特集，每个西装一个代表西装的牌
- sorting位集
- 将比特集转换回手中
这就是在C ++中的algorithm，有一些暗示的Suit和CardSet类。 请注意，return语句通过连接位串来转换手。
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/你可以select你需要的各种扑克游戏，并在“编程选项卡”中有一个“独特的西装模式”部分。; 所以只要将其复制并加载到程序中可能比试图生成自己的程序更容易。
看看这里：
http://specialk-coding.blogspot.com/
http://code.google.com/p/specialkpokereval/
这些将一张5张牌（和一张7张牌）作为一个整数，这个总和是独立于牌的个人牌。 正是你所需要的。
这是用Objective-C和Java编写的快速排名7和5张牌的scheme的一部分。
如果你只是感兴趣的手，导致不同的手排名，实际上只有7462不同的手类必须考虑（见维基百科 ）。
通过为每个class级及其伴随的多样性创build一个表格，您可以快速检查所有相关的加权概率。 也就是说，假设没有卡是已知的，因此已经预先固定。
在非等价的意义上，你很可能真的想要产生不同的手数。 在这种情况下，根据维基百科文章，有7462个可能的手。 这是一个python片段，将枚举全部。
这个逻辑很简单：每一个五行都有一只手; 另外，如果所有的队伍都是独特的，那么所有的套装都可以形成另一种不同的手牌。
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
