Group-Array von verschachtelten abhängigen Array-Element

Question

Ich habe einen Array-Speicher Task-Informationen. Jede Aufgabe hat auch ein Array von taskId, auf die es sich bezieht.

Eingangs

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

die erwartete Ausgabe ist Gruppierungs die alle je Aufgabe in einem Array für auf UI anzeigt.

Ausgabe

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

ich eine Funktion haben es zu tun, aber ich scheine wurde von hartcodiert falsch denken es. Hoffe, jemand kann mir helfen, es korrekt zu archivieren, indem ich reines JavaScript/TypeScript oder Underscore benutze, da wir es bereits im Projekt verwendet haben.

---

Bekannt: TaskId werden zufällige Zeichenfolge wie „5878465507b36e1f9c4c46fe“ sein

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

EINE ANDERE WEISE:

Hier ist eine optimierte Art und Weise, es zu tun, aber die Daten innerhalb inputArr wird danach verloren. Es wird indexCache nicht verwenden, um zu sehen, ob ein Index bereits behandelt wird oder nicht, stattdessen werden alle behandelten Elemente null in inputArr.Also, wenn Sie kümmern sich nicht oder wird inputArr danach nicht mehr verwenden, das statt:

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

Wenn Sie nicht über die order der Aufgaben in der gleichen Gruppe kümmern. Die Verwendung von union and find zur Implementierung einer disjoint set könnte eine Option sein.

Util Datenstruktur:

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

Dumb Datenquelle:

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

Treiberprogramm:

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

Anmerkung: wenn id zufällige Zeichenfolge in Ihrem Fall ist, einfach this.parent ändern Wenn Sie sich für die Reihenfolge interessieren (da es Abhängigkeitsbäume gibt), sollten Sie die Verwendung von 0 in Betracht ziehenstattdessen.

Answer 3

Die Lösung ist einfach,

1. leer Gruppenliste initialisieren
2. Für jede Aufgabe finden, wenn es eine Gruppe in der Gruppenliste ist eine mit der ID oder die ID aller abhängigen Aufgaben
3. Wenn nicht hinzufügen neue Gruppe mit Task-ID und abhängigen Aufgaben

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

Sie mit meinem Code versuchen können

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