如何实现用户配对数组功能并避免重复匹配？

我实现了如下用户ID洗牌与配对功能：

/**
 * 洗牌数组
 * @param {string[]} array
 */
const shuffleArray = (array) => {
    for (let i = array.length - 1; i > 0; i--) {
        const j = Math.floor(Math.random() * (i + 1));
        [array[i], array[j]] = [array[j], array[i]];
    }

    return array;
};

/**
 * 将数组两两配对
 * @param {string[]} array
 */
const pairArray = (array) => {
    return array.reduce(function (result, value, index, array) {
        if (index % 2 === 0) result.push(array.slice(index, index + 2));
        return result;
    }, []);
};

const getRandomUsers = async () => {
    let userIDSet = [];
    const users = await svc.findAll({ enrolled: true });

    if (!Object.keys(users).length) {
        console.log("DAMN! There are no users enrolled yet. What a bummer!");
    }

    for (const user of users) {
        userIDSet.push(user.discordId);
    }

    const shuffledUserIDs = shuffleArray(userIDSet);
    const pairedUserIDs = pairArray(shuffledUserIDs);

    return pairedUserIDs;
};

运行getRandomUsers()后，会有额外方法检查并处理奇数个未配对用户（通知用户并将其从配对数组中移除）。

存在的问题 #

多次运行后会出现重复匹配的情况，希望避免同一组用户再次配对。示例如下：

const userArray = [1, 2, 3, 4, 5, 6];

const shuffleForFirst = shuffleArray(userArray);
const firstMatchmaking = pairArray(shuffleForFirst);
console.log("First Matchmaking:", firstMatchmaking);

const shuffleForSecond = shuffleArray(userArray);
const secondMatchmaking = pairArray(shuffleForSecond);
console.log("Second Matchmaking:", secondMatchmaking);

解决方案 #

核心思路是记录历史配对记录，生成新配对时检查是否与历史重复，直到生成无重复的配对结果。

1. 维护历史配对记录

用集合存储已出现的用户对（标准化格式，避免[A,B]和[B,A]被视为不同配对）：

// 存储历史配对的标准化键（如"1-2"）
const pairedHistory = new Set();

// 将配对转换为标准化键（排序后拼接，确保[A,B]和[B,A]是同一个键）
const getPairKey = (pair) => {
  return pair.sort().join('-');
};

2. 修改配对生成逻辑

添加重试机制，生成配对后检查是否重复，直到得到有效结果：

const getUniquePairedUsers = async () => {
  let userIDSet = [];
  const users = await svc.findAll({ enrolled: true });

  if (!users.length) {
    console.log("DAMN! There are no users enrolled yet. What a bummer!");
    return [];
  }

  for (const user of users) {
    userIDSet.push(user.discordId);
  }

  let validPairs = null;
  const maxRetries = 10; // 最大重试次数，防止无限循环
  let retryCount = 0;

  // 循环生成无重复的配对
  while (!validPairs && retryCount < maxRetries) {
    // 复制数组，避免修改原用户ID集合
    const shuffledUserIDs = shuffleArray([...userIDSet]);
    const pairedUserIDs = pairArray(shuffledUserIDs);
    
    // 检查当前配对是否有历史重复
    const hasDuplicate = pairedUserIDs.some(pair => {
      // 单个用户（奇数情况）跳过检查，后续会被移除
      if (pair.length !== 2) return false;
      const key = getPairKey(pair);
      return pairedHistory.has(key);
    });

    if (!hasDuplicate) {
      validPairs = pairedUserIDs;
      // 将新配对加入历史记录
      validPairs.forEach(pair => {
        if (pair.length === 2) {
          const key = getPairKey(pair);
          pairedHistory.add(key);
        }
      });
    } else {
      retryCount++;
    }
  }

  // 重试次数耗尽时的降级处理
  if (!validPairs) {
    console.log("无法生成无重复配对，将重置部分历史记录并生成新配对");
    // 清空一半历史记录，释放配对可能性
    const historyArray = Array.from(pairedHistory);
    pairedHistory.clear();
    historyArray.slice(Math.floor(historyArray.length / 2)).forEach(key => pairedHistory.add(key));
    
    // 重新生成配对并记录
    const shuffledUserIDs = shuffleArray([...userIDSet]);
    validPairs = pairArray(shuffledUserIDs);
    validPairs.forEach(pair => {
      if (pair.length === 2) {
        const key = getPairKey(pair);
        pairedHistory.add(key);
      }
    });
  }

  return validPairs;
};

注意事项

• 如果需要持久化历史记录，需将pairedHistory存储到数据库（如Redis、MongoDB），避免服务重启后丢失记录。
• 当用户池发生变化（新用户加入、老用户退出），可考虑清空部分历史记录，因为用户组合已改变，之前的重复限制可适当放宽。
• 最大重试次数可根据用户数量调整，用户越多可适当增加重试次数，或改用更高效的全组合筛选算法。

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