严重依赖Ruby数组重新排序

我需要根据依赖元素重新排序数组。 如果一个元素是一个数组（具有依赖性），那么该数组的第二个元素是依赖项，并且需要在该数组之前。 然后删除所有依赖关系信息，因为我们不再需要，我们返回一个更正顺序的数组。

# array1 = [['a'], ['b','c'], ['c','a']] # ordered = ['a', 'c', 'b'] # logic: c comes before b, a comes before c 

以下是我认为过度设计的方法：

 array1.each_with_index do |ar, i| # ignore elements without dependencies if ar.count > 1 # get dependency dep = ar[1] # get index for element where this dependency is first dep_index = array1.index { |a| a.first == dep } # remove found dependency and store dep_element = array1.delete_at(dep_index) # insert found dependency to before current element array1.insert(i, dep_element) # delete processed dependency ar.delete(dep) end end 

上面的明显问题是，当我遍历数组时，具有我尚未处理的依赖关系的元素将被移回，但循环将仅执行一次。 所以，我介绍了一段while ：

 while array1.flatten.count > array1.count 

但是，我的结果是['c', 'a', 'b'] 。

我还负责测试自引用和循环（无限）依赖循环。 我应该使用一个枚举器吗？ 我应该将数组转换为不同的结构（对象），以便更轻松地管理订单吗？

Answer 1

查看带有Ruby标准库的TSort 。

它执行拓扑排序，听起来像你需要的。 使用上面的示例：

 require 'tsort' class Hash include TSort alias tsort_each_node each_key def tsort_each_child(node, &block) fetch(node).each(&block) end end def deps arr arr.map { |head, *tail| {head => tail} }.reduce(&:merge).tsort end deps [['a'], ['b','c'], ['c','a']] #=> ['a', 'c', 'b'] 

Answer 2

无需重新发明轮子，使用Rake：

 require 'rake' ary = [[:a], [:b, :c], [:c, :a]] ordered = [] ary.each { |head, *tail| task head => tail do ordered << head end } task( main: ary.map( &:first ) ).invoke ordered #=> [:a, :c, :b] 

否则，有一个算法，但我忘了它的名字。