求一种限制连续重复次数的等概率字符串洗牌算法

核心需求回顾 #

• 对输入字符串随机洗牌，结果中相同字符连续出现次数不得超过MaxConsecutiveRepetition
• 所有合法洗牌结果出现概率严格相等
• 需规避三种低效/无效思路：朴素重洗（极端场景性能崩盘）、全排列筛选（阶乘复杂度不可行）、修改Fisher-Yates算法（无法保证等概率）

可行算法：动态规划加权随机选择法 #

这个方法通过逐步构建结果字符串+动态规划计算合法排列权重+加权随机选择，既保证合法约束，又严格满足等概率要求。

算法核心思路 #

1. 预处理统计：先统计输入字符串中每个字符的剩余出现次数，这是后续计算的基础。
2. 状态追踪：记录当前已构建字符串的末尾字符及连续出现次数，用于判断下一个字符是否合法。
3. 权重计算：对每个可选的合法字符，用记忆化动态规划（DP）计算「选择该字符后，剩余字符能组成的合法排列总数」，这个数值就是该字符的选择权重。
4. 加权随机选择：按照各字符的权重比例随机选择下一个字符，确保每个合法最终排列被选中的概率均等。
5. 状态更新：追加选中的字符，更新剩余计数和末尾连续状态，重复直到构建完整个字符串。

为什么能保证等概率？ #

假设当前有两个可选字符c1和c2，对应的后续合法排列数为w1和w2，那么选择c1的概率是w1/(w1+w2)。每一步的选择权重完全对应后续的合法可能性数量，相乘后每个最终合法排列的总选中概率都是1/(总合法排列数)，完全满足等概率要求。

C语言实现示例 #

1. 字符计数统计函数

#include <string.h>
#include <stdlib.h>
#include <stdint.h>

typedef struct {
    char c;
    int count;
} CharCount;

// 统计输入字符串中各字符的出现次数，返回不同字符的数量
int count_chars(const char* str, CharCount* counts) {
    int ascii_counts[256] = {0};
    int len = strlen(str);
    for (int i = 0; i < len; i++) {
        ascii_counts[(unsigned char)str[i]]++;
    }

    int idx = 0;
    for (int i = 0; i < 256; i++) {
        if (ascii_counts[i] > 0) {
            counts[idx].c = (char)i;
            counts[idx].count = ascii_counts[i];
            idx++;
        }
    }
    return idx;
}

2. 记忆化DP计算合法排列数

// 简易哈希表缓存（仅示例，实际可优化为更高效的实现）
typedef struct CacheNode {
    char last_char;
    int last_run;
    CharCount counts[256];
    int count_num;
    long long perm_count;
    struct CacheNode* next;
} CacheNode;

static CacheNode* cache = NULL;

// 检查缓存中是否存在对应状态，存在则返回排列数，否则返回-1
long long check_cache(char last_char, int last_run, CharCount* counts, int count_num) {
    CacheNode* curr = cache;
    while (curr != NULL) {
        if (curr->last_char != last_char || curr->last_run != last_run || curr->count_num != count_num) {
            curr = curr->next;
            continue;
        }
        int match = 1;
        for (int i = 0; i < count_num; i++) {
            if (curr->counts[i].c != counts[i].c || curr->counts[i].count != counts[i].count) {
                match = 0;
                break;
            }
        }
        if (match) {
            return curr->perm_count;
        }
        curr = curr->next;
    }
    return -1;
}

// 将状态存入缓存
void add_to_cache(char last_char, int last_run, CharCount* counts, int count_num, long long perm_count) {
    CacheNode* node = (CacheNode*)malloc(sizeof(CacheNode));
    node->last_char = last_char;
    node->last_run = last_run;
    node->count_num = count_num;
    node->perm_count = perm_count;
    memcpy(node->counts, counts, sizeof(CharCount) * count_num);
    node->next = cache;
    cache = node;
}

