Array von Arrays in eine Kombination aus Arrays und Hashes konvertieren

Question

Ich habe versucht, ein Array von Arrays in eine Kombination aus Arrays und Hashes zu konvertieren. Lassen Sie mich erklären, was ich zu erreichen versuche:

Eingang:

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

Erwartete Ausgabe:

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

Was ich mit so weit gekommen sind ist :

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 

und es gibt mir das folgende Ergebnis:

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

Kann jemand etwas Licht werfen, so dass ich dieses Problem lösen kann. Gibt es einen Namen für dieses Problem, direkte Graph/indirekte Graph/Graph-Theorie? Ich bin bereit, mein Wissen über Graphen und Bäume zu studieren und zu verbessern.

Ich würde es schätzen, wenn Sie mir helfen, das zu lösen, oder mir einige Anweisungen geben, wie man das löst.

Danke.

Answer 1

Es sieht einem Trie sehr ähnlich. , Aber es kann leicht modifiziert werden, um akzeptiert ein Array von Strings (%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 

Es gibt:

Diese Struktur wird in der Regel mit Strings (%w(a p p l e)'apple', gesehen als Array von Zeichen) verwendet:

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]