javascript - 找出许多事件之间的顺序

Question

当前正在解决一个难题并寻找一些有关按事件排序的提示。我想知道我应该遵循的具体程序是什么。考虑一下这个

我输入一个数字，然后有n个输入 每个输入都有两个事件，其中 event1 event2 和 event1 在 event2 之前发生。

考虑输入

6
Eatfood Cuthair
Eatfood BrushTeeth
School  EatFood
School  DoHair
DoHair   Meeting
Meeting Brushteeth

输出将是

school -> dohair-> eatfood -> meeting -> cuthair -> brushteeth

按照这个顺序。因为如果我们把一切都写下来，学校确实是首先发生的事情，然后是头发。如果存在不止一种可能的排序，则只需输出一种。您可以假设所有事件都以某种方式连接，并且不存在循环依赖关系。

我正在考虑做的是创建两个数组，一个包含所有 eventOne's 和所有 eventTwo's。但我不太确定从这里该去哪里。我想用 javascript 来做这个。谢谢!建议任何提示或算法

另一个输入

6
vote_140_prof announce_140_prof
vote_140_prof first_day_of_classes
dev_shed_algo vote_140_prof
dev_shed_algo do_hair
do_hair big_meeting
big_meeting first_day_of_classes

输出

dev_shed_algo do_hair vote_140_prof big_meeting announce_140_prof first_day_of_classes

我在我的电脑上找到了解决方案文件，它是用Python编写的，我不知道，但希望这能帮助其他人理解问题

from collections import defaultdict

def toposort(graph, roots):
    res = [i for i in roots]
    queue = [i for i in roots]
    while queue:
        for i in graph[queue.pop(0)]:
            if i not in res:
                res.append(i)
                queue.append(i)
    return res

graph = defaultdict(set)
a_set = set()
b_set = set()

for i in range(int(input())):
    a, b = input().split()
    a_set.add(a)
    b_set.add(b)
    graph[a].add(b)

print(" ".join(i for i in toposort(graph, a_set - b_set)))

我的尝试

var words =
    'vote_140_prof announce_140_prof vote_140_prof first_day_of_classes devshed_algo vote_140_prof dev_shed_algo do_hair do_hair big_meeting big_meeting first_day_of_classes';

var events = words;

events = events.split(/\s+/);
console.log(events);

var obj = {};
for (var i = 0 ; i < events.length ; i++)
    {
        var name = events[i];
        if(obj[name] === undefined )
            {
                obj[name] = [];
            }

        obj[name].push(events[i%2 === 1 ? i-1 : i+1]);
    }
console.log(obj);

正在格式化

function sequenceEvents(pairs){
        var edges = pairs.reduce(function(edges,pair){
            edges.set(pair[0],[]).set(pair[1],[]);
            new Map();
        });

        pairs.forEach(function(edges,pair){

            edges.set(pair[0],[]).set(pair[1],[]);

        });

        var result = [];

        while(edges.size){
            var children = new Set([].concat.apply([],[...edges.value()]));
            var roots = [...edges.keys()].filter(function(event){
                !children.has(event);
            });

            if(!roots.length) throw "Cycle detected";
        roots.forEach(function(root){
           result.push(root);
           edges.delete(root);

        });

        }

        return result;

    }

Answer 1

Python 算法不正确。对于此输入它将失败:

3
A B
A C
C B

它将输出:

A, B, C

...这与最后一条规则冲突。这是因为它错误地假设任何根事件的子事件都可以安全地添加到结果中，并且不依赖于其他事件。在上述情况下，它将把 A 识别为根，将 B 和 C 识别为其子代。然后它会从该列表中弹出 C，并将其添加到结果中，而不会看到 C 依赖于 B，而 B 尚未出现在结果中。

正如其他人所指出的，您需要确保大小写一致。 Brushteeth 和 BrushTeeth 被视为不同的事件。 EatFood 和 Eatfood 也是如此。

我在这里提供一个解决方案。我希望内联评论能够很好地解释正在发生的事情:

function sequenceEvents(pairs) {
    // Create a Map with a key for each(!) event, 
    // and add an empty array as value for each of them.
    var edges = pairs.reduce(
        // Set both the left and right event in the Map 
        //   (duplicates get overwritten)
        (edges, pair) => edges.set(pair[0], []).set(pair[1], []),
        new Map() // Start with an empty Map
    );
    // Then add the children (dependent events) to those arrays:
    pairs.forEach( pair => edges.get(pair[0]).push(pair[1]) );

    var result = [];
    // While there are still edges...
    while (edges.size) {
        // Get the end points of the edges into a Set
        var children = new Set( [].concat.apply([], [...edges.values()]) );
        // Identify the parents, which are not children, as roots
        var roots = [...edges.keys()].filter( event => !children.has(event) );
        // As we still have edges, we must find at least one root among them.
        if (!roots.length) throw "Cycle detected";
        roots.forEach(root => {
            // Add the new roots to the result, all events they depend on
            // are already in the result:
            result.push(root);
            // Delete the edges that start with these events, since the
            // dependency they express has been fulfilled:
            edges.delete(root);
        });
    }
    return result;
}


// I/O
var input = document.querySelector('#input');
var go = document.querySelector('#go');
var output = document.querySelector('#output');

go.onclick = function() {
    // Get lines from input, ignoring the initial number
    // ... then split those lines in pairs, resulting in
    // an array of pairs of events
    var pairs = input.value.trim().split(/\n/).slice(1)
                     .map(line => line.split(/\s+/));
    var sequence = sequenceEvents(pairs);
    output.textContent = sequence.join(', ');
}

Input:<br>
<textarea id="input" rows=7>6
EatFood CutHair
EatFood BrushTeeth
School  EatFood
School  DoHair
DoHair   Meeting
Meeting BrushTeeth
</textarea>
<button id="go">Sequence Events</button>
<div id="output"></div>

没有箭头函数，也没有应用

正如在评论中您表示您希望首先使用不带箭头函数的代码:

function sequenceEvents(pairs) {
    // Create a Map with a key for each(!) event, 
    // and add an empty array as value for each of them.
    var edges = pairs.reduce(function (edges, pair) {
        // Set both the left and right event in the Map 
        //   (duplicates get overwritten)
        return edges.set(pair[0], []).set(pair[1], []);
    }, new Map() ); // Start with an empty Map
    // Then add the children (dependent events) to those arrays:
    pairs.forEach(function (pair) {
        edges.get(pair[0]).push(pair[1]);
    });

    var result = [];
    // While there are still edges...
    while (edges.size) {
        // Get the end points of the edges into a Set
        var children = new Set(
            [...edges.values()].reduce(function (children, value) {
                return children.concat(value);
            }, [] )
        );
        // Identify the parents, which are not children, as roots
        var roots = [...edges.keys()].filter(function (event) {
            return !children.has(event);
        });
        if (!roots.length) throw "Cycle detected";
        roots.forEach(function (root) {
            // Add the new roots to the result, all events they depend on
            // are already in the result:
            result.push(root);
            // Delete the edges that start with these events, since the
            // dependency they express has been fulfilled:
            edges.delete(root);
        });
    }
    return result;
}