5 枚すべてのカード ポーカー ハンドを生成する
https://stackoverflow.com/questions/3829457
-
26-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
この問題は一見すると単純そうに見えますが、実際は見た目よりもはるかに複雑であることがわかります。今のところ私は困惑しています。
52 枚のカード デッキから 5 枚のカードを選択する方法は 52c5 = 2,598,960 通りあります。ただし、ポーカーではスーツは交換可能であるため、これらの多くは同等です。ハンド 2H 2C 3H 3S 4D は 2D 2S 3D 3C 4H と同等です。単にスーツを交換するだけです。によると ウィキペディア, 、スーツの色変更の可能性を考慮すると、5 枚のカードのハンドは 134,459 通りあります。
問題は、これらすべての可能なハンドを効率的に生成するにはどうすればよいでしょうか?制御不能な高速スパイラルを評価するために、より多くのカードとハンドの数に問題を適用したいので、すべてのハンドを生成してから重複を排除することはしたくありません。私の現在の試みは、深さ優先で生成し、現在生成されているカードを追跡して次のカードに有効なスーツとランクを決定するか、幅優先で考えられるすべての次のカードを生成し、それぞれを変換して重複を削除するかのどちらかを中心としています。色を変更して「正規」バージョンに移行します。これは、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
誰かが個別の手だけを生成するより良い方法を提案してもらえますか、または私の試みでどこが間違っていたかを指摘してもらえますか?
解決
総合的なアプローチです。またまた、問題と 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
他のヒント
ここでnumpyのを利用し、その多様性だけでなく、正規の取引を生成し、Pythonのソリューションです。私は、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
お客様の問題点を鳴ら面白い、簡単な試合を実装しているだけでループすべてを可能に手を取ってソートされます。私はただ見てコードの詳細にうですが、私の実装はかなり異なるからです。ここでカウントの手クリプトが160537
- 私の手はずを整理など2 3 4 4D
- がある場合2等しいカードを彩りもソート色だという0,1,2,3)
- 最初のカードは常に色が0の時、セカンドカラーを0または1
- カードで色をしているのは、以前のカードまたは次の大きな番号例場合はカード1+2カラー0カードつきの色は0または1
をしていますが、番号をwikipediaに適切なものはどれですか。
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枚のカードのセット」のスペースを横断していることであるようにしかし、それはそうです。
明確な手のスペースは、新しい文法が必要になります。重要なことは、まさに手の優先順位に関連する情報を収集することです。これらの手がクラブでロイヤルフラッシュのための「RFC」のように、記号「RF」プラススーツ指定子として記述することができるので、例えば、王室のフラッシュのみ4手が、あります。 10高心臓フラッシュは「FLH10」（ないでくださいそこにフラッシュの他の優先順位の特性がありますが、私はそれはあなたが知る必要があるすべてだと思う場合）である可能性があります。私はあなたの最初の問題文をundestand場合は、「2C 2S AH 10C 5D」で手が長い表現、「PR2 A 10 5」のようなものになるだろう。
きだというすべてに手を標準的な順序付けの価値（K）を割り当ての抽象スーツの文字によって順に初登場の順になりました。
例:JH4C QD9C3Dうに変換する3a4b9b Jc Qa.
世代を最大限に高ダイナミックプログラミング：
- タセットの単一空
- 新しいセット：
- 各手のセットを別に手を加えの残りカード
- canonicalizeすべての新しい手
- 重複削除
初期入力:
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)にすると、増加量は合計でスーツを抽出し手数1recurseます。
の総数のスーツを抽象化手可能な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.
- 変換の手にbitsets毎に一つのスーツを代表すカードスーツの
- 並べ替えるには、bitsets
- 変換bitsets入手
このアルゴリズムのようにな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の背後にある男が、この方向で素晴らしい仕事をしたが、ソースが開示されています。
くはこちらをご覧ください:
http://specialk-coding.blogspot.com/
http://code.google.com/p/specialkpokereval/
これらについて5カード手(7-カードを手に)整数としてきた場合には、個々のカード、独立した。まさにそのものです。
このスキームを迅速にランキング7-5カードを手に、Objective-CおよびJava.
異なるハンド ランキングをもたらすハンドにのみ興味がある場合、実際に考慮する必要がある個別のハンド クラスは 7,462 個だけです (「 ウィキペディア).
各クラスとそれに付随する多重度の例を含むテーブルを作成すると、確率で重み付けされた関連するすべてのハンドを非常に迅速に確認できます。つまり、既知のカードがないため、事前に固定されていると仮定します。
チャンスはあなたが本当に非同等の意味で、明確な手の数を生成したいされています。その場合には、Wikipediaの記事によると7462人の可能な手があります。ここでは、それらすべてを列挙しますPythonのスニペットです。
は論理は単純である：ランクの各5セットのための1つの手があります。全てのランクが明瞭である場合以外に、手の他、異なる種類のすべてのスーツが一致することにより形成することができる。
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
