2

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

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

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

4

2 回答 2

5

查看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']
于 2013-05-31T17:50:30.687 回答
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]

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

于 2013-05-31T17:55:40.387 回答