如何在C语言中实现5张牌的反向Fisher–Yates洗牌算法

需求说明 #

以整副52张牌为随机池，仅对前5张牌执行洗牌操作，开发时参考现代Fisher-Yates洗牌算法的实现逻辑，原实现存在逻辑问题。

参考算法伪代码 #

-- 打乱含n个元素的数组a（下标范围0..n-1）：
for i from 0 to n−2 do
     j ← 满足 i ≤ j < n 的随机整数
     交换 a[i] 和 a[j]

原实现代码 #

#include <limits.h>
#include <stdlib.h>
#include <stdio.h>

enum { NUM_CARDS_IN_DECK = 52 };
enum { NUM_CARDS_IN_HAND = 5 };

typedef unsigned int Card;

typedef struct
{
    Card cards[NUM_CARDS_IN_DECK];
} Deck;

unsigned int GetRandomNumber(unsigned int range)
{
    if (range == 0) return UINT_MAX;

    /* 用除法截断找到可被range整除的最大数 */
    const unsigned int randLimit = (RAND_MAX / range) * range;
    unsigned int number = randLimit;
    while (number >= randLimit) number = (unsigned int)rand();
    return number % range;
}

void ShuffleDeck(Deck deck[])
{
    for (unsigned int cardIndex = 0; cardIndex < NUM_CARDS_IN_HAND; cardIndex++)
    {
        unsigned int random = cardIndex + GetRandomNumber(NUM_CARDS_IN_DECK - cardIndex); // 需要random大于等于cardIndex
        printf("\n %d \n", random);
        const Card temp = deck->cards[random];
        deck->cards[random] = deck->cards[cardIndex];
        deck->cards[cardIndex] = temp;
    }
}

int main(void) 
{
    Card cards[NUM_CARDS_IN_DECK] = { 0 };
    Deck deck = { cards };

    for (int index = 0; index < 5; index++) 
    {
        for (int index = 0; index < NUM_CARDS_IN_DECK; index++)
        {
            deck.cards[index] = index;
        }

        printf("\nstarting deck : ");
        for (int index = 0; index < NUM_CARDS_IN_DECK; index++)
        {
            if (index != 0) printf(" ,");
            printf("%d", deck.cards[index]);
        }
        printf("\n");

        ShuffleDeck(&deck);

        printf("\nshuffled deck : ");
        for (int index = 0; index < NUM_CARDS_IN_DECK; index++)
        {
            if (index != 0) printf(" ,");
            printf("%d", deck.cards[index]);
        }
        printf("\n");
    }
}

修复方案 #

无需在ShuffleDeck()中添加额外循环，直接使用random = cardIndex + GetRandomNumber(NUM_CARDS_IN_DECK - cardIndex)执行无条件交换即可，该方案已验证可正常工作。

内容的提问来源于stack exchange，提问作者Andrew Hanson