javascript - 使用排序逻辑合并和排序多个数组

Question

我有一个数组数组，它​​们根据给定的位置进行排序。

例如:

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

我的目标是合并它们并删除重复项但保持顺序。例如，我期望得到 ['X', 'M', 'D', 'K', 'Z', 'H', 'T', 'B', 'A' ]

到目前为止我尝试过的: Merge arrays and keep ordering

与上面的帖子类似，可能会有冲突，但这里有以下规则:

• 如果由于信息不足而无法确定项目的最终位置，则第一个应该在第二个之前有一个索引。例如

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

结果应该是['X','H','C']

• 每个项目都应该出现在最终输出中
• 如果一个项目出现在不同位置的多个数组中，则第一个出现的是正确的(跳过其他)。

解决方案的问题来自Merge arrays and keep ordering是:

1. 当第一个数组不以“X”开头时，整个结果数组放错了位置。
2. 当第一项时项放错位置:当数组不是以'X'开头时，新项'M'将被定位在结果字符串的末尾而不是'X'和'D'之间。

这是我使用上面链接中的这些代码的结果数组:

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);
                        }
                    });
                });

我当前的结果 = ['H','T','B','A','X','K','Z','M','D']

最值得注意的是，'H' 是项目中的第一个，即使它应该在 'X','M','D','K','Z' 之后。 “D”现在位于末尾，即使它应该在 “K”、“Z”、“H”、“B”、“A” 之前。

欢迎任何帮助，在此先感谢您!

Answer 1

您可以采用所有数组中索引为零的唯一值数组，并通过查看其他数组上的索引来过滤它，如果它们的索引大于一(目前以负方式实现)则将其删除。然后过滤数组并删除空数组。

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!