Find unmatched unique pairs of an array from another array

user_4002842 0
Viewed 81

I have a list of users and I have also list of pairs of matched users. i-e

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

I want to find list of unique unmatched users. By unique, I mean user pair AB and BA will be considered as 1 pair.

Here is the solution I have came up with:

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)
}

This solutions gives the expected results, But its very expensive operation. Try running this code with 300 users and if alreadyMatched users gets bigger, it will become way more expensive.

How can I get this to be faster?

Thanks

recursion arrays javascript performance
3 Answers
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);

This algorithm ensures number of iterations == number of possible combinations.

user_115981800

This is how you can achieve that:

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);

user_49255480

Here is my take on this problem. I have replaced the matchedPairs from objects to arrays to simplify this.

 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);

user_57004590
Related