时间戳

首页 > 解决方案 > 生成唯一的 id 对

javascript - 生成唯一的 id 对

问题描述

我正在尝试生成所有可能的唯一 ID 对。目前我正在尝试用两个这样的方法来实现它：

private prepareNewList(userIds: number[], existedPartnerList: string[]) {
    const newPartnerList = [];
    let usedUsersIds = [];

    for (let i = 0; i < userIds.length - 1; i++) {
      for (let j = i + 1; j < userIds.length; j++) {
        if (usedUsersIds.includes(userIds[i])) {
          continue;
        }

        const pair = ${userIds[i]}-${userIds[j]};
        const reversedPair = ${userIds[j]}-${userIds[i]};

        if (
          !existedPartnerList.includes(pair) &&
          !existedPartnerList.includes(reversedPair)
        ) {
          newPartnerList.push(pair);
          usedUsersIds.push(userIds[i], userIds[j]);

          break;
        }
      }
    }

    usedUsersIds = [];

    for (let i = userIds.length - 1; i > 0; i--) {
      for (let j = i - 1; j >= 0; j--) {
        if (usedUsersIds.includes(userIds[j])) {
          continue;
        }

        const pair = ${userIds[i]}-${userIds[j]};
        const reversedPair = ${userIds[j]}-${userIds[i]};

        if (
          !existedPartnerList.includes(pair) &&
          !existedPartnerList.includes(reversedPair) &&
          !newPartnerList.includes(pair) &&
          !newPartnerList.includes(reversedPair)
        ) {
          newPartnerList.push(pair);
          usedUsersIds.push(userIds[i], userIds[j]);

          break;
        }
      }
    }

    return this.filterPairs(newPartnerList);
  }

private filterPairs(pairs: string[]): string[] {
    const usedIds = [];
    const pairsToRemove = [];
    pairs = pairs.sort(() => Math.random() - 0.5);

    for (let i = 0; i < pairs.length; i++) {
      const parsedPair = pairs[i].split('-');

      if (parsedPair.some((id) => usedIds.includes(id))) {
        pairsToRemove.push(pairs[i]);
      }

      usedIds.push(...parsedPair);
    }

    return pairs.filter((item) => !pairsToRemove.includes(item));
  }

但它不能正常工作。当我第一次运行脚本时，我['1-2', '3-4', '5-6', '6-4', '5-3', '4-2', '3-1']从第一种方法和[ '1-2', '3-4', '5-6' ]过滤后得到，这是正确的（因为，例如，来自 '6-4' 对的数字已经用于 '3-4' 和 '5-6 ）。

当我第二次运行脚本时，我[ '1-3', '2-3', '4-5', '6-4', '5-3', '4-2' ]从第一种方法和 [ '1-3', '4-5' ]过滤后得到，这是不正确的，因为剩下一对[ '6-2' ]或[ '2-6' ].

所以我的方法没有按我的预期工作。我应该怎么做才能让它工作？

编辑1：

我想每个月运行这个脚本来生成唯一的用户对。例如，在本月，我创建了对“用户 1-用户 2”。所以在这个月我不能再使用用户 1 和用户 2，也不能永远使用对“用户 1-用户 2”

编辑2：

也许我解释不正确或不太准确。每个月我都必须生成唯一的用户对。比如我有6个用户（总是偶数），第一次启动我可以随意生成，因为数据库中的表是空的。例如：1-2、3-4、5-6。下个月我再次运行脚本，假设用户数量没有改变，现有的对（1-2、3-4、5-6）取自基础，我必须基于这些现有的对创建不会重复的新的（例如 1-4、2-6、3-5）。因此每个月都会增加 + 用户，相应地，收益也会增加。

标签： javascript

解决方案

取2（不重复使用）

如果我正确理解了更新的要求，那么像这样的递归函数呢？

function generatePairs(ids) {
  const uniqueIds = Array.from(new Set(ids));
  const results = [];
  function generateNext(idBag, pairs = []) {
    const [a, ...rest] = idBag;
    rest.forEach((b) => {
      const newPairs = [...pairs, [a, b]];
      const next = rest.filter((e) => e !== b);
      if (next.length >= 2) {
        generateNext(next, newPairs);
      } else {
        results.push({ pairs: newPairs, rest: next });
      }
    });
  }
  generateNext(uniqueIds);
  return results;
}

