高效随机选取多个不重叠等长子序列的算法教程-Python教程-PHP中文网

高效随机选取多个不重叠等长子序列的算法教程

本文介绍一种时间与空间复杂度均优、且能保证均匀随机性的算法，用于从给定序列中无偏地选取 m 个长度为 n 的互不重叠连续子序列。

本文介绍一种时间与空间复杂度均优、且能保证均匀随机性的算法，用于从给定序列中无偏地选取 m 个长度为 n 的互不重叠连续子序列。

在序列分析、数据采样、测试用例生成等场景中，常需从一个原始序列中随机抽取若干固定长度、彼此不重叠、位置连续的子序列（如滑动窗口式抽样），同时要求所有合法解具有完全相等的被选概率——即满足均匀随机性（uniform randomness）。朴素的贪心逐次采样法（如先随机选一个子序列、再在剩余片段中递归选取）会因“早期选择破坏后续可行性”而引入偏差，甚至导致失败（尤其当 N 较大时）；而暴力枚举所有可行解再随机选取则在时间和空间上不可行（组合爆炸）。

所幸，存在一个简洁、高效且数学严谨的解决方案：将问题转化为“带间隔约束的起始位置采样”问题。

核心思想：压缩采样空间 + 偏移校正

假设原始序列为 seq，长度为 L = len(seq)，需选出 M 个长度为 N 的不重叠子序列。每个子序列由其起始索引 start_i 唯一确定，且必须满足：

0 ≤ start_i ≤ L − N
子序列区间 [start_i, start_i + N) 两两不交 → 等价于 start_{i+1} ≥ start_i + N

关键洞察是：若将 M 个长度为 N 的块“紧贴放置”，它们至少占据 M × N 个位置；而实际序列有 L 个位置，因此剩余 L − M×N 个“空闲位置”可自由分配为 M+1 段间隙（首段前、块间 M−1 段、末段后）。这些间隙长度均为非负整数，总和为 L − M×N。

但更巧妙的建模方式是：对起始位置做线性变换，消除重叠约束。
考虑理想情况 N = 1：只需从 [0, L) 中无放回随机选 M 个索引，共 C(L, M) 种等可能方案。
当 N > 1 时，为确保第 i 个块不侵入第 i+1 个块，我们强制在每两个相邻块之间预留至少 N−1 个“缓冲位”。于是，若将 M 个起始位置记为 s₀ ，定义新变量：

d_i = s_i − i × (N − 1)

则约束 s_{i+1} ≥ s_i + N 等价于 d_{i+1} > d_i（严格递增），且 d_i ∈ [0, L − M×N + M)。
因此，只需从大小为 L − M×N + M 的整数集中均匀随机选取 M 个不同元素作为 d_i，再按 s_i = d_i + i×(N−1) 还原即可。

该方法时间复杂度为 O(M log M)（排序 d_i），空间复杂度 O(M)，远优于暴力法的指数级开销，且天然保证均匀性。

Python 实现与验证

以下是完整、可运行的实现：

import random

def sample_nonoverlapping_subsequences(seq, M, N):
    L = len(seq)
    if M * N > L:
        raise ValueError(f"Cannot select {M} non-overlapping subsequences of length {N} from sequence of length {L}")

    # Step 1: Sample M distinct dividers from [0, L - M*N + M)
    # This represents the "compressed" start positions
    dividers = sorted(random.sample(range(L - M * N + M), M))

    # Step 2: Recover actual start indices with offset correction
    starts = [d + i * (N - 1) for i, d in enumerate(dividers)]

    # Step 3: Extract subsequences
    return [seq[start : start + N] for start in starts]

# Example usage
seq = list(range(1, 17))  # [1, 2, ..., 16]
M, N = 3, 3
samples = sample_nonoverlapping_subsequences(seq, M, N)
print(samples)
# e.g., [[2, 3, 4], [7, 8, 9], [12, 13, 14]]

✅ 正确性保障：