Pairing two identical arrays, avoiding duplicates

19 Jun 2020 algorithm

I recently answered a question on Stack Overflow where the OP had two identical arrays, and wished to pair them, but avoiding duplicates. So:

let arr1 = [1, 2, 3, 4],
    arr2 = [1, 2, 3, 4];

Therefore [1,2] would be an acceptable pair, but [1,1] would not.

At first glance it doesn't sound difficult, but it turned out to be a bit of a brain burner. I thought I'd post my approach here.

The crux of the approach involves ensuring each pair except the last will always be valid. And then, if we end up with duplicate values in the final pair, we can just swap the B value from the final pair with the B value from the first pair.

Here's the full answer:

//set arrays - can be the same or different; order unimportant
let a = [1,2,3,4],
    b = [1,2,3,4];

//shuffle the b array
b.sort(() => Math.floor(Math.random() * 2));

//log the first b val in our shuffled array
let first_b_val = b[0];

//map a values to be values
let pairs = a.map(a_val => {
    let b_index = b[0] !== a_val ? 0 : 1;
    b_val = b[b_index];
    if (!b_val) b_val = a_val;
    b.splice(b_index, 1);
    return [a_val, b_val];
});

//sometimes we'll get a clash with the final pair - if so,
//swap the final pair's b value with the first pair's b value
let final_pair = pairs[pairs.length-1];
if (final_pair[0] === final_pair[1]) {
    let tmp = final_pair[1];
    final_pair[1] = pairs[0][1];
    pairs[0][1] = tmp;
}

Let's take a look in more detail. First we declare our arrays. As commented, they can be the same or different, and the order is unimportant. We'll then shuffle the B array randomly.

We're now ready to generate pairs. We do this by creating a new array, pairs, which is derived from mapping A values to B values. As we iterate over the A values we need to algorithmically decide which B value to pair them with. As we decide on a partner, we delete it from the B array. Specifically:

Use the first value in B (index 0) if it's different from the current A value
Otherwise use the second value in B (index 1)
Check we ended up with a B value (by the time we're pairing the last value, there will be only one value left in B, i.e. only index 0, no index 1)
If we didn't, it'll be the last pairing; for now, allow it to be the same as the A value, so we'll have a duplicate
Remove the selected B value from the B array, so it can't be chosen again

Let's walk through it as it happens. Suppose our two arrays (after shuffling the B array) are:

let a = [1,2,3,4],
    b = [4,1,3,2];

The algorithm steps through in the following ways in building the pairs:

A value = 1; B value = 4 (index 0); delete b[0]; b now == [1,3,2]
A value = 2; B value = 1 (index 0); delete b[0]; b now == [3,2]
A value = 3; B value = 2 (index 1 - because b[0] is same as A value); delete b[1]; b now == [2]
A value = 4; B value = 2 (index 0); delete b[0]; b now = []

But what about if we'd ended up with a duplicate final pair? In that case, our failsafe, which uses B index 1 rather than 0 wouldn't work because there's no more B values to choose from. This would happen if our arrays had started like this:

let a = [1,2,3,4],
    b = [3,1,2,4];

In that case we'd have ended up with the following pairs:

[
    [1,3],
    [2,1],
    [3,2],
    [4,4]
]

Our algorithm ensures that any remaining duplicate pair, if we get one at all, would be in the final pair. That brings us to the last part of the code:

let final_pair = pairs[pairs.length-1];
if (final_pair[0] === final_pair[1]) {
    let tmp = final_pair[1];
    final_pair[1] = pairs[0][1];
    pairs[0][1] = tmp;
}

That simply says that, if the final pair end up the same, we swap over the B values from the final and first pairs.

Thus, we're guaranteed to have non-matching pairs.

Did I help you? Feel free to be amazing and buy me a coffee on Ko-fi!