Merge and sort multiple arrays using their ordering logic

Question

I have an array of arrays and they are sorted based on their given position.

For example:

const test_arrays = [
['H', 'A'],
['X', 'K', 'Z', 'H', 'B', 'A'],
['M', 'H', 'B'],
['X', 'M', 'D','H', 'T', 'B'],
['X', 'D', 'K', 'Z']
]

My aim is to merge them and remove duplicates but keeping the ordering. For instance, I am expecting to get a result of ['X', 'M', 'D', 'K', 'Z', 'H', 'T', 'B', 'A']

What I have tried so far: Merge arrays and keep ordering

Similar to the post from the above, it is likely that there will be conflicts but here are the following rules:

If the final position of the item cannot be determined because of insufficient information, the first one should have an index before the second one. E.g.

const arrays = [
['X', 'H'],
['X', 'C']
]

The result should be ['X','H','C']

Every items should appear in the final output
If an item is appearing in multiple arrays at different positions, the first appearance is the right one (skip others).

The problems of the solution from Merge arrays and keep ordering are:

The whole result array is misplaced when the first array does not start with 'X'.
The item is misplaced when the first item : When the array does not start with 'X', the new item 'M' will be positioned in the end of the result string instead of between 'X' and 'D'.

This is my result array using these codes from the link above:

var test_array_sorted=[];
test_arrays.forEach(array => {
                    array.forEach((item, idx) => {
                        // check if the item has already been added, if not, try to add
                        if(!~test_array_sorted.indexOf(item)) {
                            // if item is not first item, find position of his left sibling in result array
                            if(idx) {
                                const result_idx = test_array_sorted.indexOf(array[idx - 1]);
                                // add item after left sibling position
                                test_array_sorted.splice(result_idx + 1, 0, item);
                                return;
                            }

                        test_array_sorted.push(item);
                        }
                    });
                });

My current result = ['H','T','B','A','X','K','Z','M','D']

Most noticeably, 'H' is the first in the item even though it should be after 'X','M','D','K','Z'. 'D' is now positioned in the end even though it should be before 'K','Z','H','B','A'.

Any help is welcomed and thank you so much in advance!

Do you have to manage if it's possible ? i.e if the first array is ['H', 'A'] and the second could be ['X', 'D', 'K', 'Z'] ? Or will it be always possible ? — Leyff da, Feb 12 '21 at 15:41
Hi Leyff thanks! In this particular case, the result array should be ['H','A','X','D','K','Z'] since there is no logic to determine the sequence. As such, the result array would just be a merged solution similar to .concat. — Kaspar, Feb 12 '21 at 15:45

Nina Scholz · Accepted Answer · 2021-02-17T14:30:12.900

You could take an array of unique values of index zero of all arrays and filter it by looking to the indices on other arrays and remove if they have an index greater than one (currently implemented in a negative fashion). Then filter the arrays and remove empty arrays.

const
    topSort = (arrays) => {
        const result = [];
        while (arrays.length) {
            const
                temp = [...new Set(arrays.map(([v]) => v))]
                    .filter(v => arrays.every(a => a.indexOf(v) < 1));

            if (!temp.length) throw new Error('Circular reference!');
            temp.forEach(v => {
                result.push(v);
                arrays = arrays.filter(a => {
                    if (a[0] === v) a.shift();
                    return a.length;
                });
            });
        }
        return result;
    },
    arrays = [['H', 'A'], ['X', 'K', 'Z', 'H', 'B', 'A'], ['M', 'H', 'B'], ['X', 'M', 'D', 'H', 'T', 'B'], ['X', 'D', 'K', 'Z']],
    circularReference = [['x', 'c'], ['c', 'x']];

console.log(...topSort(arrays));            // X M D K Z H T B A
console.log(...topSort(circularReference)); // Exception: Circular reference!

Hi Nina in the case of logical error like `test_arrays =[['x','c'],['c','x']]` what is the best way to have the alert pop up and jump out of the while loop? — Kaspar, Feb 17 '21 at 14:20
you could store the array with items and if empty, you got a circular reference somehwere. please see edit. — Nina Scholz, Feb 17 '21 at 14:30

score 0 · Answer 2 · answered Feb 12 '21 at 16:03

0

Use .sort() to sort array

test_array_sorted.sort()

answered Feb 12 '21 at 16:03

ShåmwëêlYt Pøōl

13
6

Merge and sort multiple arrays using their ordering logic

2 Answers2