arrays - 在 Ruby 中使用 TSort 对数组重新排序和排序

Question

希望我能在 Ruby 中的这个特定的重新排序/排序问题上得到一些帮助。

我有一个数组数组，像这样:

[['b', 'f'],
['f', 'h'],
['a', 'e'],
['b', 'c'],
['b', 'd'],
['e', 'g'],
['c', 'f'],
['d', 'f'],
['f', 'g'],
['g', 'h']]

每个数组中的第二个元素必须出现在第一个元素之后，所以我想编写一个程序将它们排序成一个如下所示的数组:

['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h']

我正在尝试使用 Ruby 内置的 TSort 库，我也在使用 this stack overflow post .

所以我这样做:

class Hash
  include TSort
  alias tsort_each_node each_key
  def tsort_each_child(node, &block)
    fetch(node).each(&block)
  end
end

def flex_sort(arr)
  stuff = arr.map do |head, *tail|
    {head => tail}
  end
  stuff.reduce(&:merge).tsort.reverse
end

sorted = flex_sort(flex)

关于这个我有几个问题。首先，我是否走在正确的轨道上？其次，当我运行这段代码时，你会注意到数组的初始数组不包括第一个元素为 'h' 的数组，因此当我将它们转换为散列并尝试运行 .tsort，我得到类似 key 'h' does not exist 的信息，这迫使我将 ['h'] 放入数组数组只是为了它不会破坏。有解决办法吗？

Answer 1

fetch如果第二个参数不存在，则采用默认值。

fetch(node, []).each(&block)

第二个问题是，当您&:merge 数组彼此时，您将覆盖以前的值。当前合并结果为

{"b"=>["d"], "f"=>["g"], "a"=>["e"], "e"=>["g"], "c"=>["f"], "d"=>["f"], "g"=>["h"]}

每个键只有一个值。如果你把它改成

def flex_sort(arr)
  stuff = Hash.new { |hash, key| hash[key] = [] }
  arr.each do |head, tail|
    stuff[head] << tail
  end

  stuff.tsort.reverse
end

你的哈希看起来像

{"b"=>["f", "c", "d"], "f"=>["h", "g"], "a"=>["e"], "e"=>["g"], "c"=>["f"], "d"=>["f"], "g" =>["h"]}

现在运行你的 tsort 你最终会得到

["a", "e", "b", "d", "c", "f", "g", "h"]

这与您想要的非常接近。不熟悉这种类型，不知道是否有办法在存在多种可能性时强制它在其他键之前选择一些键。但这至少让你们更亲近了。