Pairing numbers, must make pairs one at a time and can not be paired with self or group member

I have an algorithm issue here and I have no clue where to even begin. I have an array with 8 numbers, 1-8

arr = [1, 2, 3, 4, 5, 6, 7, 8]

each number in the array is part of a group

1 & 2 - group a
3 & 4 - group b
5 & 6 - group c
7 & 8 - group d

What I need to do is match each number in my array, with another number from the same array, but they can not be in the same group

• 1 & 2 may not be matched with 1 or 2
• 3 & 4 may not be matched with 3 or 4
• 5 & 6 may not be matched with 5 or 6
• 7 & 8 may not be matched with 7 or 8

Conditions

1. May not be predetermined
2. no repeats, example ... 2 and 4 can not both be paired with 8
3. They must be paired one at a time
4. Choices cannot be reset or undone, they are permanent

My problem is that if you pick it in just the right order, you can get stuck on the last number where the only pairing left would be to pair with itself example...

6 with 8
7 with 6
5 with 7
3 with 5
8 with 4
2 with 3
4 with 2
1 with _

This order leaves 1 with no option but itself.

What can I do to make it so no matter what the last number always has a viable pairing? Is this even possible?

I am open to the possibility of having to force 1 or 2 pairings when there are only 4 candidates left to pair if this is my only option.

The languages I am using are javascript / PostgreSQL if that matters.

Here is my current code. It returns an array called available. One number is chosen from the array available at random, and that number is then paired. The pairings MUST be able to remain independent of each other. At any point in time, I need to be able to make a single new pairing while leaving all other pairings untouched. I need the array available to not only return pairings that are available but also be sure that I am not left with a remainder at the end which cannot be paired.

 function selectGiftee(req, res, db){
        const {user_id, group_id} = req.body
        db.select('name', 'user_id', 'giftee_id', 'group_id').from('users')
        .then (data => {
            if (data.length) {
    // only sending available giftees

                const taken = [];
                const fullList = [];
                let available = [];

    // figure out which giftees are taken
                data.forEach( user => {
                    if (user.giftee_id !== null){
                        taken.push(user.giftee_id)
                    }
                    if (user.group_id === group_id) {
                        taken.push(user.user_id)
                    }
                })
    // add all giftees to a list
                data.forEach( user => {
                    fullList.push(user.user_id)
                })

    // only add available giftees to the available list
                available = fullList.filter(val => !taken.includes(val));

    // respond with only giftees that are not taken
                res.json(available)

from Pairing numbers, must make pairs one at a time and can not be paired with self or group member