实现x次迭代内无重复的伪随机集合元素选择算法

问题背景 #

给定数组形式的集合（比如 [A, B, C, D, E, F]），需要实现一个伪随机选择函数，要求：

• 任意元素不会在连续minspacing次迭代内重复选中（比如minspacing=3时，F,C,B,D,F,E,A,B...是合法序列，F,C,D,C...不合法）
• 选择结果要尽可能随机，不能只是简单打乱数组后依次选取
• 理想状态下无需记录全部历史选取记录，函数结构限定为 function pick(options, minspacing, iteration) {...}

解决方案 #

核心思路 #

我们可以通过维护一个固定长度的循环缓冲区来记录最近minspacing次选中的元素，每次选择时先从候选池中排除这些元素，再做随机选择。如果希望完全不维护状态，也可以基于iteration参数结合伪随机数生成器，通过数学计算避开近期选中的元素（后者随机性稍弱，但无需额外存储）。

实现方案一：带循环缓冲区的随机选择（推荐，随机性更好） #

这种方案需要维护一个长度不超过minspacing的缓冲区，用来存储最近选中的元素，确保每次选择时不会重复选中这些元素。

// 用闭包维护缓冲区，避免全局变量污染
const createPicker = () => {
  const recentPicks = [];
  
  return function pick(options, minspacing, iteration) {
    // 过滤出候选元素：排除最近minspacing次选中的
    const candidates = options.filter(item => !recentPicks.includes(item));
    
    // 极端情况处理：当候选池为空（仅当options长度<=minspacing时可能发生）
    if (candidates.length === 0) {
      return options[Math.floor(Math.random() * options.length)];
    }
    
    // 用iteration作为种子生成确定性伪随机索引（也可以用系统随机数，去掉seed相关逻辑）
    const seed = iteration;
    const randomIndex = (seed * 1103515245 + 12345) % candidates.length;
    const selected = candidates[randomIndex];
    
    // 更新缓冲区：超过minspacing长度时移除最早的元素
    recentPicks.push(selected);
    if (recentPicks.length > minspacing) {
      recentPicks.shift();
    }
    
    return selected;
  };
};

// 使用示例
const pick = createPicker();
pick(['A','B','C','D','E','F'], 3, 1); // 第一次迭代的选择

实现方案二：无状态数学映射（无需维护历史） #

如果完全不想维护任何状态，可以基于iteration和伪随机数生成器，通过计算确保元素的选中间隔至少为minspacing+1，同时加入随机扰动提升随机性。

function pick(options, minspacing, iteration) {
  const total = options.length;
  // 确保基础间隔满足minspacing要求
  const baseStep = minspacing + 1;
  const baseIndex = Math.floor(iteration / baseStep) * baseStep;
  
  // 生成随机扰动，范围控制在不会触发重复的区间内
  const seed = iteration;
  const offset = (seed * 1103515245 + 12345) % (total - minspacing);
  
  // 计算最终索引
  const finalIndex = (baseIndex + offset) % total;
  return options[finalIndex];
}

合法性说明 #

以minspacing=3、options=[A,B,C,D,E,F]为例：

• 迭代1：候选池为全部元素，随机选中F，缓冲区变为[F]
• 迭代2：候选池排除F，随机选中C，缓冲区变为[F,C]
• 迭代3：候选池排除F、C，随机选中B，缓冲区变为[F,C,B]
• 迭代4：候选池排除F、C、B，随机选中D，缓冲区变为[C,B,D]
• 迭代5：候选池排除C、B、D，随机选中F，缓冲区变为[B,D,F]
• 后续迭代都会遵循相同规则，不会出现3次内重复选中的情况，完全符合要求。

内容的提问来源于stack exchange，提问作者Steve Bennett