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

Question

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, given the same inputs, different solutions must be possible
2. no repeat pairings for example if 2 pairs with 8, 4 can not also pair with 8
3. They must be paired one at a time, with the ability to leave some pairings unfinished and come back at a later date to complete more pairings
4. Pairings cannot be reset or undone, once paired it is permanent
5. One pairing can not run both ways in all cases. For example, if 2 is paired to 3 then 3 can not always pair with 2. It is acceptable if this happens from time to time, but it can not be an intended feature.
6. We can not assume the pairings will be made in any specific order. For example, the first pairing may be made by 1, or maybe 7 or 3 and so on. Any number may need to be paired at any time.

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 or it's groupmate.

I want to stress a condition here because it keeps being overlooked in answers. I want pairings to be made one at a time. This means that you should be able to space making each pairing out as far as you want. I want to be able to make a pairing on day 0, and then I can come back day 1, week 2, or year 2750 to make the second pairing. This is necessary. Each and every single pairing must be made completely independent of each other, and at the end, the last number must be still able to make a valid pairing.

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?

update: I have added a fairly good solution in the answers section. If you are still struggling to understand what I want to accomplish try reading my answer in the answers section. The attached code is outdated since I have found a currently usable answer.

antiquated code below

 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)

Answer 1

Lets take our groups as one long list:

1 2|3 4|5 6

Now lets divide that in the middle, and move one part below the other one:

1 2|3
4|5 6

Now every element got a pair (each column) that is not from the group itself, you could turn it into a continous list by appending all the columns to one:

(1 -> 4) -> (2 -> 5) -> (3 -> 6) -> 

Now to get different combinations, we just shuffle the array of groups and the groups itself before.

// stolen from https://stackoverflow.com/questions/6274339/how-can-i-shuffle-an-array
function shuffle(a) {
    for (let i = a.length - 1; i > 0; i--) {
        const j = Math.floor(Math.random() * (i + 1));
        [a[i], a[j]] = [a[j], a[i]];
    }
    return a;
}


const groups = [[1, 2], [3, 4], [5, 6], [7, 8, 9]];

groups.forEach(shuffle);
shuffle(groups);

console.log("shuffled:", groups.join(" | "));

const list = [].concat(...groups);

console.log("list:", list);

// Now pair every element by matching the first and the second half:
const pairs = [];

for(let i = 0; i < Math.floor(list.length / 2); i++) {
  pairs.push([
   list[i],
   list[i + Math.floor(list.length / 2)]
  ]);
 }

 if(list.length % 2)
   pairs.push([list.pop()]);
 console.log("pairs:", pairs.join(" | "));

 const result = [].concat(...pairs);

 for(let i = 0; i < result.length; i++)
   console.log(result[i] + " -> " + result[(i + 1) % result.length]);

Answer 2

So here is the method I came up with to answer my own question. What I've done is to split the groups into two separate groups first. This means that group a and b are in metagroup 1 and group c and d are in metagroup 2.

second I have added in a weighting system. so when a pair is trying to be made i collect all the secondary numbers in the pairs that have already been taken and I add a weight to their group. for example, if 4 has been paired with 6 then group c gets +1 to their weight. This is only the first step of the weighting though.

Now, in the current example, 4 has already paired with 6, and therefore group c has a weight of 1. Now we want to pair 3. 3 is in the same group as 4, which is group b. So now group 3 will look at 4, and see that it has already got a pair, which is 6. 6 is part of metagroup 2, and so now both group c and d are given +10 to their weight. This leaves group c with 11, and d with 10.

Edit: these two conditions were added to clear up some less common errors I found. first I added a negative weight (-1) for any number that has not been paired yet. This makes it so that numbers without pairs are chosen before numbers with pairs. I had to do this because I was still on rare occasion getting stuck with one number that could not pair at the end. Second I changed the way numbers in the same group were handled. previously I simply removed them from the available list. This however caused an issue if their group had the lowest weight. The algorithm would suggest picking a number from that group because it's weight was lowest, but there were no numbers in the group so it resulted in a deadlock. Now i add 20 weight to the group a number is in so that it can never be the lowest weight.

