38

この問題は一見単純に聞こえますが、見た目よりもはるかに複雑であることがわかります。今のところ困惑しています。

52カードデッキから5枚のカードを選択する52c5=2,598,960の方法があります。ただし、ポーカーではスーツは交換可能であるため、これらの多くは同等です-ハンド2H 2C 3H3S4Dは2D2S3D3C4Hと同等です-単にスーツを交換するだけです。ウィキペディアによると、スーツの色の変更の可能性を考慮すると、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

誰かが明確な手を生成するためのより良い方法を提案したり、私の試みでどこが間違っていたかを指摘したりできますか？

4

11 に答える 11

18

あなたの全体的なアプローチは健全です。問題はあなたの関数にあると私はかなり確信しています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
于 2010-09-30T14:41:28.360 に答える
3

これは、numpyを利用し、正規の取引とその多重度を生成するPythonソリューションです。Pythonのitertoolsモジュールを使用して、4つのスーツの24の可能な順列すべてを作成し、2,598,960の可能な5枚のカードの取引すべてを反復処理します。各取引は並べ替えられ、わずか5行で正規IDに変換されます。ループはすべての取引をカバーするために10回の反復を通過するだけであり、メモリ要件を管理するためにのみ必要であるため、非常に高速です。の使用を除いて、すべての重い持ち上げはnumpyで効率的に行われますitertools.combinations。これが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
于 2012-12-12T10:04:45.763 に答える
2

あなたの問題は面白そうだったので、私は単純に、可能なすべての手をソートされた方法でループすることによってそれを実装しようとしました。私はあなたのコードを詳細に調べていませんが、私の実装はあなたの実装とはかなり異なっているようです。私のスクリプトが見つけた手の数を推測します：160537

  • 私の手は常にソートされています、例えば2 3 4 4 D
  • 等しいカードが2枚ある場合、色もソートされます（色は単に0、1、2、3と呼ばれます）
  • 最初のカードの色は常に0、2番目の色は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)
于 2010-09-30T13:37:23.853 に答える
1

私はポーカープレイヤーではないので、ハンドの優先順位の詳細は私を超えています。しかし、問題は、「異なるポーカーハンド」のスペースをトラバースする必要があるときに、デッキからセットを生成することによって「5枚のカードのセット」のスペースをトラバースしていることのようです。

明確な手のスペースには、新しい文法が必要になります。重要なことは、手の優先順位に関連する情報を正確にキャプチャすることです。たとえば、ロイヤルフラッシュであるハンドは4つしかないため、これらのハンドは、シンボル「RF」に加えて、クラブのロイヤルフラッシュの「RFC」のようなスーツ指定子として説明できます。10ハイハートフラッシュは「FLH10」である可能性があります（フラッシュに他の優先特性があるかどうかはわかりませんが、知っておく必要があるのはそれだけだと思います）。「2C2SAH10C 5D」のハンドは、最初の問題の説明がわからない場合は「PR2 A 105」のように、より長い表現になります。

個別の手の文法を定義したら、それを正規表現として表現できます。これにより、個別の手の空間全体を生成する方法がわかります。楽しいように聞こえる！

于 2010-09-30T10:26:29.143 に答える
1

すべての手に値の正規の順序（AからK）を与えるだけで、最初に出現する順序に従って抽象的なスーツの文字を割り当てることができます。

例：JH 4C QD9C3Dは3a4b9bJcQaに変換されます。

生成は動的計画法として最適に機能するはずです。

  • 空の片手のセットから始めます。
  • 新しいセットを作成します。
    • 古いセットの各ハンドについて、残りのカードの1つを追加して、可能な各ハンドを生成します。
    • すべての新しい手を正規化する
    • 重複を削除する
于 2010-09-30T12:51:36.787 に答える
1

初期入力：

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

うまくいけば、それは簡単に理解できるように十分に分割されています。

于 2010-09-30T16:35:10.913 に答える
1

これは、スーツのパーミュタトインに基づいて手を標準的なものに減らすための単純で簡単なアルゴリズムです。

  1. 手を4つのビットセットに変換します。スーツごとに1つ、スーツのカードを表します。
  2. ビットセットを並べ替える
  3. ビットセットを手元に戻す

これは、C ++でのアルゴリズムの外観であり、いくつかの暗黙の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);
}
于 2012-03-19T19:11:35.887 に答える
0

5枚のカードハンドの同値類を生成するのは簡単な作業ではありません。これが必要なときは、通常http://www.vpgenius.com/Webページを使用します。http://www.vpgenius.com/video-poker/games/で、必要なポーカーゲームの種類を選択できます。また、[プログラミング]タブには、[ユニークなスーツパターン]のセクションがあります。したがって、それをコピーしてプログラムにロードする方が、独自に生成するよりも簡単な場合があります。

于 2010-09-30T11:05:36.747 に答える
0

ここを見てください：

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

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

これらは、5枚のカードの手（および7枚のカードの手）を整数と見なし、個々のカードの合計であり、スーツとは無関係です。まさにあなたが必要なもの。

これは、Objective-CとJavaで記述された、7枚と5枚のカードのハンドをすばやくランク付けするためのスキームの一部です。

于 2011-04-12T02:31:26.483 に答える
0

異なるハンドランキングをもたらすハンドだけに興味がある場合は、実際に考慮しなければならないのは7462の異なるハンドクラスだけです（ウィキペディアを参照）。

各クラスの例とそれに付随する多重度を含むテーブルを作成することにより、確率で重み付けされたすべての関連するハンドを非常に高速にチェックできます。つまり、カードが知られていないため、事前に修正されていると仮定します。

于 2011-04-28T03:33:35.150 に答える
-1

非等価の意味で、あなたは本当に多くの異なるハンドを生成したいのかもしれません。その場合、ウィキペディアの記事によると、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
于 2012-07-08T18:53:40.457 に答える