Implementation of Barrington's theorem. Convert's circuit to a group program and then runs it to show the truth table according to the group program

barrington.py

# Author: P. R. Vaidyanathan
# Examples at the end of document

class Permutation(list):
    """
    Represents a permutation and supports inverse, composition,
    multiplication using * operator, action on set (through calling),
    cycle decomposition and cycle to cycle conversion
    """

    def __init__(self, map_to):
        self.to = list(map_to)
        self.n = len(self.to)
        list.__init__(self,self.to)
        self._inv = None

    def __call__(self, l):
        try:
            return Permutation([l[e] for e in self.to])
        except TypeError:
            l = list(l)
            return Permutation([l[e] for e in self.to])

    def compose(self, p2):
        return self(p2.to)

    def __mul__(self, p2):
        return self.compose(p2)

    @property
    def inv(self):
        if not self._inv:
            res = [-1]*self.n
            for i in range(self.n):
                res[self.to[i]] = i
            self._inv = Permutation(res)
        return self._inv

    def comm(self, p2):
        cyc1 = self.decompose()
        cyc2 = Permutation(p2).decompose()
        assert len(cyc1) == 1, "self not a single cycle"
        assert len(cyc2) == 1, "other not a single cycle"
        return Permutation(y for x,y in sorted(zip(cyc1[0], cyc2[0])))
        #return Permutation(y for x,y in sorted(zip(p2, self.to)))

    def decompose(self):
        cycles = []
        visited = [False]*self.n
        for start in range(self.n):
            if visited[start]: continue
            visited[start] = True
            cur_cyc = [start]
            cur = self.to[start]
            while True:
                if cur == start:
                    cycles.append(cur_cyc)
                    break
                else:
                    visited[cur] = True
                    cur_cyc.append(cur)
                    cur = self.to[cur]
        return cycles

def make_wreath(inners, outer, debug=False):
    """
    Construct a permutation which is a wreath product of a list of permutations (inners)
    and an outer permutation
    """
    dom = len(inners[0])
    assert len(outer) == len(inners), "outer permutation mismatch with inner permutations"
    assert all(len(i)==dom for i in inners), "inner permutation degrees different"
    innerps = [Permutation(ip)(range(dom*i,dom*i+dom)) for i,ip in enumerate(inners)]
    if debug:print innerps
    final = []
    for i in Permutation(outer):
        final.extend(innerps[i])
    if debug:print final
    return Permutation(final)


class Circuit(object):
    """
    Represents abstract tree, used to hold expressions
    Modified from: https://www.geeksforgeeks.org/expression-tree/
    """

    def __init__(self , value):
        self.value = value
        self.left = None
        self.right = None

    def __str__(self):
        s = ""
        braces = bool(self.left or self.right)
        s += "("*braces
        if self.left:s += str(self.left)
        s += str(self.value)
        if self.right:s += str(self.right)
        s += ")"*braces
        return s

def make_circuit(postfix, unary="-", binary="+*"):
    """
    Parse postfix expression (from space-separated string) to
    construct an expression tree
    Accepts strings of binary of unary operator symbols
    Modified from: https://www.geeksforgeeks.org/expression-tree/
    """
    stack = []
    for char in postfix.split() :
        if char in binary:
            t = Circuit(char)
            # Pop two top nodes
            t1 = stack.pop()
            t2 = stack.pop()
            t.right = t1
            t.left = t2
            stack.append(t)
        elif char in unary:
            t = Circuit(char)
            t1 = stack.pop()
            t.right = t1
            stack.append(t)
        else:
            t = Circuit(char)
            stack.append(t)
    t = stack.pop()
    return t

# postfix = "x1 x2 + y2 f * g * -"
# r = make_circuit(postfix, "", "+*-")
# print "Infix expression is", r

