Determine sets of associatively equivalent permutations of commutative operations
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 2n 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)