Nested partitions of integers

I want to create all nested partitions of an integer - with all possible permutations of numbers and brackets (nests) at all possible positions.

For example, for n = 3, I would like to have

(3,)
(1, 2)
(1, 1, 1)
(1, (1, 1))
(2, 1)
((1, 1), 1)

In general something like

(2,3,(1,1,(3,4,5),1),5,(1,2,3))

for a nested partition of 31.

I managed to write this code (based on the standard partition of integers):

def partitions(n):
    yield (n,)
    for i in range(1, n):
        for q in partitions(i):
            for p in partitions(n-i):
                yield q + p
                if len(q) > 1:
                    yield (q,) + p
                if len(p) > 1:
                    yield q + (p,)
                if len(p) > 1 and len(q) > 1:
                    yield (q,) + (p,)

But it returns duplicates, for n=3, we get twice the sequence (1, 1, 1). It makes sense, since I once split 2 as 1+2 and 2+1 and then we flatten the subpartitions of the 2. Any ideas how to fix my program?

I would split the partitioning from the bracketing part and create two generators, one for each. Then a third generator can take care of producing the desired result:

def bracket(p):
    n = len(p)
    yield p
    for i in range(0, n-1):
        left = p[:i]
        for j in range(i + 2, n + 1 - (i == 0)):
            suffix = p[j:]
            for mid in bracket(p[i:j]):
                for right in bracket(suffix):
                    yield left + (mid,) + right
                    if len(right) >= 2:
                        yield left + (mid,) + (right,)

def partitions(n):
    yield (n,)
    for i in range(1, n):
        for p in partitions(n - i):
            yield (i,) + p

def nested_partitions(n):
    for p in partitions(n):
        yield from bracket(p)

For n equal to 5 this generates 112 tuples:

(5,)
(1, 4)
(1, 1, 3)
((1, 1), 3)
(1, (1, 3))
(1, 1, 1, 2)
((1, 1), 1, 2)
((1, 1), (1, 2))
((1, 1, 1), 2)
(((1, 1), 1), 2)
((1, (1, 1)), 2)
(1, (1, 1), 2)
(1, (1, 1, 2))
(1, ((1, 1), 2))
(1, (1, (1, 2)))
(1, 1, (1, 2))
(1, 1, 1, 1, 1)
((1, 1), 1, 1, 1)
((1, 1), (1, 1, 1))
((1, 1), (1, 1), 1)
((1, 1), ((1, 1), 1))
((1, 1), 1, (1, 1))
((1, 1), (1, (1, 1)))
((1, 1, 1), 1, 1)
((1, 1, 1), (1, 1))
(((1, 1), 1), 1, 1)
(((1, 1), 1), (1, 1))
((1, (1, 1)), 1, 1)
((1, (1, 1)), (1, 1))
((1, 1, 1, 1), 1)
(((1, 1), 1, 1), 1)
(((1, 1), (1, 1)), 1)
(((1, 1, 1), 1), 1)
((((1, 1), 1), 1), 1)
(((1, (1, 1)), 1), 1)
((1, (1, 1), 1), 1)
((1, (1, 1, 1)), 1)
((1, ((1, 1), 1)), 1)
((1, (1, (1, 1))), 1)
((1, 1, (1, 1)), 1)
(1, (1, 1), 1, 1)
(1, (1, 1), (1, 1))
(1, (1, 1, 1), 1)
(1, ((1, 1), 1), 1)
(1, (1, (1, 1)), 1)
(1, (1, 1, 1, 1))
(1, ((1, 1), 1, 1))
(1, ((1, 1), (1, 1)))
(1, ((1, 1, 1), 1))
(1, (((1, 1), 1), 1))
(1, ((1, (1, 1)), 1))
(1, (1, (1, 1), 1))
(1, (1, (1, 1, 1)))
(1, (1, ((1, 1), 1)))
(1, (1, (1, (1, 1))))
(1, (1, 1, (1, 1)))
(1, 1, (1, 1), 1)
(1, 1, (1, 1, 1))
(1, 1, ((1, 1), 1))
(1, 1, (1, (1, 1)))
(1, 1, 1, (1, 1))
(1, 1, 2, 1)
((1, 1), 2, 1)
((1, 1), (2, 1))
((1, 1, 2), 1)
(((1, 1), 2), 1)
((1, (1, 2)), 1)
(1, (1, 2), 1)
(1, (1, 2, 1))
(1, ((1, 2), 1))
(1, (1, (2, 1)))
(1, 1, (2, 1))
(1, 2, 2)
((1, 2), 2)
(1, (2, 2))
(1, 2, 1, 1)
((1, 2), 1, 1)
((1, 2), (1, 1))
((1, 2, 1), 1)
(((1, 2), 1), 1)
((1, (2, 1)), 1)
(1, (2, 1), 1)
(1, (2, 1, 1))
(1, ((2, 1), 1))
(1, (2, (1, 1)))
(1, 2, (1, 1))
(1, 3, 1)
((1, 3), 1)
(1, (3, 1))
(2, 3)
(2, 1, 2)
((2, 1), 2)
(2, (1, 2))
(2, 1, 1, 1)
((2, 1), 1, 1)
((2, 1), (1, 1))
((2, 1, 1), 1)
(((2, 1), 1), 1)
((2, (1, 1)), 1)
(2, (1, 1), 1)
(2, (1, 1, 1))
(2, ((1, 1), 1))
(2, (1, (1, 1)))
(2, 1, (1, 1))
(2, 2, 1)
((2, 2), 1)
(2, (2, 1))
(3, 2)
(3, 1, 1)
((3, 1), 1)
(3, (1, 1))
(4, 1)

This grows exponentially. For n=10, there are over half a million tuples.

You can remove dict to remove duplicates while keeping order

for par in dict.fromkeys(partitions(3)):
    print(par)

Output

(3,)
(1, 2)
(1, 1, 1)
(1, (1, 1))
(2, 1)
((1, 1), 1)