ruby - 从相关对象构建树

Question

我需要建立这棵树：

result = [
  ['t9'],
  ['t3',   
    ['t4'],
    ['t8',   
      ['t6'],
      ['t1',
        ['t5']
      ]
    ]
  ],
  ['t7',
    ['t2']
  ]
]

从这些对象：

{:id => 't1', :tg => 't8', :rank => 2}
{:id => 't2', :tg => 't7', :rank => 1}
{:id => 't3', :tg => nil, :rank => 2}
{:id => 't4', :tg => 't3', :rank => 1}
{:id => 't5', :tg => 't1', :rank => 1}
{:id => 't6', :tg => 't8', :rank => 1}
{:id => 't7', :tg => nil, :rank => 3}
{:id => 't8', :tg => 't3', :rank => 2}
{:id => 't9', :tg => nil, :rank => 1}

tg是自引用关联。 rank是数组中的位置/索引

任何想法（在红宝石中首选）？

Answer 1

def combine e, a
  a
  .inject([]){|a, h| a[h[:rank] - 1] = [h[:id]] if h[:tg] == e; a}
  .map{|e| e + combine(e.first, a)}
end

combine(nil, [
  {:id => 't1', :tg => 't8', :rank => 2},
  {:id => 't2', :tg => 't7', :rank => 1},
  {:id => 't3', :tg => nil, :rank => 2},
  {:id => 't4', :tg => 't3', :rank => 1},
  {:id => 't5', :tg => 't1', :rank => 1},
  {:id => 't6', :tg => 't8', :rank => 1},
  {:id => 't7', :tg => nil, :rank => 3},
  {:id => 't8', :tg => 't3', :rank => 2},
  {:id => 't9', :tg => nil, :rank => 1},
])
# => [["t9"], ["t3", ["t4"], ["t8", ["t6"], ["t1", ["t5"]]]], ["t7", ["t2"]]]

Answer 2

听起来你正在建造类似树的东西。该算法可以总结如下：

1. 找到 :tg 为 nil 的所有节点，然后得到 [t3, t7, t9]
2. 在[t3, t7, t9] 中找到所有:tg 的节点，然后返回[t4, t8]
3. 找到所有节点 :tg 在 [t4, t8] ...

Answer 3

使用递归（基于@cenyongh 的树概念）

def tree(arr,parent=nil)
    arr.select{|n| n[:tg] == parent}.
            sort_by{|n| n[:rank]}.
            map{|n| [n[:id]] +  tree(arr,n[:id])}
end

# call
tree(array_of_objects)