从另一个数组中查找不匹配的唯一数组对

Question

我有一个用户列表，还有一个匹配用户对的列表。i-e

const users = ["A", "B", "C", "D", "E", "F", "G"];
const alreadyMatchedUsers = [
{ user1: 'A', user2: 'B' },
{ user1: 'A', user2: 'C' },
]

我想查找唯一的不匹配用户列表。所谓唯一，我的意思是用户对AB和BA将被视为1对。

以下是我提出的解决方案：

const alreadyMatchedUsers = [
{ user1: 'A', user2: 'B' },
{ user1: 'A', user2: 'C' },
]
const unMatchedArrary = []
// const users = ['A', 'B', 'C', 'D']
const users = []
for (let i = 0; i < 300; i++) users.push(i)
const n = users.length
const uniquePossiblePairs = []
const uniquePossiblePairsCount = (n * (n - 1)) / 2
for (let i = 0; i < n - 1; i++) {
console.log('Main loop+++++++++++++++++', users[i])
for (let j = i; j < n - 1; j++) {
// uniquePossiblePairs.push({ user1: users[i], user2: users[j + 1] });
const alreadyMatched = alreadyMatchedUsers.some(
(mpair) => (users[i] === mpair.user1 || users[i] === mpair.user2)
&& (users[j + 1] === mpair.user1 || users[j + 1] === mpair.user2),
)
if (!alreadyMatched) {
unMatchedArrary.push({ user1: users[i], user2: users[j + 1] })
}
console.log('Already Matched, ', users[i], users[j + 1], alreadyMatched)
}
}
console.log('UNIQUE POSSIBLE PAIRS Count', uniquePossiblePairsCount)
console.log('UNIQUE POSSIBLE PAIRS', uniquePossiblePairs)
console.log('UNMATCHED ARRARY ', unMatchedArrary)
}

这种解决方案给出了预期的结果，但其操作非常昂贵。试着用300个用户运行这个代码，如果已经匹配的用户越来越大，它将变得更加昂贵。

我怎样才能更快？

感谢

Answer 1

const users = ["A", "B", "C", "D", "E", "F"];
const combinations = [];
while (users.length > 0) {
const lastUser = users[users.length-1]; // start at last user of users list.

// this loop gets all combinations involving the last user.
for (let user of users) {
if (user !== lastUser) {
combinations.push({"user1": user, "user2": lastUser});
}
}

// this gets rid of last user from the users list, as we have found all its combinations from this iteration of the while loop.
users.pop()
}
console.log(combinations);

该算法确保迭代次数==可能组合的次数。

Answer 2

这就是实现这一点的方法：

const users = ["A", "B", "C", "D", "E", "F", "G"];
const alreadyMatchedUsers = [
{ user1: 'A', user2: 'B' },
{ user1: 'A', user2: 'C' },
]

const pairs = alreadyMatchedUsers.map(x => `${x.user1}${x.user2},${x.user2}${x.user1}`);
let allPairs = [];
for (user of users) {
allPairs.push(...users.map(x => `${user}${x},${x}${user}`))
}
// filter allPairs
const uniquePairs = allPairs
.filter(pair => !pairs.includes(pair) && pair.split(',')[0] != pair.split(',')[1])
.map(pair => pair.split(',')[0].split('')); 
console.log('pairs: ', pairs);
console.log('allPairs: ', allPairs);
console.log('uniquePairs', uniquePairs);

Answer 3

以下是我对这个问题的看法。为了简化这一点，我已经将matchedPears从对象替换为数组。

const users = ["A", "B", "C", "D", "E", "F", "G"];
const alreadyMatchedUsers = [
["A", "B"],
["A", "C"],
];
const unmatchedPairs = [...alreadyMatchedUsers];
const unmatchedPairsFinal = [];
for (let i = 0; i < users.length; i++) {
users.forEach((user) => {
if (user !== users[i]) {
console.log("checking", user, " vs ", users[i]);
const alreadyDetected = unmatchedPairs.filter((userCheck) => {
return userCheck.includes(user) && userCheck.includes(users[i]);
});
console.log(alreadyDetected);
if (!alreadyDetected.length > 0) {
unmatchedPairs.push([user, users[i]]);
unmatchedPairsFinal.push([user, users[i]]);
}
}
});
}
console.log(unmatchedPairs);
console.log(unmatchedPairsFinal);