JS Secret Santa算法实现：满足双向互斥兼容奇偶人数的优化咨询

你要满足的两个约束用随机洗牌+单向循环分配的方案就能完美实现，时间复杂度仅为O(n)，没有多余的比较操作，是速度最快的实现方式。

方案逻辑 #

• 首先做边界校验：用户列表长度必须≥3，否则无法满足「双向互斥」约束（2个用户必然形成互送，1个用户无分配对象）
• 对用户列表执行 Fisher-Yates 随机洗牌，保证分配结果完全随机
• 每个用户的送礼对象固定为洗牌后列表中自己的下一位用户，最后一位用户的送礼对象为列表第一位用户，形成一个完整的单向长环
• 因为整个分配是长度为n(n≥3)的单向环，不存在长度为2的子环，自然就不会出现双向互送的情况，且奇偶长度的列表都能完美适配

完整可运行代码 #

// Fisher-Yates 洗牌算法，O(n)复杂度，保证公平随机
function shuffle(arr) {
  for (let i = arr.length - 1; i > 0; i--) {
    const j = Math.floor(Math.random() * (i + 1));
    [arr[i], arr[j]] = [arr[j], arr[i]];
  }
  return arr;
}

function generateSecretSanta(users) {
  // 边界校验
  if (users.length < 3) {
    throw new Error('用户数不能少于3，否则无法满足双向互斥约束');
  }
  // 洗牌避免固定顺序
  const shuffledUsers = shuffle([...users]);
  const result = [];
  const len = shuffledUsers.length;
  // 单向循环分配
  for (let i = 0; i < len; i++) {
    result.push({
      santaClaus: shuffledUsers[i],
      user: shuffledUsers[(i + 1) % len]
    })
  }
  return result;
}

// 测试用例
const names = ['a', 'b', 'c', 'd', 'e', 'f', 'g'];
console.log(generateSecretSanta(names));

原代码的问题 #

你初始写的代码存在两个明显缺陷：

• 每次调用filter删除元素的复杂度是O(n)，整体复杂度为O(n²)，用户量大的时候性能很差
• 只能处理偶数长度的列表，奇数长度会剩余1个用户无法分配，且无法避免双向互送的情况

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