目前正在解决一个难题,并寻找一些按事件排序的技巧。我想知道我应该遵循的程序到底是什么。考虑一下
我输入一个数字,然后输入n
每个输入有两个事件,其中 for 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;
}
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>
没有箭头功能,也没有apply
正如您在注释中指出的那样,您希望首先拥有没有箭头函数的代码:
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;
}
好的。这是我对这个问题的看法。
var makePair = function(i0, i1) {
return {start: i0, end: i1};
};
var mp = makePair;
var makeBefores = function(pairs) {
var befores = {};
pairs.forEach(function(pair) {
if (befores[pair.end] == null) {
befores[pair.end] = [pair.start];
} else {
befores[pair.end].push(pair.start);
}
if (befores[pair.start] == null) {
befores[pair.start] = [];
}
});
for (var key in befores) {
console.log("after " + key + "there is:");
for (var i = 0; i < befores[key].length; i++) {
console.log(befores[key][i]);
}
}
return befores;
};
var shouldGoBefore = function(item, before) {
for (var i = 0; i < before.length; i++) {
if (item == before[i]) {
return true;
}
}
return false;
};
var sortEvents = function(pairs) {
if (pairs.length === 0) {
return [];
}
if (pairs.length === 1) {
return [pairs[0].start, pairs[0].end];
}
console.log(pairs);
var befores = makeBefores(pairs);
var sorted = [];
for (var key in befores) {
var added = false;
for (var i = 0; i < sorted.length; i++) {
console.log('checking if ' + sorted[i] + ' should go before ' + befores[key]);
if (shouldGoBefore(sorted[i], befores[key])) {
//console.log("splicing");
sorted.splice(i, 0, key);
added = true;
break;
}
}
if (!added) {
sorted.push(key);
}
}
return sorted.reverse();
}
var pairs = [mp('vote_140_prof','announce_140_prof'),mp('vote_140_prof','first_day_of_classes'),mp('dev_shed_algo','vote_140_prof'),mp('dev_shed_algo','do_hair'),mp('do_hair','big_meeting'),mp('big_meeting','first_day_of_classes'),mp('announce_140_prof','first_day_of_classes')];
console.log(sortEvents(pairs));
事情可能不起作用的一个原因是您的测试数据的大小写不一致。此运行的结果是:
Array [ "School", "EatFood", "CutHair", "Meeting", "BrushTeeth", "DoHair" ]
我将在您的其他数据集上对其进行测试,但我相信这满足了提示。我将在一分钟内写下它是如何工作的。
请注意,这不会执行任何文件 IO 或行读取。它将要sortEvents
的输入作为具有 start
和 end
属性的对象数组,我提供了一个帮助程序方法makePair
创建该属性。
该解决方案的工作原理是构建一个字典,其中包含哪些元素先于其他元素。
如果您有这样的输入:
a->b
c->a
c->b
b->d
字典是这样的:
a->[c],
c->[],
b->[a,c],
d->[b]
然后我们使用数组作为一种链表,我们浏览它,看看我们是否必须插入一些东西。因此,例如,如果我们试图查看应该插入a
的位置并且列表c
,那么我们将查看字典中的c
,看到其中c
,然后我们知道在a
之前应该有c
,因此我们必须在c
之后插入a
从第一个事件开始进行哈希映射,并将其值设置为 0,而不是在遇到事件 2 时检查哈希中事件 1 的值,而不是为事件 2 输入较小的值。完成后按值对哈希进行排序。
宾果游戏
line = input();
myMap = dict()
i=0
while i < line:
event1 = raw_input()
event2 = raw_input()
if event1 in myMap :
myMap[event2] = myMap[event1]+1
elif event2 in myMap:
myMap[event1] = myMap[event2]-1
else :
myMap[event1] = 0
myMap[event2] = 1
i=i+1
print i
print myMap
我不知道为什么有些人投了反对票,但是是的,它正在工作,至少在你的两个样本上都是这样
示例输入和输出
6
eatfood
cuthair
1
{'eatfood': 0, 'cuthair': 1}
eatfood
brushteeth
2
{'brushteeth': 1, 'eatfood': 0, 'cuthair': 1}
school
eatfood
3
{'brushteeth': 1, 'eatfood': 0, 'school': -1, 'cuthair': 1}
school
dohair
4
{'brushteeth': 1, 'eatfood': 0, 'school': -1, 'cuthair': 1, 'dohair': 0}
dohair
meeting
5
{'school': -1, 'brushteeth': 1, 'cuthair': 1, 'dohair': 0, 'eatfood': 0, 'meeting': 1}
meeting
brushteeth
6
{'school': -1, 'brushteeth': 2, 'cuthair': 1, 'dohair': 0, 'eatfood': 0, 'meeting': 1}
代码是用python写的,随意用javascript转换