按嵌套依赖数组元素对数组进行分组

Question

我可以帮助您翻译。以下是翻译的结果：

我有一个存储任务信息的数组。每个任务还有一个依赖于它的taskId数组。

输入

let inputArr = [
    {
        id: 1,
        dependOnTasks: [2, 3]
    },
    {
        id: 2,
        dependOnTasks: [3]
    },
    {
        id: 3,
        dependOnTasks: []
    },
    {
        id: 4,
        dependOnTasks: [5]
    },
    {
        id: 5,
        dependOnTasks: []
    },
    {
        id: 6,
        dependOnTasks: [5]
    }
]

预期输出是将所有依赖任务分组到一个数组中，以便在用户界面中显示。

输出

[
    [
        {
            id: 1,
            dependOnTasks: [2, 3]
        },
        {
            id: 2,
            dependOnTasks: [3]
        },
        {
            id: 3,
            dependOnTasks: []
        }
    ],
    [
        {
            id: 4,
            dependOnTasks: [5]
        },
        {
            id: 5,
            dependOnTasks: []
        },
        {
            id: 6,
            dependOnTasks: [5]
        }
    ]
]

我已经编写了一个函数来实现它，但是似乎我错误地硬编码了它。希望有人能够帮助我使用纯JavaScript / TypeScript或Underscore正确地实现它，因为我们已经在项目中使用了它。

---

注意：TaskId 将是类似于 "5878465507b36e1f9c4c46fe" 的随机字符串。

- trungk18

---

如果例如任务3依赖于任务4，预期的输出将是什么？或者任务5依赖于任务1？ - Robin Mackenzie

如果任务3依赖于任务4，我们可以得出结论，所有任务都相互依赖。因此，结果将是一组6个任务。如果任务5依赖于任务1，则同样如此。这对您清楚吗？如果有任何疑问，请告诉我。 - trungk18

这些ID是像这样的吗（第一个对象为1，第二个为2，以此类推…）还是它们是随机数？ - ibrahim mahrir

它将是类似于“5878465507b36e1f9c4c46fe”的随机字符串。 - trungk18

Answer 1

// will contain the groups (results).
var result = [];

// will serve as a holder of the already treated indexes of inputArr.
var indexCache = [];

// insert obj into a group, insert its dependencies and the object that depend on it as well.
function insertWithDependencies(obj, group){
    // insert this obj into this group
    group.push(obj);

    // First: look for the objects it depends on
    obj.dependOnTasks.forEach(function(id){
        for(var i = 0; i < inputArr.length; i++){
            // if the object in this index is already treated, then ignore it
            if(indexCache.indexOf(i) != -1) continue;
            // if this object is a dependency of obj then insert it with its own dependencies.
            if(inputArr[i].id == id){
                var o = inputArr[i];
                indexCache.push(i); // cache this i as well
                insertWithDependencies(o, group);
            }
        }
    });

    // Then: look for the objects that depends on it
    for(var i = 0; i < inputArr.length; i++){
        // if the object in this index is already treated, then ignore it
        if(indexCache.indexOf(i) != -1) continue;
        // if this object depends on obj then insert it with ...
        if(inputArr[i].dependOnTasks.indexOf(obj.id) != -1){
            var o = inputArr[i];
            indexCache.push(i); // cache i 
            insertWithDependencies(o, group);
        }
    }
};

// while there is element in the inputArr that haven't been treated yet
while(inputArr.length != indexCache.length){
    // the group that will hold the depending tasks all together
    var group = [];

    // look for the first untreated object in inputArr
    var i;
    for(i = 0; i < inputArr.length; i++)
        if(indexCache.indexOf(i) == -1)
            break;
    var obj = inputArr[i];

    // cache its index
    indexCache.push(i)

    // insert it along its dependencies
    insertWithDependencies(obj, group);

    // push the group into the result array
    result.push(group);
}

另一种方法：

这是一种优化的方法，但是inputArr中的数据将会在处理后丢失。它不会使用indexCache来判断索引是否已经被处理过，而是会将所有被处理过的项目在inputArr中设为null。因此，如果你不关心或者不会在之后使用inputArr，请使用这种方法代替：

var result = [];
function insertWithDependencies(obj, group){
    group.push(obj);
    obj.dependOnTasks.forEach(function(id){
        for(var i = 0; i < inputArr.length; i++){
            if(!inputArr[i]) continue;
            if(inputArr[i].id == id){
                var o = inputArr[i];
                inputArr[i] = null;
                insertWithDependencies(o, group);
            }
        }
    });
    for(var i = 0; i < inputArr.length; i++){
        if(!inputArr[i]) continue;
        if(inputArr[i].dependOnTasks.indexOf(obj.id) != -1){
            var o = inputArr[i];
            inputArr[i] = null;
            insertWithDependencies(o, group);
        }
    }
};

function findNotNull(){
    for(var i = 0; i < inputArr.length; i++)
        if(inputArr[i]) return i;
    return -1;
}

var index;
while((index = findNotNull()) != -1){
    var group = [];

    var obj = inputArr[index];
    inputArr[index] = null;
    insertWithDependencies(obj, group);

    result.push(group);
}

console.log(result);

- ibrahim mahrir

Answer 2

解决方案很简单，

