Determine sets of associatively equivalent permutations of commutative operations

Question

There are many types of binary operations, which can be categorized by their associative properties and their commutative properties.

• A binary operation () is associative if the order of operations between operands does not affect the result — i.e. if (a(bc)) = ((ab)c).

• A binary operation () is commutative if the order of two operands within one operation does not affect the result — i.e. if (ab) = (ba).

There are operations like addition and multiplication that are both associative and commutative, and operations like subtraction and division that are neither associative nor commutative.

There are also operations — such as the group composition operator — that are associative but not commutative.

But then there are operations that are commutative but not associative. These are more rare and not analyzed as much mathematically, but they occur. For example, rounded multiplication is such an operation. If you round a calculation to the nearest tenth after every multiplication, you can get anomalies like (6.8 × 5.7) × 2.9 = 112.5 while 6.8 × (5.7 × 2.9) = 112.2.

---

Let a permutation of the operands P in an operation tree (such as ((x(xx))((x(xx))x))) be associatively equivalent to another permutation Q, if the operands in P can be rearranged by the commutative property to form an operation tree identical to the original.

For example, permutations (a(b(c(de)))) and (a(b(c(ed)))) of the operation tree (x(x(x(xx)))) are equivalent, because d commutes with e. However, (a(b(c(de)))) and (a(b(d(ce)))) are not equivalent, because (c(de)) is not equal to (d(ce)).

A more complex example might be (((ab)c)(d(ef))) and (((ef)d)(c(ba))). Step-by-step, the two of these can be shown to be equivalent as follows:

(((ab)c)(d(ef))) = (((ba)c)(d(ef)))     since    a    commutes with    b
(((ba)c)(d(ef))) = (((ba)c)((ef)d))     since  (ef)   commutes with    d
(((ba)c)((ef)d)) = ((c(ba))((ef)d))     since  (ba)   commutes with    c
((c(ba))((ef)d)) = (((ef)d)(c(ba)))     since (c(ba)) commutes with ((ef)d)

Permutations of different operation trees are not comparable. (a(b(c(de)))) and ((((ab)c)d)e) are neither associatively equivalent nor associatively distinct, because their operation trees are different.

---

Your task is to build a program that will find all the associatively equivalent permutations of the operands of a given operation tree.

Your program will take input in the form given above, with brackets enclosing juxtaposed operators. The operands will always be lowercase letters, in alphabetical order starting from a, and will contain a maximum of 26 letters.

Your program will output a series of permutations of the letters, without the brackets, representing all of the permutations that are associatively equivalent with the original permutation.

For example, if you are given an input of:

((ab)(cd))

Then your program will output:

abcd
abdc
bacd
badc
cdab
cdba
dcab
dcba

Your program must be accompanied by a description of its algorithm, and a proof of its asymptotic runtime with respect to the number of operands in the operation tree. The program with the lowest asymptotic runtime in this manner wins.

Answer 1

Every parenthesis has in it two elements, either a terminal symbol, or another parenthesis. These two elements have two possible permutations, ab and ba.

This means that the expression forms a binary tree, and every node inside the tree has two possible permutations. So the total output is always 2ⁿ where n is the number of parenthesis pairs. This means that an asymptotical algorithm will always do this amount of work.

For this optimal algorithm we will parse the expression, then recursively generate possibilities, 2 for each parenthesis pair. As seen in the paragraph above, this is optimal.

def parse(inp):
    c = inp.pop(0)
    while c == ")": c = inp.pop(0)

    if c == "(":
        return [parse(inp), parse(inp)]

    return c

def possibs(tree):
    if len(tree) == 2:
        for left_possib in possibs(tree[0]):
            for right_possib in possibs(tree[1]):
                yield left_possib + right_possib
                yield right_possib + left_possib
    else:
        yield tree


tree = parse(list("((ab)(cd))"))

for possib in possibs(tree):
    print(possib)