配列の配列を配列とハッシュの組み合わせに変換する

Question

配列の配列を配列とハッシュの組み合わせに変換しようとしています。私は私が達成しようとしているかを説明してみましょう：

入力：

[['a'], ['b'], ['a', 'b', 'c'], ['a', 'b', 'd']] 

予想される出力：

[:a => [{:b => [:c, :d]}], :b] 

私はそう遠いが出ている何：

def converter(array) 
    tree_hash = {} 

    array.each do |path| 
    path.each_with_index.inject(tree_hash) do |node, (step, index)| 
     step = step.to_sym 

     if index < path.size - 1 
     node[step] ||= {} 
     else 
     node[step] = nil 
     end 
    end 
    end 

    tree_hash 
end 

、それは私に次のような結果得られます。

converter([['a'], ['b'], ['a', 'b', 'c'], ['a', 'b', 'd']]) 
=> {:a=>{:b=>{:c=>nil, :d=>nil}}, :b=>nil} 

私はこの問題を解決することができるように、誰もがいくつかの光を投げることができるし。この問題の名前はありますか？直接グラフ/間接グラフ/グラフ理論ですか？私はグラフや樹木に関する知識を勉強して改善したいと思っています。

これを解決するのを手伝ったり、解決方法を教えていただければ幸いです。

ありがとうございました。

Answer 1

Trieとよく似ています。

この構造は、通常（'apple'、文字の配列として見：%w(a p p l e)）文字列で使用され、容易にストリング（%w(bar car)）の配列を受け入れるように変更することができる。

class Node 
    attr_reader :key, :children 
    def initialize(key, children = []) 
    @key = key 
    @children = children 
    end 

    def to_s 
    key.to_s 
    end 

    def to_sym 
    key.to_sym 
    end 
end 

class Trie 
    attr_reader :root 
    def initialize 
    @root = Node.new('') 
    end 

    def self.from_array(array) 
    array.each_with_object(Trie.new) { |letters, trie| trie.add(letters) } 
    end 

    def add(letters) 
    node = root 
    letters.each do |c| 
     next_node = node.children.find { |child| child.key == c } 
     if next_node 
     node = next_node 
     else 
     next_node = Node.new(c) 
     node.children.push(next_node) 
     node = next_node 
     end 
    end 
    end 

    def show(node = root, indent = 0) 
    puts ' ' * indent + node.to_s 
    node.children.each do |child| 
     show(child, indent + 1) 
    end 
    end 

    def to_arrays_and_hashes 
    recursive_to_arrays_and_hashes(root)[root.to_sym] 
    end 

    private 

    def recursive_to_arrays_and_hashes(node) 
    if node.children.empty? 
     node.to_sym 
    else 
     {node.to_sym => node.children.map{|c| recursive_to_arrays_and_hashes(c)}} 
    end 
    end 
end 

array1 = [['a'], ['b'], ['a', 'b', 'c'], ['a', 'b', 'd']] 
array2 = [['foo'], ['bar', 'car']] 

[array1, array2].each do |array| 
    trie = Trie.from_array(array) 
    trie.show 
    p trie.to_arrays_and_hashes 
end 

が返します。

a 
    b 
     c 
     d 
    b 
[{:a=>[{:b=>[:c, :d]}]}, :b] 

    foo 
    bar 
    car 
[:foo, {:bar=>[:car]}] 

Answer 2

def group_by_prefix(elements) 
    elements.group_by(&:first).map do |prefix, elements| 
    remainders = elements.map { |element| element.drop(1) }.reject(&:empty?) 

    if remainders.empty? 
     prefix.to_sym 
    else 
     {prefix.to_sym => group_by_prefix(remainders)} 
    end 
    end 
end 

foo = [['a'], ['b'], ['a', 'b', 'c'], ['a', 'b', 'd']] 
group_by_prefix(foo) # => [{:a=>[{:b=>[:c, :d]}]}, :b]