Skip to content

Instantly share code, notes, and snippets.

@shadabahmed
Last active December 16, 2015 04:59
Show Gist options
  • Save shadabahmed/5381574 to your computer and use it in GitHub Desktop.
Save shadabahmed/5381574 to your computer and use it in GitHub Desktop.
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