Match users in pair array but avoid previous matches

Question

I shuffle and pair the user ids as you can see below.

/**
 * @see https://stackoverflow.com/a/12646864
 * @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;
};

/**
 * @see https://stackoverflow.com/a/44996257
 * @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;
};

After running getRandomUsers(), a method checks for non-pair (odd) elements. If any, notify the user and delete from matchmaking array.

The problem is: These matches will repeat in a certain time. But I don't want the same users to match again.

For example:

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

Answer 1

Consider the situation where you have an array of 4 user ids. The possible pairings of the user id at index 0 with other indices are: [0,1],[0,2],[0,3]. Once any of those pairs have been used, they cannot appear again in the same or in any other pairing permutation.

The key insight, therefore, is that if you have n users, you cannot have more than n-1 possible pairing permutations. E.g. if you have 4 users, there are only 4-1=3 pairing permutations: [1,2],[3,4], [1,3],[2,4], [1,4],[2,3].

As trincot pointed out, there is a Circle Method for finding all possible pairing permutations (e.g. all 3 possible pairing permutations when there are 4 users).

The first thing you need to do is pick a pairing permutation that you have not chosen before. If there are 3 possible permutations, you should shuffle the array [0,1,2] to get your random order of possible permutations.

E.g. if you randomly decide the order of pairing permutations you will use is [2,0,1], then the only thing you need to keep track of from then on is that array and how far into that array you've visited so far. You do not need to generate all possible pairing permutations up front or keep track of every single pairing you've ever used.

Then, you find each pairing permutation in that order, and it'll be obvious when you've used up all possible pairing permutations.

function* rotatedSequence(start, leftRotation, len) {
  for(let i=0; i<len; i++) yield start+(leftRotation+i)%len
}
function getPairingPermutation(n,i) {
  return pair([0,...rotatedSequence(1,i,n-1)])
}
function pair(a) {
  return a.slice(0,a.length/2).map((e,i,r)=>[e,a[r.length+i]])
}
function* shuffle(arr) {
  arr = [...arr];
  while(arr.length) yield arr.splice(Math.random()*arr.length|0, 1)[0]
}
function sequence(n) {
  return [...rotatedSequence(0,0,n)]
}
function shuffledSequence(n) {
  return [...shuffle(sequence(n))]
}

let users = sequence(6).map(i=>String(Math.random()).substring(2,6))

console.log('users:', users)

let possibleParingPermutations = users.length - 1

let seq = shuffledSequence(possibleParingPermutations)

console.log('pairing permutation sequence', seq)

for(let i of seq) {
  // map index pairs to ids in the users array
  // this will also shuffle the pairs within the permutation - this may not
  // be necessary depending on your situation
  let paringPermutation = [...shuffle(getPairingPermutation(users.length, i))]
    .map(j=>[...shuffle(j)].map(k=>users[k]))

  console.log(`permutation ${i}:`, 
    paringPermutation.map(j=>`[${j.join()}]`).join())
}

Answer 2

You could use the the scheduling algorithm for round robin, which takes the previous pairing and then rotates all of the users one "position" except the first one, like this (columns are pairings):

Here is a generator function that performs that rotation:

function* pairings(users) {
    for (let round = 1; round < users.length; round++) {
        yield Array.from({length: users.length / 2}, (_, i) => [users[i], users.at(-1-i)]);
        // Perform round-robin shift, keeping first player in its spot:
        users = [users[0], ...users.slice(2), users[1]];
    }
}

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

// Example run:
const userArray = [1, 2, 3, 4, 5, 6];

const shuffled = shuffleArray(userArray);
for (const pairs of pairings(shuffled)) {
    console.log("matchmaking:", JSON.stringify(pairs));
}

If you want to remove the pattern that emerges, then you could also shuffle the pairings:

function* pairings(users) {
    for (let round = 1; round < users.length; round++) {
        yield Array.from({length: users.length / 2}, (_, i) => [users[i], users.at(-1-i)]);
        // Perform round-robin shift, keeping first player in its spot:
        users = [users[0], ...users.slice(2), users[1]];
    }
}

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

// Example run:
const userArray = [1, 2, 3, 4, 5, 6];

const shuffled = shuffleArray(userArray);
for (const pairs of pairings(shuffled)) {
    shuffleArray(pairs);
    console.log("matchmaking:", JSON.stringify(pairs));
}