JavaScript中的高級數組和循環

Question

我正在嘗試編寫一個涉及數組的複雜函數。這個問題涉及一個（假想的）軟件包安裝程序，每個軟件包包含0或1個依賴項。任務是按順序排列軟件包和依賴項，以便安裝成功。

函數應該接受一個定義依賴關係的字符串數組。每個字符串都包含一個包的名稱，後跟一個冒號和空格，然後包含該包所需的任何依賴項。該程序應該按照安裝順序輸出一個以逗號分隔的軟件包名稱列表，以便軟件包的依賴性始終位於該軟件包之前。

例如，

['KittenService: ','Leetmeme: Cyberportal','Cyberportal: Ice','CamelCaser: KittenService','Fraudstream: Leetmeme','Ice: '] 

輸入應輸出

'KittenService, Ice, Cyberportal, Leetmeme, CamelCaser, Fraudstream' 

我已經得到了函數向下的基本步驟等反轉包和依賴性的順序和消除結腸。但是，當涉及到像上述那樣更復雜的系統時，我遇到了麻煩。誰能幫我？

Answer 1

這個想法是形成一個directed acyclic graph (DAG)然後在圖上執行一個topological sorting。下面我的解決方案並不真正形成適當的DAG，但它使用depth-first search進行拓撲排序。它適用於你的情況。但是，這不適用於所有情況，但您可以使用上述兩個想法來創建自己的完美版本。

var input = [ 
 
    'KittenService: ', 
 
    'Leetmeme: Cyberportal', 
 
    'Cyberportal: Ice', 
 
    'CamelCaser: KittenService', 
 
    'Fraudstream: Leetmeme', 
 
    'Ice: ' 
 
]; 
 
var dependencies = {}; 
 
var result = []; 
 

 
// Form the dependency graph 
 
for (var i = 0; i < input.length; i += 1) { 
 
    var inputSplit = input[i].split(':'); 
 
    var key = inputSplit[0].trim(); 
 
    var value = inputSplit[1].trim(); 
 
    dependencies[key] = value; 
 
} 
 

 
// Depth-first search 
 
for (var key in dependencies) { 
 
    if (dependencies.hasOwnProperty(key)) { 
 
    visit(key); 
 
    } 
 
} 
 

 
function visit(key) { 
 
    if (!dependencies.hasOwnProperty(key)) { 
 
    return; 
 
    } 
 

 
    if (dependencies[key] !== '') { 
 
    visit(dependencies[key]); 
 
    } 
 

 
    result.push(key); 
 
    delete dependencies[key]; 
 
} 
 

 
console.log(result);

Answer 2

這裏是我的方式來解決這個問題，我的想法是找到使用迭代的依賴關係。看看註釋代碼

function dependencies(inputPackages){ 
 
    // the final list of packages 
 
    var packages = [] 
 

 
    // list of packages there having a dependency 
 
    var packagesWithDependency = []; 
 

 
    inputPackages.forEach(function(package){ 
 
     package = package.split(": "); // seperate package and dependency 
 
     if(package[1] === ""){ // package has no dependencies, append it directly to list of packages 
 
      packages.push(package[0]) 
 
     }else{ // package has a dependency, save it for later 
 
      packagesWithDependency.push({ 
 
       package: package[0], 
 
       dependencie: package[1] 
 
      }) 
 
     } 
 
    }) 
 

 
    // while there are unresolved packages 
 
    while(packagesWithDependency.length > 0){ 
 
     // we need this to check if there was found a package in this iteration 
 
     var packageWithDependencyCount = packagesWithDependency.length; 
 

 
     packagesWithDependency.forEach(function(packageWithDependency, index, object){ 
 
      // if the dependencies for a package is found in the packages list, then add the new package, and remove it from the packagesWithDependency list 
 
      if(packages.indexOf(packageWithDependency.dependencie) >= 0){ 
 
       packages.push(packageWithDependency.package); 
 
       object.splice(index, 1); 
 
      } 
 
     }) 
 
     
 
     // if no package was resolved in this iteration, then return false, the input requires a package there wasn't specified 
 
     if(packagesWithDependency.length == packageWithDependencyCount){ 
 
      return false; 
 
     } 
 
    } 
 

 

 
    // return packages // if you want the array instead 
 
    return packages.join(", ") 
 
} 
 

 
console.log(dependencies(['KittenService: ','Leetmeme: Cyberportal','Cyberportal: Ice','CamelCaser: KittenService','Fraudstream: Leetmeme','Ice: '])) 
 
console.log(dependencies(['KittenService: ','Leetmeme: Unknown package']))

該解決方案可以擴展到處理多依賴。

Answer 3

Array.sort會帶來奇蹟過了，它使你的代碼更加簡練：

function orderByDependency(input) { 
 
    return input.map(function(str, i) { 
 
    return { 
 
     dependency: str.split(': ')[1] ? str.split(': ')[1] : false, 
 
     name: str.split(': ')[0] 
 
    }; 
 
    }).sort(function(a, b) { 
 
    return b.dependency === false || a.dependency == b.name; 
 
    }); 
 
} 
 

 
document.body.innerHTML = orderByDependency([ 
 
    'KittenService: ', 
 
    'Leetmeme: Cyberportal', 
 
    'Cyberportal: Ice', 
 
    'CamelCaser: KittenService', 
 
    'Fraudstream: Leetmeme', 
 
    'Ice: ' 
 
]).map(function(pkg) { 
 
    return '<div> Loading ' + pkg.name + '...<hr></div>'; 
 
}).join('');