javascript - 当排序顺序信息仅适用于某些项目时，对 Javascript 数组进行排序

Question

我有一个数据数组 -

let data = ['x1', 'x2', 'x3', 'x4'];

另一个二维数组指定数据数组中元素的排序顺序 -

let order =
    [
        ['x4', 'x1'],
        ['x3', 'x2']
    ];

已编辑:从订单数组中删除了冲突规则

“order”数组仅提供数据数组中某些元素的排序数据。 “order”数组中未提供的项目的顺序无关紧要。

我正在使用以下逻辑 -

console.log("Before sort:", data);

data.sort((a, b) => {
    console.log("a:", a, ",", "b:", b);

    for (orderRow of order) {
        if (orderRow.includes(a) && orderRow.includes(b)) {
            return orderRow.indexOf(a) - orderRow.indexOf(b);
        }
    }

    return 0;
});

console.log("After sort:", data);

下面是输出 -

Before sort: [ 'x1', 'x2', 'x3', 'x4' ]
a: x2 , b: x1
a: x3 , b: x2
a: x3 , b: x2
a: x3 , b: x1
a: x4 , b: x3
a: x4 , b: x2
After sort: [ 'x1', 'x3', 'x2', 'x4' ]

逻辑不起作用(x4 需要位于 x1 之前，如 order 数组第一项中提到的那样)，因为 x1,x4 对永远不会直接按排序进行比较。

寻找建议。

预期结果:[ 'x4', 'x3', 'x2', 'x1' ] ==> x4 必须位于 x1 之前 [顺序数组 - 项目 1]

OR ["x4", "x1", "x3", "x2"] ==> 满足顺序数组 i 中的所有规则，例如 x3 在 x2 之前，x4 在 x1 之前

注意:订单数组的行数可能不同，每行中的项目也不同。如果多行指定了冲突的排序顺序，则应用索引较低的行提供的排序顺序。

Answer 1

这是 topological sorting 的简单实现使用深度优先行走。孤立节点以相反的顺序添加。

function topsort(nodes, graph) {
    let color = {},
        sorted = [];

    for (let node of nodes)
        visit(node)

    return sorted

    function visit(node) {
        if (color[node] === 'black')
            return
        if (color[node] === 'grey')
            throw new Error('cycle!')
        color[node] = 'grey'
        for (let [n, m] of graph)
            if (n === node)
                visit(m)
        color[node] = 'black'
        sorted.unshift(node)
    }
}

//

let data = [...'abcdefgh'];

let order = [
    ['b', 'a'],
    ['a', 'c'],
    ['a', 'g'],
    ['f', 'c'],
    ['e', 'f'],
];


console.log(...topsort(data, order))