寻求等概率选取给定序列中M个不重叠且长度为N的子序列的高效算法

假设我们有一个输入序列，比如：

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]

现在需要随机、等概率地选出M个不重叠、长度均为N的子序列。举个例子，如果要选3个长度为3的子序列，一个合法解可能是：

[3, 4, 5]
[8, 9, 10]
[11, 12, 13]

注意子序列的顺序不影响解的判定，而且所有合法解都要有相同的被选中概率。

我尝试过的算法及其问题 #

我之前试过一种分步随机选取的方法，步骤如下：

• 先随机选第一个子序列，比如[11, 12, 13]
• 此时原序列被分成了两段可用的剩余序列：[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]和[14, 15, 16]
• 再从剩余的可用序列里随机选第二个子序列，比如[3, 4, 5]
• 这时剩下的足够容纳长度N的可用序列是[6, 7, 8, 9, 10]和[14, 15, 16]
• 最后从中选出第三个子序列[8, 9, 10]

但这个方法有个致命缺陷：当子序列长度N较大时，很可能中途就没法选出足够的子序列了。比如如果要选3个长度为5的子序列，明明存在合法解，但如果第一次随机选了[3, 4, 5, 6, 7]，剩下的序列就没法再选出两个长度为5的子序列了，算法直接失败。

当然我知道暴力解法：先枚举所有合法的解，再随机选一个。但这种方法太耗时间和空间了，有没有更“聪明”的高效算法？

高效且等概率的解决方案 #

这里有个巧妙的思路，能保证等概率且不会出现中途失败的情况，核心是把问题转化为选取合法的起始位置组合：

1. 先明确合法起始位置的约束：
   假设原序列长度为L，我们需要选M个起始索引s_1 < s_2 < ... < s_M（以0-based索引举例），必须满足两个条件：

   • 每个子序列不超出原序列范围：s_i + N - 1 < L
   • 子序列之间完全不重叠：s_{i+1} >= s_i + N

2. 转化问题简化选取逻辑：
   我们可以把每个选中的子序列“压缩”，去掉它们之间的强制间隔。令t_i = s_i - (i-1)*(N-1)，此时t_i的取值范围会简化为0 <= t_1 < t_2 < ... < t_M <= L - M*N（推导过程：由s_M + N -1 <= L-1，代入s_M = t_M + (M-1)*(N-1)，可得t_M <= L - M*N）。
   现在问题就变成了：从[0, 1, ..., L - M*N]这个范围内随机等概率选取M个不同的整数——这是一个标准的组合抽样问题，有成熟的高效实现方式。

3. 还原为原序列的子序列：
   选好t_1 < t_2 < ... < t_M后，再还原出对应的起始位置：s_i = t_i + (i-1)*(N-1)。这样得到的s_i必然满足所有约束，不会出现重叠或超出序列的情况。

举个实际例子：原序列长度L=16，要选M=3个长度N=5的子序列：

• 计算得L - M*N = 16 - 3*5 = 1，所以t_i的可选范围是[0,1]？不对，换1-based索引更直观：此时t_i的可选范围是1~16-3*5+3=4，从1-4中选3个不同的数，比如选1,2,4，还原出s_1=1，s_2=2+4=6，s_3=4+8=12，对应的子序列就是[1-5]、[6-10]、[12-16]，完全符合要求。

这个方法的核心优势：

• 不会出现中途失败的情况，因为我们从一开始就保证了选取的起始位置必然满足所有约束
• 严格等概率：每个合法的子序列组合对应唯一的t组合，而选取t组合是等概率的，所以最终的子序列解也是等概率的
• 时间空间效率极高：只需要做一次组合抽样，不需要枚举所有解，抽样可以用Fisher-Yates洗牌的变种高效完成，时间复杂度O(M)，空间复杂度O(M)（仅需存储选中的t值）

备注：内容来源于stack exchange，提问作者Jeyekomon