-1

我需要建立这棵树:

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是数组中的位置/索引

任何想法(在红宝石中首选)?

4

3 回答 3

3
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"]]]
于 2013-11-01T11:25:56.713 回答
0

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

  1. 找到 :tg 为 nil 的所有节点,然后得到 [t3, t7, t9]
  2. 在[t3, t7, t9] 中找到所有:tg 的节点,然后返回[t4, t8]
  3. 找到所有节点 :tg 在 [t4, t8] ...
于 2013-11-01T10:54:43.287 回答
0

使用递归(基于@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)
于 2013-11-01T11:17:10.657 回答