1. 初始化一个空的组列表
2. 对于每个任务，查找是否在组列表中有具有id或任何依赖任务id的组
3. 如果没有，则添加一个新的组，其中包含任务id和依赖任务

var input = [
    { id: 1,  dependOnTasks: [2, 3]   },
    { id: 2,  dependOnTasks: [3]  },
    { id: 3,  dependOnTasks: [] },
    { id: 4,  dependOnTasks: [5] },
    { id: 5,  dependOnTasks: [] },
    { id: 6,  dependOnTasks: [5] }
];

var groups = [];

for (var i = 0; i < input.length; i++){
  var group = findGroup(groups,input[i]);
  if (!group){
    group = {ids : []};
    group.ids.push(input[i].id);
    groups.push(group);
  }
  
  if (group.ids.indexOf(input[i].id) === -1){
    group.ids.push(input[i].id);    
  }
  
  for (var j = 0; j < input[i].dependOnTasks.length; j++){
    if (group.ids.indexOf(input[i].dependOnTasks[j]) === -1){
      group.ids.push(input[i].dependOnTasks[j]);    
    }
  }
}
document.write(groups[0].ids + '</br>');
document.write(groups[1].ids + '</br>');

function findGroup(groups,task){
  for (var i = 0; i < groups.length; i++){
    var group = groups[i];
    if (group.ids.indexOf(task.id) !== -1){
      return group;
    }
    
    for (var j = 0; j < task.dependOnTasks.length; j++){
      if (group.ids.indexOf(task.dependOnTasks[j]) !== -1){
        return group;
      }
    }
  }
  return null;
}

- Low Flying Pelican

---

根据我的数据，似乎出现了某些错误。稍后我会更新问题并附上这些数据。 - trungk18

Answer 3

你可以尝试使用我的代码。

var inputArr = [
    {
        id: 1,
        dependOnTasks: [2, 3]
    },
    {
        id: 2,
        dependOnTasks: [3]
    },
    {
        id: 3,
        dependOnTasks: []
    },
    {
        id: 4,
        dependOnTasks: [5]
    },
    {
        id: 5,
        dependOnTasks: []
    },
    {
        id: 6,
        dependOnTasks: [5]
    }
]

// make matrix graph
var map = {};
for (var i = 0; i < inputArr.length; i++) {
    var task = inputArr[i];
    map[task.id] = map[task.id] || {};
    for (var j = 0; j < task.dependOnTasks.length; j++) {
        var dependId = task.dependOnTasks[j];
        map[dependId] = map[dependId] || {};
        map[task.id][dependId] = true;
        map[dependId][task.id] = true;
    }
}

var groupTasks = [];

for (var key in map) {
    var group = groupTasks.filter(function(e) {
        return e.indexOf(key) >= 0;
    })[0]

    if (!group) {
        group = [key];
        groupTasks.push(group);
    }

    for (var dependKey in map[key]) {
        if (group.indexOf(dependKey) == -1) {
            group.push(dependKey);
        }
    }
}

var result = groupTasks.map(function(group) {
    var tasks = [];
    group.forEach(function(id) {
        var task = inputArr.filter(function(e) { return e.id == id })[0];
        tasks.push(task);
    });
    return tasks;
})

console.log(JSON.stringify(result, null, 4));

- Tung Hoang

Answer 4

如果您不关心同一组中任务的顺序，则可以使用“并查集”实现“不相交集合”来解决问题。

数据结构如下：

function UnionFind(n) {
  this.parent = [...Array(n+1).keys()]
}

UnionFind.prototype.find = function(x) {
  if (this.parent[x] === x) {
    return x
  }
  const ret = this.find(this.parent[x])
  this.parent[x] = ret
  return ret
}

UnionFind.prototype.union = function(x, y) {
  let x_rep = this.find(x)
  let y_rep = this.find(y)
  if (x_rep !== y_rep) {
    this.parent[x_rep] = y_rep
  }
}

愚蠢的数据源：

let inputArr = [
    {
        id: 1,
        dependOnTasks: [2, 3]
    },
    {
        id: 2,
        dependOnTasks: [3]
    },
    {
        id: 3,
        dependOnTasks: []
    },
    {
        id: 4,
        dependOnTasks: [5]
    },
    {
        id: 5,
        dependOnTasks: []
    },
    {
        id: 6,
        dependOnTasks: [5]
    }
]

驱动程序：

let len = inputArr.length
let uf = new UnionFind(len)

// iterate through all tasks to group them
inputArr.forEach(entry => {
  entry.dependOnTasks.forEach(depsId => {
    uf.union(entry.id, depsId)
  })
})

// reiterate to retrieve each task's group and group them using a hash table
let groups = {}
inputArr.forEach(entry => {
  const groupId = uf.find(entry.id)
  if (!groups.hasOwnProperty(groupId)) {
    groups[groupId] = [entry]
    return
  }
  groups[groupId].push(entry)
})

let result = Object.keys(groups).map(groupId => groups[groupId])
console.log(JSON.stringify(result, null, 2))

注意：如果您的情况中id是随机字符串，则只需将this.parent更改为哈希映射，如果您关心顺序（因为存在依赖树），请考虑使用拓扑排序。

- Allen

---

谢谢Xlee，我正在检查它。 - trungk18