Let's start with an example.
binary tree, internal node is addition
four bits for the leaves, 1=1, 0=x
two bits to encode balance: right, left, center == 00, ignore==11
seven bits to encode inverses: 1 -> that edge has an inverse
=> initially 3 * 2^11 possibilities == 6144, but...
exclude left-heavy forms (10) (now just need one bit == unbalanced)
for right-heavy forms (10), exclude left-heavy leaves: bb01 == bb10
for balanced forms (00),
- there is only one unique 1-bit and 3-bit leaf pattern: 0001, 1110
- there are only two unique 2-bit patterns: 1001, 1100
exclude inverses of 1-leaves: 1/1 == 1
=> Algorithm:
(unbalanced)
for all integers n in 0 - 2^4
if n != bb10
for all integers m in 0 - 2^7
if m has 0s where n has 1s
generate expression
(balanced)
for all integers n in { 0000, 1000, 1001, 1100, 1110, 1111 }
for all integers m in 0 - 2^7
if m has 0s where n has 1s
generate expressionThere are three kinds of leaves, $1$, $x$, and $1/x$. There are two kinds of interior nodes, $a+b$ and$1/(a+b)$.
In [30]:
class Node(object):
def __eq__( self, other ):
return (isinstance(other, self.__class__)
and self.__dict__ == other.__dict__)
def __str__( self ):
return u""
class One(Node):
def __hash__( self ):
return 1;
def __str__( self ):
return "1"
class X(Node):
def __hash__( self ):
return 2;
def __str__( self ):
return "x"
class InverseX(Node):
def __hash__( self ):
return 3;
def __str__( self ):
return "1/x"
class Sum(Node):
def __init__( self, left, right ):
self.left = left
self.right = right
def __hash__( self ):
return 5 * self.left.__hash__() * self.right.__hash__();
def __eq__( self, other ):
if isinstance( other, self.__class__ ):
if self.__dict__ == other.__dict__ :
return True
elif ( self.left == other.right ) and ( self.right == other.left ):
return True
else:
return False
else:
return False;
def __str__( self ):
return "(" + str(self.left) + "+" + str(self.right) + ")"
class InverseSum(Sum):
def __hash__( self ):
return 7 * self.left.__hash__() * self.right.__hash__();
def __str__( self ):
return "1/(" + str(self.left) + "+" + str(self.right) + ")"
def factory( i ):
if i == 1:
return One()
if i == 2:
return X()
return InverseX()
def addUnique( s, e ):
if not e in s:
print "NEW " + str(e)
s .add( e )
exprs = set()
for a in range(3):
for b in range(3):
for c in range(3):
for d in range(3):
ae = factory(a)
be = factory(b)
ce = factory(c)
de = factory(d)
addUnique( exprs, InverseSum( Sum( ae, be ), Sum( ce, de ) ) )
addUnique( exprs, InverseSum( Sum( ae, be ), InverseSum( ce, de ) ) )
addUnique( exprs, InverseSum( InverseSum( ae, be ), Sum( ce, de ) ) )
addUnique( exprs, InverseSum( InverseSum( ae, be ), InverseSum( ce, de ) ) )
In [ ]: