javascript - 生成图的每种拓扑排序

Question

考虑这个代表图形的输入数组:

[
    {"id":1,"prev":["NaN"]},
    {"id":2,"prev":["NaN"]},
    {"id":3,"prev":[1]},
    {"id":4,"prev":[2]},
    {"id":5,"prev":[2]},
    {"id":6,"prev":[3,4]},
    {"id":7,"prev":[5,6]}
]

我的任务是找到对列表中的元素进行排序的每个可能的选项。

元素的顺序取决于该元素是否有前一个元素。例如，没有。 7 永远是最后一个，因为它有 2 个前面的元素并且没有跟随者。

我尝试按如下方式实现但没有成功:

var possibleSolutions = [];
recursiveCheck(tasks.slice(), tasks.length, []);

function recursiveCheck(array, noCalls, currentSolution) {
    var solution = currentSolution;
    array.forEach((task, index, object) => {
        if (task.prev.length <= 1 && isNaN(task.prev[0])) {
            var tmpTasks = array.slice();
            solution.push(task.id);
            tmpTasks.splice(index, 1);
            tmpTasks.forEach(el => {
                el.prev.forEach((prevEl, index, object) => {
                    if (prevEl == task.id) {
                        object.splice(index, 1)
                    }
                })
            })
            noCalls--;
            if (noCalls == 0) {
                possibleSolutions.push(solution)
                solution = [];
            } else {
                recursiveCheck(tmpTasks, noCalls, solution);
            }
        }
    });
}

这应该是输出:

[
    [1,2,3,4,5,6,7],
    [1,2,3,4,6,5,7],
    [1,2,3,5,4,6,7],
    [1,2,4,3,5,6,7],
    [1,2,4,3,6,5,7],
    [1,2,4,5,3,6,7],
    [1,2,5,3,4,6,7],
    [1,2,5,4,3,6,7],
    [1,3,2,4,5,6,7],
    [1,3,2,4,6,5,7],
    [1,3,2,5,4,6,7],
    [2,1,3,4,5,6,7],
    [2,1,3,4,6,5,7],
    [2,1,3,5,4,6,7],
    [2,1,4,3,5,6,7],
    [2,1,4,3,6,5,7],
    [2,1,4,5,3,6,7],
    [2,1,5,3,4,6,7],
    [2,1,5,4,3,6,7],
    [2,4,1,3,5,6,7],
    [2,4,1,3,6,5,7],
    [2,4,1,5,3,6,7],
    [2,4,5,1,3,6,7],
    [2,5,1,3,4,6,7],
    [2,5,1,4,3,6,7],
    [2,5,4,1,3,6,7]
]

再举一个例子，数组不能像 [1,3,6,...] 那样排列，因为 6 有一个前一个元素 4，因此元素 4 必须在 6 之前。

Answer 1

让我们更抽象地讨论一下这个问题。

一个directed graph是我们真正作为输入的数据结构。我们有一组 V 顶点/节点和一组 E 边。每条边都是有序对 (v1, v2)，其中 v1 和 v2 都是顶点，表示从 v1< 开始的箭头 到 v2。在这里，我们使用“邻接列表”表示法来表示该图。

任务是找到到达topologically sort的所有方法。这张图。

我们可以如下描述对图进行拓扑排序的方法:

如果我们想对空图(没有顶点的图)进行拓扑排序，这很简单:唯一的方法是输出空排序[]。因此对空图进行拓扑排序的所有方法的列表将为[[]]。

现在，让我们考虑一下非空图的拓扑排序问题。考虑一个序列s，它是非空图G的拓扑排序。我们可以考虑 s 的第一个元素，我们将其称为 x，以及所有其余元素的序列，我们将其称为 s'.

我们知道x一定是G中的一个节点，并且我们知道x在G<中不能有任何前驱。换句话说，不可能有节点 y 使得 (y, x) 是一条边。

我们还知道s'一定是G'_x的拓扑排序，它是G但有节点 x(以及连接到它的所有边)已删除。

因此，为了得到G的所有拓扑排序，我们必须找到所有以x为起始元素，剩余元素为s'的序列，例如x 是 G 中没有前身的元素，而 s' 是 G'_x 的拓扑排序。

const remove_node = (g, x) => 
    g.flatMap((node) => node["id"] == x ? 
                        [] : 
                        {"id": node["id"], 
                         "prev": node["prev"].filter((id) => id != x)});

const topological_sorts = (g) => 
    g.length == 0 ?
    [[]] :
    g.filter((node) => node["prev"].length == 0)
     .map((node) => node["id"])
     .flatMap((id) => 
       topological_sorts(remove_node(g, id)).map((sorting) =>
         [id].concat(sorting)));

const remove_nan = (g) => g.map((node) => 
   ({ "id" : node.id, 
     "prev": node.prev.filter((predecessor) => 
       predecessor !== "NaN") } ));

const get_answer = (g) => topological_sorts(remove_nan(g));

在图表上调用 get_answer 将得到正确的答案。