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

如何高效随机选取多个不重叠等长子序列

本文介绍一种时间与空间复杂度均为 o(m) 的算法，用于从给定序列中均匀随机选取 m 个长度为 n 的互不重叠连续子序列，确保所有合法解等概率出现。

本文介绍一种时间与空间复杂度均为 o(m) 的算法，用于从给定序列中均匀随机选取 m 个长度为 n 的互不重叠连续子序列，确保所有合法解等概率出现。

在序列分析、数据采样或强化学习中的 episode 切分等场景中，常需从一维有序序列中抽取若干不重叠、等长、连续的子序列（subsequences），且要求抽样过程完全均匀随机——即每个合法解出现的概率严格相等。朴素的贪心随机选择（如逐个挑选、剔除已占位置）会因依赖顺序导致概率偏差，尤其在序列较满时易失败；而枚举全部解再随机选取则面临组合爆炸，不可扩展。

核心思想在于：将“选 M 个长度为 N 的不重叠子序列”转化为“选 M 个起始位置”，并保证它们之间至少间隔 N（避免重叠）。关键洞察是——若将每个子序列“压缩”为其首元素，并预留其后 N−1 个位置作为专属延伸区，则 M 个起始位置实际只需满足两两间距 ≥ N，等价于在收缩后的搜索空间中无约束地随机选取 M 个互异位置。

具体实现步骤如下：

计算有效起始范围：原序列长度为 L = len(seq)，M 个子序列共占 M × N 个位置。为保证能放下 M 个长度为 N 的块且互不重叠，最后一个子序列的起始索引最大可取 L − N；但更紧的约束来自“预留间隙”视角：若将每个子序列视作占据 1 个“槽位” + 后续 N−1 个强制占用位，则 M 个槽位共需 M + M×(N−1) = M×N 位置，而总长度 L 中还需容纳 M−1 个间隔（但此间隔可为 0）。更简洁的推导是：将 M 个子序列的起始位置记为 s₀ ，约束为 sᵢ₊₁ ≥ sᵢ + N。令 tᵢ = sᵢ − i×(N−1)，则 t₀ 且 tᵢ ∈ [0, L − M×N + M) —— 即 tᵢ 是在大小为 L − M×N + M 的集合中无放回随机选取的 M 个升序索引。
采样与还原：
- 从 range(L − M×N + M) 中随机无放回抽取 M 个整数，排序得 dividers；
- 将 dividers[i] 映射回原始起始位置：start_i = dividers[i] + i × (N−1)；
- 提取子序列：seq[start_i : start_i + N]。

该方法时间复杂度为 O(M log M)（主要来自排序，但因 M 通常远小于 L，可视为 O(M)），空间复杂度 O(M)，且数学上可证其均匀性：dividers 的每种组合等概率，而映射 t → s 是双射，故所有合法起始位置元组等概率。

以下是完整可运行代码示例：

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}")

    # Effective range for choosing M 'divider' positions
    effective_len = L - M * N + M
    dividers = sorted(random.sample(range(effective_len), M))

    # Map dividers to actual start indices
    starts = [d + i * (N - 1) for i, d in enumerate(dividers)]

    # Extract subsequences
    return [seq[s : s + N] for s in starts]

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

注意事项：