如何生成无历史重复、单月用户不复用的唯一ID配对？

问题根因 #

你现有实现的核心缺陷在于：

• 两层嵌套循环生成配对时的贪心选择逻辑，会优先匹配靠前的ID，很容易把剩下的ID堵成无法配对的组合
• filterPairs 是无回溯的贪心过滤，前面选的配对会直接占用ID，不会考虑是否会导致剩余ID没有合法配对可选，自然就会出现你遇到的遗漏用户的情况

最优方案：圆桌轮转配对算法 #

这个算法是这类定期不重复配对场景的标准解法，天生满足你的所有需求：

1. 自动保证每次生成的都是覆盖所有用户的完美配对，不会有遗漏
2. 自动不会生成历史重复的配对（正序逆序都算的场景下只要统一把配对存成小ID-大ID的格式就行，不用判断正反）
3. 适配扩容场景，新增用户后只要调整轮转基数即可
4. 时间复杂度比你现在的O(n²)两层循环更优，大数据量下也不会卡

调整后的代码实现 #

// 工具方法：统一格式化配对为小ID在前的格式，避免正反重复判断
private formatPair(id1: number, id2: number): string {
  return id1 < id2 ? `${id1}-${id2}` : `${id2}-${id1}`;
}

private generateMonthlyPairs(userIds: number[], existedPartnerList: string[]): string[] {
  // 先打乱用户顺序，避免每次配对顺序固定
  const shuffledUsers = [...userIds].sort(() => Math.random() - 0.5);
  const existedSet = new Set(existedPartnerList);

  // 特殊处理：如果只有2个用户直接返回
  if (shuffledUsers.length === 2) {
    const pair = this.formatPair(shuffledUsers[0], shuffledUsers[1]);
    return existedSet.has(pair) ? [] : [pair];
  }

  // 固定第一个用户，剩下的用户轮转
  const fixed = shuffledUsers[0];
  const rotateList = shuffledUsers.slice(1);
  const n = rotateList.length;

  // 尝试所有轮转偏移量，直到找到能生成完美匹配的偏移
  for (let offset = 0; offset < n; offset++) {
    const tempUsed = new Set<number>([fixed]);
    const tempResult: string[] = [];
    let valid = true;

    // 尝试当前偏移的配对
    const firstPair = this.formatPair(fixed, rotateList[offset]);
    if (existedSet.has(firstPair)) continue;
    tempResult.push(firstPair);
    tempUsed.add(rotateList[offset]);

    // 配对剩下的用户：第i个和第n-1-i个配对
    for (let i = 0; i < n / 2; i++) {
      if (i === offset || tempUsed.has(rotateList[i])) continue;
      const j = n - 1 - i;
      if (tempUsed.has(rotateList[j])) continue;

      const pair = this.formatPair(rotateList[i], rotateList[j]);
      if (existedSet.has(pair)) {
        valid = false;
        break;
      }

      tempResult.push(pair);
      tempUsed.add(rotateList[i]);
      tempUsed.add(rotateList[j]);
    }

    // 如果当前偏移生成了完美匹配，直接返回
    if (valid && tempResult.length === userIds.length / 2) {
      return tempResult;
    }
  }

  // 所有轮转都试了还是没找到的话，用回溯法兜底（仅当剩余可配对组合极少时触发）
  return this.backtrackFindPairs([...userIds], existedSet);
}

// 兜底回溯方法，保证一定能找到完美匹配（只要还有可用配对）
private backtrackFindPairs(remainingUsers: number[], existedSet: Set<string>): string[] | null {
  if (remainingUsers.length === 0) return [];

  const first = remainingUsers[0];
  for (let i = 1; i < remainingUsers.length; i++) {
    const pair = this.formatPair(first, remainingUsers[i]);
    if (existedSet.has(pair)) continue;

    const newRemaining = remainingUsers.filter((_, idx) => idx !== 0 && idx !== i);
    const subResult = this.backtrackFindPairs(newRemaining, existedSet);
    if (subResult !== null) {
      return [pair, ...subResult];
    }
  }

  return null;
}

额外优化点 #

• 用Set替代数组做存在性判断，时间复杂度从O(n)降到O(1)，用户量大的时候性能提升非常明显
• 统一把配对存为小ID在前的格式，不用再判断正序逆序两种情况，减少一半的判断逻辑
• 优先用高效的轮转算法，只有极端场景才触发兜底回溯，兼顾性能和正确性
• 新增用户的时候不需要调整原有逻辑，直接把新用户加入userIds数组即可，算法会自动适配

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