// 递归计算当前状态下的合法排列总数
long long calc_valid_perms(CharCount* counts, int count_num, char last_char, int last_run, uint8_t max_repeat) {
    // 检查缓存
    long long cached_val = check_cache(last_char, last_run, counts, count_num);
    if (cached_val != -1) {
        return cached_val;
    }

    // 终止条件：所有字符已用完
    int all_zero = 1;
    for (int i = 0; i < count_num; i++) {
        if (counts[i].count > 0) {
            all_zero = 0;
            break;
        }
    }
    if (all_zero) {
        add_to_cache(last_char, last_run, counts, count_num, 1);
        return 1;
    }

    long long total = 0;
    for (int i = 0; i < count_num; i++) {
        if (counts[i].count == 0) continue;
        char c = counts[i].c;
        // 检查是否允许选择该字符
        if (c == last_char && (last_run + 1) > max_repeat) {
            continue;
        }

        // 临时修改计数，递归计算子问题
        counts[i].count--;
        int new_run = (c == last_char) ? (last_run + 1) : 1;
        long long sub_perm = calc_valid_perms(counts, count_num, c, new_run, max_repeat);
        total += sub_perm;
        // 恢复计数
        counts[i].count++;
    }

    add_to_cache(last_char, last_run, counts, count_num, total);
    return total;
}

3. 核心洗牌函数实现

// 生成大范围随机数（解决rand()范围不足问题）
long long generate_large_rand(long long max) {
    long long result = 0;
    long long range = (long long)RAND_MAX + 1;
    while (max > 0) {
        result = (result * range) + rand();
        max /= range;
    }
    return result % ((long long)RAND_MAX + 1);
}

void CRLimitedShuffle(char* Str, uint8_t MaxConsecutiveRepetition) {
    int len = strlen(Str);
    if (len <= 1) {
        return;
    }

    // 统计字符计数
    CharCount counts[256];
    int count_num = count_chars(Str, counts);

    char result[len + 1];
    result[len] = '\0';
    char last_char = '\0';
    int last_run = 0;

    // 清空缓存
    while (cache != NULL) {
        CacheNode* temp = cache;
        cache = cache->next;
        free(temp);
    }

    for (int i = 0; i < len; i++) {
        // 收集所有可选字符及其权重
        typedef struct {
            int idx;
            long long weight;
        } Option;
        Option options[256];
        int option_num = 0;
        long long total_weight = 0;

        for (int j = 0; j < count_num; j++) {
            if (counts[j].count == 0) continue;
            char c = counts[j].c;
            if (c == last_char && (last_run + 1) > MaxConsecutiveRepetition) {
                continue;
            }

            // 计算当前字符的权重
            counts[j].count--;
            int new_run = (c == last_char) ? (last_run + 1) : 1;
            long long weight = calc_valid_perms(counts, count_num, c, new_run, MaxConsecutiveRepetition);
            counts[j].count++;

            options[option_num].idx = j;
            options[option_num].weight = weight;
            total_weight += weight;
            option_num++;
        }

        // 加权随机选择字符
        long long rand_val = generate_large_rand(total_weight - 1);
        long long current_sum = 0;
        int selected_idx = -1;
        for (int j = 0; j < option_num; j++) {
            current_sum += options[j].weight;
            if (rand_val < current_sum) {
                selected_idx = options[j].idx;
                break;
            }
        }

        // 更新状态
        char selected_c = counts[selected_idx].c;
        result[i] = selected_c;
        counts[selected_idx].count--;
        if (selected_c == last_char) {
            last_run++;
        } else {
            last_char = selected_c;
            last_run = 1;
        }
    }

    // 将结果复制回原字符串
    strcpy(Str, result);
}

关键注意事项 #

• 随机数生成：示例中generate_large_rand解决了rand()范围不足的问题，避免当总权重超过RAND_MAX时的概率偏差。
• 缓存优化：示例中的缓存是简易链表实现，实际应用中可替换为更高效的哈希表（比如基于状态的哈希值），大幅提升重复状态的查询速度。
• 字符集兼容：当前实现针对ASCII字符，若需支持宽字符，只需调整计数和缓存的字符存储逻辑。
• 性能表现：对于字符种类较少的字符串，缓存能有效减少重复计算，性能远优于朴素重洗法；即使字符串较长，只要合法排列数存在，算法就能高效运行。

内容的提问来源于stack exchange，提问作者埃博拉酱