class GroupProgram(object):
    """
    Represents a Group Program (see Barrington's Theorem).
    Supports appending instructions of the form (var, g, h). Also supports
    running the program by providing the variable values either as dict
    or keyword arguments.
    """

    def __init__(self, degree=5, instrs=[]):
        self.instr = []
        self.degree = degree
        if instrs:
            for var, g, h in instrs: self.append(var, g, h)

    def append(self, var, g, h):
        assert isinstance(g,Permutation), "g must be permutation object"
        assert isinstance(h,Permutation), "h must be permutation object"
        self.instr.append((var, g, h))

    def __str__(self):
        s = ""
        for var, g, h in self.instr:
            s += "<{},{},{}>\t".format(var, g, h)
        return s.strip()

    def run(self, valdict={}, **kwargs):
        res = Permutation(range(self.degree))
        valdict.update(kwargs)
        for var, g, h in self.instr:
            if valdict[var]:
                res = res*g
            else:
                res = res*h
        return res

def adjust(el, rho, pre=True):
    """
    Adjust an instruction of a group program by (pre|post)multiplying
    both g and h by given permutation
    """
    var, g, h = el
    if pre:
        return (var, rho*g, rho*h)
    else:
        return (var, g*rho, h*rho)
        
def circuit2gp(circuit, alpha):
    """
    Construct a Group Program which alpha-evaluates the given circuit
    (See Barrington's Theorem)
    """
    g = Permutation([1,2,3,4,0])
    h = Permutation([2,0,4,1,3])
    e = Permutation(range(5))
    val = circuit.value
    if val not in "^v-":
        if val == "1":
            return [("x1", alpha, alpha)]
        elif val == "0":
            return [("x1", e, e)]
        else:
            return [(val, alpha, e)]
    elif val == "-": # NOT gate
        p_ = circuit2gp(circuit.right, alpha.inv)
        return p_ + [("x1", alpha, alpha)]
    elif val == "v":  # OR gate
        new_c = Circuit("-") # apply DeMorgan's law
        new_c.right = Circuit("^")
        new_c.right.left = Circuit("-")
        new_c.right.left.right = circuit.left
        new_c.right.right = Circuit("-")
        new_c.right.right.right = circuit.right
        return circuit2gp(new_c, alpha)
    else: # assume AND gate (^)
        p1  = circuit2gp(circuit.left, g)
        p2  = circuit2gp(circuit.right, h)
        p1_ = circuit2gp(circuit.left, g.inv)
        p2_ = circuit2gp(circuit.right, h.inv)
        rho = alpha.comm(g*h*g.inv*h.inv)
        p1[0] = adjust(p1[0], rho, pre=True)
        p2_[-1] = adjust(p2_[-1], rho.inv, pre=False)
        return p1 + p2 + p1_ + p2_

def test_gp(gp, varnames):
    """
    Test given Group Program by tabulating all possible values
    """
    numvar = len(varnames)
    print "|\t".join(varnames + ["output"])
    for i in range(2**numvar):
        bits = bin(i)[2:].zfill(numvar)
        varvals = dict(zip(varnames, map(int,bits)))
        #print varvals
        print " |\t".join(bits),"|\t",
        print gp.run(varvals)
        
### Usage

my_cyc = Permutation([1,3,0,4,2])
c = make_circuit("x1 1 ^ x2 - ^", "-", "^")
gp = GroupProgram(degree=5, instrs=circuit2gp(c, my_cyc))
print gp
print c
test_gp(gp, ["x1", "x2"])

c = make_circuit("x1 1 ^", "-", "^")
gp = GroupProgram(degree=5, instrs=circuit2gp(c, my_cyc))
print gp
print c
test_gp(gp, ["x1"])

c = make_circuit("x1 1 v", "-", "^v")
gp = GroupProgram(degree=5, instrs=circuit2gp(c, my_cyc))
print gp
print c
test_gp(gp, ["x1"])

c = make_circuit("x1 x2 v", "-", "v")
gp = GroupProgram(degree=5, instrs=circuit2gp(c, my_cyc))
print gp
print c
test_gp(gp, ["x1", "x2"])