我需要订购一个对象数组，由名称和依赖项列表（由名称组成）组成。
这个数组的一个例子可以是：
[
{ name: 'a', requires: ['b', 'c'] },
{ name: 'b', requires: ['c'] },
{ name: 'c', requires: [] },
]
我希望对这个数组进行排序，以便需要一组特定依赖项的项目将位于其所需依赖项之后。
该数组实际上可以包含更多项目，如果排序函数在循环依赖的情况下抛出错误，我也没关系。
输出示例：
[
{ name: 'c', requires: [] }, // first, no dependencies, and required by both the others
{ name: 'b', requires: ['c'] }, // second, because it needs `c` first
{ name: 'a', requires: ['b', 'c'] }, // last, because requires both the others
]
最简洁的方法是什么？
您可以尝试以下（更改测试用例以支持更多可能的组合）
var arr = [
{ name: 'd', requires: ['a', 'c'] },
{ name: 'a', requires: ['b', 'c'] },
{ name: 'b', requires: ['c'] },
{ name: 'e', requires: ['d'] },
{ name: 'c', requires: [] },
];
var map = {}; // Creates key value pair of name and object
var result = []; // the result array
var visited = {}; // takes a note of the traversed dependency
arr.forEach(function(obj){ // build the map
map[obj.name] = obj;
});
arr.forEach(function(obj){ // Traverse array
if(!visited[obj.name]) { // check for visited object
sort_util(obj);
}
});
// On visiting object, check for its dependencies and visit them recursively
function sort_util(obj){
visited[obj.name] = true;
obj.requires.forEach(function(dep){
if(!visited[dep]) {
sort_util(map[dep]);
}
});
result.push(obj);
}
console.log(result);更新：感谢 Nina Scholz，我更新了代码，以便
sort这可能可以完成任务。 背后的想法是，使用
sortabab对于每个元素，我还继承了所有依赖项。
const list = [
{ name: 'b', requires: ['c'] },
{ name: 'e', requires: ['d'] },
{ name: 'd', requires: ['a', 'c'] },
{ name: 'c', requires: [] },
{ name: 'a', requires: ['b', 'c'] },
];
// indexed by name
const mapped = list.reduce((mem, i) => {
mem[i.name] = i;
return mem;
}, {});
// inherit all dependencies for a given name
const inherited = i => {
return mapped[i].requires.reduce((mem, i) => {
return [ ...mem, i, ...inherited(i) ];
}, []);
}
// order ...
const ordered = list.sort((a, b) => {
return !!~inherited(b.name).indexOf(a.name) ? -1 : 1;
})
console.log(ordered);此提案查找先前的元素并检查实际元素是否具有之前排序的所需要求。
如果找到所有要求，则将对象拼接到索引。
function order(array) {
var i = 0,
j,
temp;
while (i < array.length) {
temp = array.slice(0, i);
for (j = i; j < array.length; j++) {
if (array[j].requires.every(n => temp.some(({ name }) => n === name))) {
array.splice(i++, 0, array.splice(j, 1)[0]);
break;
}
}
}
return array;
}
var array = [{ name: 'd', requires: ['a', 'c'] }, { name: 'a', requires: ['b', 'c'] }, { name: 'b', requires: ['c'] }, { name: 'e', requires: ['d'] }, { name: 'c', requires: [] }];
console.log(order(array));.as-console-wrapper { max-height: 100% !important; top: 0; }几年后，我找到了这个问题的超短解决方案，我的一个朋友与我分享了它，我不接受学分。
elements.sort((a, b) =>
a.requires.includes(b.name) ? 1 : b.requires.includes(a.name) ? -1 : 0
);
您的数据可以通过图表表示。所以你可以使用拓扑排序来解决这个问题。
详细阐述我对 Fez Vrasta 发布的答案的评论：
假设我们没有原来问题中的元素，而是：
[
{ name: 'a', requires: ['b'] },
{ name: 'b', requires: ['c'] },
{ name: 'c', requires: [] },
]
我所做的就是删除显式的“a 需要 c”条目，尽管 a 需要 b，b 需要 c 这一事实暗示了这一点。现在，我想检查 Fez Vrasta 的答案是否适用于这组数据，即处理顺序应该是 c，然后是 b，然后是 a。但是，我知道排序的结果可能取决于原始列表中项目的顺序，因此为了安全起见，我将生成原始列表的所有可能的排列，对每个排列进行排序（通过 Fez Vrasta 的算法），然后显示结果列表中项目的顺序。我从某处偷了一个列表排列算法。您可以 1) 相信我，2) 获取自己的算法或 3) 手动形成所有排列（因为只有 3 个条目，所以无论如何也只有 6 种可能的排列）。
我的测试算法是：
import {generatePermutations} from './utils.js';
let elements = [
{ name: 'a', requires: ['b'] },
{ name: 'b', requires: ['c'] },
{ name: 'c', requires: [] },
]
for (let lItems of generatePermutations(elements)) {
let org = lItems.map(x => x.name).join(' ');
lItems.sort((a, b) =>
a.requires.includes(b.name) ? 1
: b.requires.includes(a.name) ? -1
: 0
);
let result = lItems.map(x => x.name).join(' ');
console.log(org, ' => ', result);
}
运行结果为：
$ node dep.js
a b c => c b a
a c b => a c b
b a c => b a c
b c a => c b a
c a b => c b a
c b a => c b a
如您所见，它并不总是给出正确的结果。剧透警告：如果我将“c”添加到 a 的要求列表中，我会得到原始元素列表的所有可能排列的正确结果。