A tree for creating parenthesis permutation
require 'graphviz' | |
class LeveledBinaryTree | |
Node = Struct.new(:weight, :str, :left, :right) | |
attr_accessor :levels, :root | |
def initialize(clear_last_level = true) | |
@root = Node.new(1, '(') | |
@levels = {0 => [@root]} | |
@clear_last_level = clear_last_level | |
end | |
def construct(n) | |
@max_level = 2*n - 1 | |
1.upto(@max_level - 1).each do |current_level| | |
@levels[current_level] = [] | |
@levels[current_level - 1].each do |node| | |
@levels[current_level] << node.left = Node.new(node.weight + 1, node.str + '(') if node_possible?(current_level, node.weight + 1) | |
@levels[current_level] << node.right = Node.new(node.weight - 1, node.str + ')') if node_possible?(current_level, node.weight - 1) | |
end | |
@levels[current_level - 1] = nil if @clear_last_level | |
end | |
end | |
def last_level | |
@levels[@max_level - 1] | |
end | |
def draw | |
GraphViz::new( :G, :type => :'strict digraph', :ordering =>"out" ) do |g| | |
0.upto(@max_level - 1).each do |current_level| | |
@levels[current_level].each do |node| | |
cur_node = g.find_node(node.object_id.to_s) || g.add_nodes(node.object_id.to_s, :label => "#{node.str} -> #{node.weight}") | |
[[node.left, "left"], [node.right, "right"]].each do |child, label| | |
next unless child | |
child_node = g.add_nodes(child.object_id.to_s, :label => "#{child.str} -> #{child.weight}") | |
g.add_edges(cur_node, child_node, :label => label, :sametail => '1') | |
end | |
end | |
end | |
end.output( :png => 'wac8.png' ) | |
end | |
private | |
def node_possible?(current_level, weight) | |
weight >= 0 && weight <= (@max_level - current_level) | |
end | |
end | |
tree = LeveledBinaryTree.new(false) | |
tree.construct(3) | |
tree.draw | |
tree.last_level.each{|x| puts x.str + ')'} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment