限制连续重复次数的等概率洗牌算法设计

大家好，这个问题最初来自Stack Overflow，我觉得它更需要数学层面的突破，所以把问题转到这里来讨论。另外我还发现了一个类似的问题，看起来是这个问题的特例。

先明确一下我的需求：我要对一个已知字符串进行洗牌，这个字符串里可以有任意数量的重复字符，但洗牌后的结果绝对不能出现同一个字符连续重复n次的情况。举个例子，比如原字符串是"aaaabbbcc"，n=2的话，"aabaabbcc"是符合要求的排列，但"aaabbbcca"就不行——因为里面有三个连续的a，超过了n=2的限制。

现在的核心问题是：怎么设计这样的洗牌算法，才能保证每一个符合要求的字符串都有相同的出现概率？

我先梳理了几个自己想到的思路，以及它们存在的问题：

• 暴力重试法：最直接的想法就是先随机洗牌，然后检查结果是否符合要求，如果不符合就重新洗牌。但这种方法在极端场景下性能会差到离谱。比如原字符串是"aaaabbbbbbbbbb"，n=2的时候，符合要求的排列数量极少（几乎只有交替排列的可能），这时候每次随机生成的结果几乎都是无效的，函数会一直循环，直到碰巧生成那个唯一的正确序列，概率极低，完全不实用。

• 生成所有有效排列再随机抽取：另一个思路是先枚举所有可能的排列，剔除不符合要求的，再从剩下的有效排列里随机选一个。但这个方法的复杂度是阶乘级的，很快排列数量就会超过64位无符号整数的上限，根本没法处理稍长一点的字符串。

• 修改Fisher-Yates洗牌算法：我还想到可以对经典的Fisher-Yates算法做数学上的调整：从随机选一个字符开始，每次选下一个字符的时候，根据前一个字符连续出现的次数乘以一个衰减系数来调整选中概率。比如如果前一个字符已经连续出现了n次，那衰减系数就设为0，确保下一个字符不能和它相同。但问题是，我不知道该怎么精确计算这个衰减系数，才能保证最终所有有效排列的出现概率都是相等的。

有没有大佬能帮忙指点一下？或者给点数学上的思路方向？

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