ruby 如何递归地将嵌套的散列扁平化为具有特定格式的数组的数组？

ckx4rj1h  于 2023-04-20  发布在  Ruby
关注(0)|答案(7)|浏览(93)

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

{
  '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
ruby

7条答案

按热度按时间
7cjasjjr

7cjasjjr1#

正如评论中所暗示的：
看起来很简单。递归地下降到散列，注意你在这个分支中访问的键。当你看到一个数组时，不需要进一步递归。将它附加到键列表并返回
跟踪很容易，只需将临时状态传递给参数中的递归调用。
我的意思是这样的：

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以返回一个现成的数组，而不是一个接一个地产生元素。

赞(0）分享  回复(0）举报  2023-04-20
sqserrrh

sqserrrh2#

你可以这样做：

def flat_hash(h)
  return [h] unless h.kind_of?(Hash)
  h.map{|k,v| flat_hash(v).map{|e| e.unshift(k)} }.flatten(1)
end

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

p flat_hash(input)

输出将是：

[
  ["a", "b", "c"], 
  ["a", "d", "e", "f"], 
  ["a", "d", "g", "h", "i", "j", "k"], 
  ["a", "l", "m", "n", "o", "p"], 
  ["q", "r", "s"]
]
赞(0）分享  回复(0）举报  2023-04-20
vm0i2vca

vm0i2vca3#

这当然需要一个递归的解决方案。下面的方法不会改变原始的哈希值。

编码

def recurse(h)
  h.each_with_object([]) do |(k,v),arr|
    v.is_a?(Hash) ? recurse(v).each { |a| arr << [k,*a] } : arr << [k,*v]
  end 
end

示例

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

说明

递归方法执行的操作总是很难解释。根据我的经验，最好的方法是用puts语句来增加代码。然而，这本身是不够的，因为当查看输出时，很难跟踪获得特定结果的递归级别，并将其传递给它本身或返回给它本身的一个版本。解决方案是缩进和取消缩进结果。请注意我构造代码的方式，我使用的几个辅助方法都是相当通用的，因此这种方法可以适用于检查其他递归方法执行的操作。

INDENT = 8
def indent; @col += INDENT; end
def undent; @col -= INDENT; end
def pu(s); print " "*@col; puts s; end
def puhline; pu('-'*(70-@col)); end 
@col = -INDENT
def recurse(h)
  begin
    indent
    puhline
    pu "passed h = #{h}"
    h.each_with_object([]) do |(k,v),arr|
      pu "  k = #{k}, v=#{v}, arr=#{arr}"
      if v.is_a?(Hash)
        pu "  calling recurse(#{v})"
        ar = recurse(v)
        pu "  return value=#{ar}"
        pu "  calculating recurse(v).each { |a| arr << [k,*a] }"
        ar.each do |a|
          pu "    a=#{a}"
          pu "    [k, *a] = #{[k,*a]}"
          arr << [k,*a]
        end
      else
        pu "  arr << #{[k,*v]}"
        arr << [k,*v]
      end
      pu "arr = #{arr}"
    end.tap { |a| pu "returning=#{a}" }
  ensure
    puhline
    undent
  end
end
recurse h
----------------------------------------------------------------------
passed h = {"a"=>{"b"=>["c"], "d"=>{"e"=>["f"], "g"=>["h", "i", "j", "k"]},
            "l"=>["m", "n", "o", "p"]}, "q"=>{"r"=>["s"]}}
  k = a, v={"b"=>["c"], "d"=>{"e"=>["f"], "g"=>["h", "i", "j", "k"]},
            "l"=>["m", "n", "o", "p"]}, arr=[]
  calling recurse({"b"=>["c"], "d"=>{"e"=>["f"], "g"=>["h", "i", "j", "k"]},
                   "l"=>["m", "n", "o", "p"]})
        --------------------------------------------------------------
        passed h = {"b"=>["c"], "d"=>{"e"=>["f"], "g"=>["h", "i", "j", "k"]},
                    "l"=>["m", "n", "o", "p"]}
          k = b, v=["c"], arr=[]
          arr << ["b", "c"]
        arr = [["b", "c"]]
          k = d, v={"e"=>["f"], "g"=>["h", "i", "j", "k"]}, arr=[["b", "c"]]
          calling recurse({"e"=>["f"], "g"=>["h", "i", "j", "k"]})
                ------------------------------------------------------
                passed h = {"e"=>["f"], "g"=>["h", "i", "j", "k"]}
                  k = e, v=["f"], arr=[]
                  arr << ["e", "f"]
                arr = [["e", "f"]]
                  k = g, v=["h", "i", "j", "k"], arr=[["e", "f"]]
                  arr << ["g", "h", "i", "j", "k"]
                arr = [["e", "f"], ["g", "h", "i", "j", "k"]]
                returning=[["e", "f"], ["g", "h", "i", "j", "k"]]
                ------------------------------------------------------
return value=[["e", "f"], ["g", "h", "i", "j", "k"]]
          calculating recurse(v).each { |a| arr << [k,*a] }
            a=["e", "f"]
            [k, *a] = ["d", "e", "f"]
            a=["g", "h", "i", "j", "k"]
            [k, *a] = ["d", "g", "h", "i", "j", "k"]
        arr = [["b", "c"], ["d", "e", "f"], ["d", "g", "h", "i", "j", "k"]]
          k = l, v=["m", "n", "o", "p"],
            arr=[["b", "c"], ["d", "e", "f"], ["d", "g", "h", "i", "j", "k"]]
          arr << ["l", "m", "n", "o", "p"]
        arr = [["b", "c"], ["d", "e", "f"], ["d", "g", "h", "i", "j", "k"],
               ["l", "m", "n", "o", "p"]]
        returning=[["b", "c"], ["d", "e", "f"], ["d", "g", "h", "i", "j", "k"],
                   ["l", "m", "n", "o", "p"]]
        --------------------------------------------------------------
  return value=[["b", "c"], ["d", "e", "f"], ["d", "g", "h", "i", "j", "k"],
                ["l", "m", "n", "o", "p"]]
  calculating recurse(v).each { |a| arr << [k,*a] }
    a=["b", "c"]
    [k, *a] = ["a", "b", "c"]
    a=["d", "e", "f"]
    [k, *a] = ["a", "d", "e", "f"]
    a=["d", "g", "h", "i", "j", "k"]
    [k, *a] = ["a", "d", "g", "h", "i", "j", "k"]
    a=["l", "m", "n", "o", "p"]
    [k, *a] = ["a", "l", "m", "n", "o", "p"]
arr = [["a", "b", "c"], ["a", "d", "e", "f"], ["a", "d", "g", "h", "i", "j", "k"],
       ["a", "l", "m", "n", "o", "p"]]
  k = q, v={"r"=>["s"]}, arr=[["a", "b", "c"], ["a", "d", "e", "f"],
    ["a", "d", "g", "h", "i", "j", "k"], ["a", "l", "m", "n", "o", "p"]]
  calling recurse({"r"=>["s"]})
        --------------------------------------------------------------
passed h = {"r"=>["s"]}
          k = r, v=["s"], arr=[]
          arr << ["r", "s"]
        arr = [["r", "s"]]
        returning=[["r", "s"]]
        --------------------------------------------------------------
  return value=[["r", "s"]]
----------------------------------------------------------------------
  calculating recurse(v).each { |a| arr << [k,*a] }
    a=["r", "s"]
    [k, *a] = ["q", "r", "s"]
arr = [["a", "b", "c"], ["a", "d", "e", "f"], ["a", "d", "g", "h", "i", "j", "k"],
       ["a", "l", "m", "n", "o", "p"], ["q", "r", "s"]]
returning=[["a", "b", "c"], ["a", "d", "e", "f"], ["a", "d", "g", "h", "i", "j", "k"],
           ["a", "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"]]
赞(0）分享  回复(0）举报  2023-04-20
jtw3ybtb

jtw3ybtb4#

这将返回一个包含所有路径的Array。

def paths(element, path = [], accu = [])
  case element
  when Hash
    element.each do |key, value|
      paths(value, path + [key], accu)
    end
  when Array
    accu << (path + element)
  end
  accu
end

为了更好的打印你可以做

paths(tree_def).map { |path| path.join(".") }
赞(0）分享  回复(0）举报  2023-04-20
pgccezyw

pgccezyw5#

请看下面的代码，它会一直递归地调用，直到到达数组值。
这个递归调用会有多个分支，op应该是每个分支的单独副本，所以我使用了string，它总是在这里作为一个新对象创建，否则数组就像使用通过引用调用

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

@output = []

def nested_array(h, op='')
  h.map do |k,v|
    if Hash === v
      nested_array(v, op+k)
    else
      @output << (op+k+v.join).chars
    end
  end
end

nested_array(hash)

@output将是您想要的数组。

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

**更新：**键值对可以多于一个字符，所以下面的nested_array方法可能会更好。

def nested_array(h, op=[])
  h.map do |k,v|
    if Hash === v
      nested_array(v, Array.new(op) << k)
    else
      @output << ((Array.new(op) << k) + v)
    end
  end
end
赞(0）分享  回复(0）举报  2023-04-20
2j4z5cfb

2j4z5cfb6#

这里所有的解都是递归的，下面是一个非递归的解。

def flatten(input)
  sol = []
  while(input.length > 0)
    unprocessed_input = []
    input.each do |l, r|
      if r.is_a?(Array)
        sol << l + r
      else
        r.each { |k, v| unprocessed_input << [l + [k], v] }
      end
    end
    input = unprocessed_input
  end
  return sol
end
flatten([[[], h]])

代码说明：

  • 数组形式的哈希是[[k1，v1]，[k2，v2]]。
  • 当input_hash以上述形式呈现时，[[]，{ a：{..} }]，可以生成这种形式的partial_solutions [ [a]，{..} ]。索引“0”保存部分解，索引“1”保存尚未处理的输入。
  • 由于这种格式很容易将partial_solutionMap到未处理的输入并累积未处理的输入，因此将input_hash转换为这种格式会导致，[]，input_hash

解决方案：

[["a", "b", "c"], ["a", "l", "m", "n", "o", "p"], ["q", "r", "s"], ["a", "d", "e", "f"], ["a", "d", "g", "h", "i", "j", "k"]]
赞(0）分享  回复(0）举报  2023-04-20
pu3pd22g

pu3pd22g7#

我需要一个与此类似的解决方案。在我的用例中，我希望任何数组都能与之前的“路径”进行置换。我希望编写一些简洁的结构，可以表示“路径”（不一定是文件路径，但可能是消息路由路径），并在需要时进行扩展。一个简单的例子是

hash2 = {"a"=>{"b"=>["c", "d"]}}
expand_structure(hash2)
# [["a", "b", "c"], ["a", "b", "d"]]

我想到的解决方案在下面。

def expand_structure(o, path=[])
  case o
  when Hash
    o.inject([]) do |collector, (k, v)|
      collector += expand_structure(v, path + [k])
    end
  when Array
    o.map { |e| expand_structure(e, path) }
  else # unstructured "value"
    path + [o]
  end
end

也就是说，如果你想保持你的数组平坦，而不是在它们上面进行置换，你可以修改上面的内容，不再递归，只返回附加到路径上的数组。

def expand_structure2(o, path=[])
  case o
  when Hash
    o.inject([]) do |collector, (k, v)|
      collector += expand_structure2(v, path + [k])
    end
  when Array
    [path + o]
  else # unstructured "value"
    path + [o]
  end
end

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

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

# => true

注意：我还没有决定方法的名字;很明显，在一天结束的时候，这取决于程序员，但这是一个有趣的问题，在某种意义上，结构是膨胀的，而在另一些意义上，它是扁平的。

赞(0）分享  回复(0）举报  2023-04-20
我来回答

相关问题

    查看更多

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新问答

    更多
    • 蜀ICP备2022004421号-2 NULL123 https://www.null123.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com