严重卡在Ruby数组重新排序上 [英] Seriously stuck on Ruby array reordering

问题描述

我需要根据相关元素对数组重新排序.如果元素是数组(具有依赖项)，则该数组的第二个元素是依赖项，并且必须位于该数组之前.然后，由于不再需要所有依赖项信息，因此将其删除，并返回具有正确顺序的数组.

I need to reorder an array based on dependent elements. If an element is an array (has dependency), the second element of that array is the dependency, and will be required to come before that array. All dependency information is then removed as we don't need any more, and we return an array with corrected order.

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

这是我认为设计过度的方法:

Here is my approach which I think is over-engineered:

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:

The obvious problem with the above is that as I iterate through the array, elements which have dependencies I haven't processed will be shifted back, yet the loop will only be performed once. So, I introduced a while:

while array1.flatten.count > array1.count

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

我还受命测试自引用和循环(无限)依赖性循环.我应该使用枚举器吗?我是否应该将数组转换为不同的结构(对象)以简化订单管理?

I have also been tasked to test for self-referential and circular (infinite) dependency loops. Should I have used an Enumerator? Should have I converted array to different structure (objects) to enable easier management of order?

推荐答案

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

Check out TSort, which comes with the Ruby standard library.

它执行拓扑排序，听起来像您所需要的.使用上面的示例:

It performs a topological sort, which sounds like what you need. Using your example above:

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

这篇关于严重卡在Ruby数组重新排序上的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！