ruby - 如何以递归方式将嵌套散列展平为具有特定格式的数组？

Question

我有一个看起来像这样的嵌套哈希:

{
  'a' => {
    'b' => ['c'],
    'd' => {
      'e' => ['f'],
      'g' => ['h', 'i', 'j', 'k']
    },
    'l' => ['m', 'n', 'o', 'p']
  },
  'q' => {
    'r' => ['s']
  }
}

散列可以有更多的嵌套，但最后一层的值总是数组。

我想将散列“扁平化”为一种格式，在该格式中我得到一个数组数组，代表所有键和值，这些键和值构成嵌套散列的整个“路径/分支”，从最低级别的值到哈希的顶部。这有点像从底部开始向上遍历“树”，同时在途中收集键和值。

特定哈希的输出应该是:

[
  ['a', 'b', 'c'],
  ['a', 'd', 'e', 'f'],
  ['a', 'd', 'g', 'h', 'i', 'j', 'k'],
  ['a', 'l', 'm', 'n', 'o', 'p'],
  ['q', 'r', 's']
]

我尝试了很多不同的方法，但到目前为止没有任何效果。再次记住，可能会出现比这些更多的级别，因此解决方案必须是通用的。

注意:数组的顺序和其中元素的顺序并不重要。

我做了以下，但它并没有真正起作用:

tree_def = {
  'a' => {
    'b' => ['c'],
    'd' => {
      'e' => ['f'],
      'g' => ['h', 'i', 'j', 'k']
    },
    'l' => ['m', 'n', 'o', 'p']
  },
  'q' => {
    'r' => ['s']
  }
}
branches = [[]]

collect_branches = lambda do |tree, current_branch|
  tree.each do |key, hash_or_values|
    current_branch.push(key)
    if hash_or_values.kind_of?(Hash)
      collect_branches.call(hash_or_values, branches.last)
    else # Reached lowest level in dependency tree (which is always an array)
      # Add a new branch
      branches.push(current_branch.clone)
      current_branch.push(*hash_or_values)
      current_branch = branches.last
    end
  end
end

collect_branches.call(tree_def, branches[0])

branches #=> wrong result

Answer 1

正如评论中所暗示的:

Looks pretty straightforward. Descend into hashes recursively, taking note of keys you visited in this branch. When you see an array, no need to recurse further. Append it to the list of keys and return

Tracking is easy, just pass the temp state down to recursive calls in arguments.

我的意思是这样的:

def tree_flatten(tree, path = [], &block)
  case tree
  when Array
    block.call(path + tree)
  else
    tree.each do |key, sub_tree|
      tree_flatten(sub_tree, path + [key], &block)
    end
  end
end

tree_flatten(tree_def) do |path|
  p path
end

此代码只是打印每个扁平化路径，但您也可以将其存储在数组中。或者甚至修改 tree_flatten 以返回一个准备好的数组，而不是一个一个地生成元素。