如何为扑克游戏生成2,598,960手牌（有效方式）

html5 • • 问答

使用选择方法 nPk（即 nPk = n!/(nk)!*k!）计算 52 副牌中的扑克手总数（即每手五张牌），即 2,598,960 手可能。我想做的是生成所有可能的情况（即 2,598,960 手）。我想到的唯一方法是随机生成一个手并将其添加到一个向量中。每次添加手牌时，我都会检查它是否已经存在，如果存在，则继续生成随机手牌。这当然会奏效，但我正在为此寻找更快、更优雅的方法。一手牌的顺序并不重要。这是一个最小的工作示例，可以节省您的时间。

#include <iostream>
#include <string>
#include <vector>
#include <ctime>
using namespace std;

const int SUIT_MAX(4);
const int RANK_MAX(13);
const int HAND_SZ(5);
const std::string SUIT[SUIT_MAX]  = {"S", "H", "D", "C"};
const std::string RANK[RANK_MAX]  = {"2","3","4","5","6","7","8","9","10","J","Q","K","A"};

class Card
{
public:
    Card(const string &suit, const string &rank) { m_card = rank + suit; }
    std::string print() const { return m_card; }
private:
    string m_card;
};

class Hand
{
public:
    Hand(const vector<Card>& cards) 
    { 
        m_hand.push_back(cards);
    }
    void printHand()
    {
        for (int i(0); i < m_hand.size(); ++i)
            for (int j(0); j < m_hand[i].size(); ++j)
                cout << m_hand[i][j].print() << " ";
        cout << endl;
    }
private:
    vector<vector<Card>> m_hand;
};

int main()
{
    srand((int) time(0));
    Card c1(SUIT[0], RANK[3]);
    vector<Card> handVec;
    
    for(int i(0); i < HAND_SZ; ++i){
        int suit = (rand() % (SUIT_MAX));
        int rank = (rand() % (RANK_MAX));
        Card c(SUIT[suit], RANK[rank]);
        handVec.push_back(c);
    }
        
    Hand h1(handVec);
    h1.printHand();
    
    return 0;
}

回答

更好的方法是给所有卡片一个数字索引，然后编写一个递归函数来迭代所有现有的组合，而不是猜测和检查。假设您有一副有 5 张牌的牌，而手上只有 3 张，这将是您的结果。

1,2,3
1,2,4
1,2,5
1,3,4
1,3,5
1,4,5
2,3,4
2,3,5
2,4,5
3,4,5

下一张牌总是比前一张牌高，你只需增加最后一行直到你到达最高的牌，然后你增加它之前的牌。

请注意，在上面的示例中，第一张牌只到highest_card-2，第二张牌到highest_card-1。从而第二张牌开始，lowest_card+1第三手牌开始于lowest_card+2

更新

这是代码

std::vector<std::vector<int>> all_options;

int factorial(int x)
{
    int total = 1;
    for(int i = 1; i <= x; i++)
        total *= i;
    return total;
}

int combination(int total, int x)
{
    return factorial(total) / (factorial(total-x) * factorial(x));
}

void _recursive_combination(int min, int max, int current_depth, int max_depth, std::vector<int> &previous_values)
{
    for(int i = min; i <= max; ++i) {
        previous_values.push_back(i);
        if( current_depth == max_depth )
            all_options.push_back(previous_values);
        else
            _recursive_combination(i + 1, max + 1, current_depth + 1, max_depth, previous_values);
        previous_values.pop_back();
    }
}

// depth starts at 1, not 0.
void initialize_combinations(int min, int max, int depth)
{
    // Be carefull! 52! is too big.
    // int total_combinations = combination(max - min + 1, depth) Doesn't work as 52! is too high.
    // all_options.reserve(total_combinations);

    std::vector<int> buffer;
    buffer.reserve(depth);

    _recursive_combination(min, max - depth + 1, 1, depth, buffer);
}

void print_combinations()
{
    for(auto &row : all_options){
        for(auto col : row)
            std::cout << " " << col;
        std::cout << "n";
    }
}

int main()
{
    int cards_per_hand = 5;

    auto start = std::chrono::system_clock::now();
    initialize_combinations(1, 52, cards_per_hand);
    std::chrono::milliseconds duration = std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::system_clock::now() - start);

    // print_combinations(); // Be carefull, this will make you wait for an eternity.
    std::cout << "nnSize: " << std::size(all_options);
    std::cout << "nTime: " << duration;
    std::cout << std::endl;

    return 0;
}

在我的 PC 上，调试模式下大约需要 6.7 秒，发布模式下大约需要 0.2 秒。您可以通过预订来减半2.598.960。您必须对其进行硬编码，因为组合计算会导致数字溢出。

以上是如何为扑克游戏生成2,598,960手牌（有效方式）的全部内容。
THE END
分享
二维码
< <上一篇
下一篇>>