How can we generate all possible parenthesizations of a tuple of integers?

Samuel Muldoon 0
Viewed 36

The following is one example of what our input looks like...

# INPUT 
(1, 2, 3)

The input is an iterable container full of integers.

The desired output is a tuple of all ways to parenthesize the integers.

For the example input supplied earlier, the return value would look something like the following:

# OUTPUT 
result = (
    "(1, 2, 3)",
    "(1, 2)(3)",
    "(1)(2, 3)",
    "(1)(2)(3)"
)

Between two numbers, we must choose for the delimiter to be , or )(

# intermediate_result
intermediate_result = (
    ("," , "," , ","),
    (")(", ")(", ")("),
    (")(", ")(", ")("),
    (")(", ")(", ")("),
)

What is the simplest piece of python source code you can think of to generate all possible parenthesizations of the numbers?

Note that we could begin by generating tuples of booleans.

(True, True, False, True)

Everywhere we see True we can replace True with ", ".
False can be replaced by the string ")("

The following might prove useful:

def num_to_binary_str(num:int, nbits:int):
    """
        +--------+-------------+
        | INPUT  |   OUTPUT    |
        +--------+-------------+
        | int(0) | str('0000') |
        | int(1) | str('0001') |
        | int(2) | str('0010') |
        | int(3) | str('0011') |
        | int(4) | str('0100') |
        | int(5) | str('0101') |
        | int(6) | str('0110') |
        | int(7) | str('0111') |
        | int(8) | str('1000') |
        | int(9) | str('1001') |
        +--------+-------------+
    """
    nbits = int(str(nbits))
    num = int(str(num))
    # r = ("{" + "0:0{}b".format(nbits) + "}").format(num)
    # r = "0:0{}b".format(nbits).join("{}").format(num)
    r = str(nbits).join(("{0:0", "b}")).format(num)
    return r
parentheses combinatorics permutation python-3.x python
1 Answers

IIUC, you are trying to find all partitions of list. This can be done as follows.

Code

def partitions(lst):
    n = len(lst)
    result = []
    for partition_index in range(2 ** (n-1)):
        partition = []
        subset = []

        for position in range(n):
            subset.append(lst[position])

            # check whether to "break off" a new subset
            if 1 << position & partition_index or position == n-1:
                partition.append(subset)
                subset = []
        
        # Format current partition with desired and append to result
        result.append(''.join(f'({p})' for x in partition if (p:=','.join(str(v) for v in x))))
        
    return tuple(result)

Test

print(partitions([1, 2, 3]))
# Output: ('(1,2,3)', '(1)(2,3)', '(1,2)(3)', '(1)(2)(3)')
DarrylG0
Related