So now we have our weights set and 3 is still trying to pair. we have a look at all our weights and see that group a and b have a 0 for their score and c has 11 and d has 10. 3 is part of group b and pairing with self is specifically blocked so that is not possible, so this leaves only group a to choose from, so 3 will pair with either 1 or 2.

this is the only method I was able to find that would allow me to form pairs 1 at a time on demand. Below is my code, it may be a bit confusing since I'm just pulling it straight out of a program, but if anyone needs clarificaion on how it works I'll be happy to explain.

function chooseGiftee(avail){
    const int = avail.length;
    const index = Math.floor((Math.random() * int) + 1);
    return avail[index-1];
}

function getCandidates(weights){
        return candidates;
}



function selectGiftee(req, res, db){
    const {user_id, spouse_id, group_id} = req.body;
    if (!user_id || !spouse_id || !group_id){
        return res.status(400).json('Missing Credentials')
    }

    db.select('user_id', 'spouse_id', 'giftee_id', 'group_id').from('users')
    .then (data => {

        if (data.length) {
// only sending available giftees


            let newGiftee;
            const taken = [];
            const fullList = [];
            let available = [];
            let filteredAvailable = [];
            let nullCount = 0;
            let nullArr = [];
            let a = 0;
            let b = 0;
            let c = 0;
            let d = 0;

//for the love of god man please refactor all this stuff!!!!!!!


// figure out which giftees are taken and set weight for already picked groups 
            data.forEach( user => {

                if (user.giftee_id === null){
                    switch (user.user_id){
                        case 1:
                        case 2:
                            a--;
                            break;
                        case 3:
                        case 4:
                            b--;
                            break;
                        case 5:
                        case 6:
                            c--; 
                            break;
                        case 7:
                        case 8:
                            d--;
                            break;
                    }
                }

                if (user.giftee_id !== null){
                    taken.push(user.giftee_id);
                }
                switch (user.giftee_id){
                        case 1:
                        case 2:
                            a++;
                            break;
                        case 3:
                        case 4:
                            b++;
                            break;
                        case 5:
                        case 6:
                            c++; 
                            break;
                        case 7:
                        case 8:
                            d++;
                            break;
                    }

                if (user.group_id === group_id) {
                    switch(user.giftee_id){
                        case 1:
                        case 2:
                        case 3:
                        case 4:
                            a += 10;
                            b += 10;
                            break;
                        case 5:
                        case 6:
                        case 7:
                        case 8:
                            c += 10;
                            d += 10;
                            break;
                    }
                    switch(user.group_id){
                        case 1:
                            a += 10;
                            break;
                        case 2:
                            b += 10;
                            break;
                        case 3:
                            c += 10;
                            break;
                        case 4:
                            d += 10;
                            break;
                    }
                }
            })


// add all giftees to a list
            data.forEach( user => {
                fullList.push(user.user_id)
            })

// only add available giftees to available list

            available = fullList.filter(val => !taken.includes(val));


// Choose from what is available based on groupWeight
            let lowWeight = Math.min(a, b, c, d);
            let candidates = [];
            if(lowWeight === a){
                    candidates.push(1, 2);
            }
            if(lowWeight === b){
                    candidates.push(3, 4);
            }
            if(lowWeight === c){
                    candidates.push(5, 6);
            }
            if(lowWeight === d){
                    candidates.push(7, 8);
            }

            filteredAvailable = available.filter(val => candidates.includes(val));



// check if there is three or less choices left, and if so we need to prevent a deadlock

            if (nullCount <= 4){
                filteredAvailable = filteredAvailable.filter(val => !nullArr.includes(val))
            }
            newGiftee = chooseGiftee(filteredAvailable);

Answer 3

If each of the group contains 2 values exactly (I will address if not too) then we can keep punch the numbers at odd index to keep creating a wall in between them. for eg

Groups

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

Starts with [1, 2] the initial array

process next -> [3, 4] punch at index 1 and 4 at index 3 so it became [1, 3, 2, 4]

Now process next ([5,6]) and do the same, so it became: [1, 5, 3, 6, 2, 4]

and then process next and continue.

Now, If there are groups that can have arbitrary length! SO, now here is the problem (Bang On! this is why I came here)

First we need to understand when (under which condition) it can be done! If there exists a group having length L and summation of length of all other groups is M then N - M should be <= 1

WHY?

lets assume a group have 3 members, in order to separate them out you need minimum 2 wall. so, all other group combining must have length 2.

So, If condition satisfied now we need to create pairs (because now possible)

1. First step, sort the array of groups desc with respect to their length
2. We need to start with the first one, but we need a continuation of odd indexes if the second group did not spoiled the first group completely.

Let's assume Groups are:

[[1, 2, 3, 4, 5, 6], [7,8,9], [10, 11, 12], [...], [.....]]

As the first group have length 6 and 5 elements is needed to dismiss it completely the next group [7, 8, 9] have length 3 so definitely it needs 2 more elements, so when we will start processing the next group after placing the current group components at 1, 3, 5 index, we need to start placing at 7, 9, ...

3. Once it dismissed the first array we can start from index 1 and keeping odd indexes.

I can produce a working code on demand, but once it's clear what we have to do the coding part all of us can do easily. Focused mainly in the algorithm part. However I can write a code if that helps!

ADDED example of implementation

var groups1 = [
    [7, 8, 9],
    [10, 11],
    [1, 2, 3, 4, 5, 6],
    [12, 13]
  ],
  groups2 = [
    [1, 2],
    [3, 4],
    [5, 6],
    [7, 8]
  ];

function punchGroups(groups) {
  groups.sort((a, b) => b.length - a.length);
  let firstLen = (groups[0] || []).length,
    oic = 0, //odd index increment counter
    covered = false; //covered the largest array flag
  return groups.reduce((acc, e) => {
    if (!acc.length) {
      return acc.concat(e)
    }
    e.forEach((n, i) => {
      let idx = (covered ? (i * 2) : (oic++) * 2) + 1;
      acc.splice(idx, 0, n);
      covered = oic >= (firstLen - 1)
    })
    return acc;
  }, []);
}

console.log('Groups: ', groups2);
console.log('Pairs: ', punchGroups(groups2));
console.log('-------------------------------');
console.log('Groups: ', groups1);
console.log('Pairs: ', punchGroups(groups1));

Well, Now to have different combinations of pairs (obviously within one of the possible pairs) you just need to manage groups and member of groups in all possible combinations (just use recursion to have all the combo) and process each to have all different possible pairs. You can generate all the outputs and pick one from them each day with a index or some factor which will make your call different may be timestamp and calculate it to a number within index range of all possible output array.

Answer 4

Your numbers are graph nodes, and edges exist from every node to all others but group neighbor. You need to cover all n nodes with n/2 edges while no node is shared by two edges. This covering is called perfect matching (not maximal as I wrote before, but perfect is maximal)

Python example using networkx library finds maximal matching (here is also perfect, but we cannot expect this fact always):

import networkx as nx
lst = [1, 2, 3, 4, 5, 6, 7, 8]
G = nx.Graph()
for i in range(0, len(lst)):
    for j in range(i + 1, len(lst)):
        if ((i // 2) != (j // 2)): //make edge for items from different pairs
            G.add_edge(lst[i], lst[j])
#print(G.edges)
m = nx.maximal_matching(G)
print(m)
>>> {(4, 2), (1, 3), (6, 8), (5, 7)}