Групповой массив по вложенному зависимому элементу массива

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»

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, чтобы узнать, обрабатывается ли индекс уже или нет, но вместо этого он будет обрабатывать все обработанные элементы null в inputArr.Так что, если вы не заботитесь или не будет использовать 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); 

Answer 2

Если вы не заботитесь о order задач в одной и той же группе. Возможно использование опции union and find для реализации опции disjoint set.

структура данных Util:

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)) 

примечание: если идент случайная строка в вашем случае, просто изменить this.parent к хэш-карте, и если вы заботитесь о заказе (поскольку есть деревья зависимостей), рассмотрите возможность использования topological sort вместо.

Answer 3

Раствор прост,

1. Инициализировать список пуст группы
2. Для каждой задачи найти, если есть группа в списке групп с идентификатором или идентификатором любых зависимых задач
3. Если не добавить новая группа с идентификатором задачи и зависимых задач

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; 
 
}

Answer 4

Вы можете попробовать с моим кодом

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));