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