对于偶数个用户，例如

generatePairs(["John", "Mary", "Anne", "Zalgo", "Kenny", "Ben"]).forEach((result) => {
  console.log(result.pairs, result.rest);
});

结果是

[ [ 'John', 'Mary' ], [ 'Anne', 'Zalgo' ], [ 'Kenny', 'Ben' ] ] []
[ [ 'John', 'Mary' ], [ 'Anne', 'Kenny' ], [ 'Zalgo', 'Ben' ] ] []
[ [ 'John', 'Mary' ], [ 'Anne', 'Ben' ], [ 'Zalgo', 'Kenny' ] ] []
[ [ 'John', 'Anne' ], [ 'Mary', 'Zalgo' ], [ 'Kenny', 'Ben' ] ] []
[ [ 'John', 'Anne' ], [ 'Mary', 'Kenny' ], [ 'Zalgo', 'Ben' ] ] []
[ [ 'John', 'Anne' ], [ 'Mary', 'Ben' ], [ 'Zalgo', 'Kenny' ] ] []
[ [ 'John', 'Zalgo' ], [ 'Mary', 'Anne' ], [ 'Kenny', 'Ben' ] ] []
[ [ 'John', 'Zalgo' ], [ 'Mary', 'Kenny' ], [ 'Anne', 'Ben' ] ] []
[ [ 'John', 'Zalgo' ], [ 'Mary', 'Ben' ], [ 'Anne', 'Kenny' ] ] []
[ [ 'John', 'Kenny' ], [ 'Mary', 'Anne' ], [ 'Zalgo', 'Ben' ] ] []
[ [ 'John', 'Kenny' ], [ 'Mary', 'Zalgo' ], [ 'Anne', 'Ben' ] ] []
[ [ 'John', 'Kenny' ], [ 'Mary', 'Ben' ], [ 'Anne', 'Zalgo' ] ] []
[ [ 'John', 'Ben' ], [ 'Mary', 'Anne' ], [ 'Zalgo', 'Kenny' ] ] []
[ [ 'John', 'Ben' ], [ 'Mary', 'Zalgo' ], [ 'Anne', 'Kenny' ] ] []
[ [ 'John', 'Ben' ], [ 'Mary', 'Kenny' ], [ 'Anne', 'Zalgo' ] ] []

对于奇数（我们无法将所有人配对），未配对的进入rest：

# ["John", "Mary", "Anne", "Zalgo", "Kenny"]

[ [ 'John', 'Mary' ], [ 'Anne', 'Zalgo' ] ] [ 'Kenny' ]
[ [ 'John', 'Mary' ], [ 'Anne', 'Kenny' ] ] [ 'Zalgo' ]
[ [ 'John', 'Anne' ], [ 'Mary', 'Zalgo' ] ] [ 'Kenny' ]
[ [ 'John', 'Anne' ], [ 'Mary', 'Kenny' ] ] [ 'Zalgo' ]
[ [ 'John', 'Zalgo' ], [ 'Mary', 'Anne' ] ] [ 'Kenny' ]
[ [ 'John', 'Zalgo' ], [ 'Mary', 'Kenny' ] ] [ 'Anne' ]
[ [ 'John', 'Kenny' ], [ 'Mary', 'Anne' ] ] [ 'Zalgo' ]
[ [ 'John', 'Kenny' ], [ 'Mary', 'Zalgo' ] ] [ 'Anne' ]

取 1 个（所有对，可重复使用）

这样的事情不会做吗？需要特别注意确保输入没有重复并对结果进行排序......

function generatePairs(ids) {
  const uniqueIds = Array.from(new Set(ids));
  const outSet = new Set();
  for (let i = 0; i < uniqueIds.length; i++) {
    for (let j = i + 1; j < uniqueIds.length; j++) {
      outSet.add(`${uniqueIds[i]}-${uniqueIds[j]}`);
    }
  }
  const out = Array.from(outSet);
  out.sort();
  return out;
}


console.log(generatePairs([1, 1, 2, 3, 4, 5, 5, 6]));

输出是

[
  '1-2', '1-3', '1-4',
  '1-5', '1-6', '2-3',
  '2-4', '2-5', '2-6',
  '3-4', '3-5', '3-6',
  '4-5', '4-6', '5-6'
]

推荐阅读