ruby - 严重卡在 Ruby 数组重新排序上

Question

我需要根据相关元素对数组重新排序。如果一个元素是一个数组(具有依赖性)，则该数组的第二个元素是依赖性，并且需要位于该数组之前。然后删除所有依赖信息，因为我们不再需要了，我们返回一个顺序正确的数组。

# 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

查看 TSort ，它与 Ruby 标准库一起提供。

它执行拓扑排序，这听起来正是您所需要的。使用上面的示例:

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