Merge and sort multiple arrays using their ordering logic

user_15197861 0
Viewed 108

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:

  1. The whole result array is misplaced when the first array does not start with 'X'.
  2. 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!

merge sorting arrays javascript
2 Answers

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!

user_14476750

Use .sort() to sort array

test_array_sorted.sort()

user_140264860
Related