How to partition list so that there are no partitions with same characters-CodePudding

So first I want to partition list to every possible partition, without changing the order of list. Like this:

[['a', 'b', 'a']]
[['a'], ['b', 'a']]
[['a', 'b'], ['a']]
[['a'], ['b'], ['a']]

Count of ways to do this is 4. I want to remove all possible partitions that have same characters in the part. For same input than last time:

[['a'], ['b', 'a']]
[['a', 'b'], ['a']]
[['a'], ['b'], ['a']]

Removed [['a', 'b', 'a']] , because it has 2 a's in same part. How to do it in python?

CodePudding user response：

One approach is to use itertools.combinations on range to create all the different ways to partition the list. Once the list is partitioned filter out if any of the parts contains duplicated elements.

from itertools import combinations, chain


def partition(alist, indices):
    # https://stackoverflow.com/a/1198876/4001592
    pairs = zip(chain([0], indices), chain(indices, [None]))
    return (alist[i:j] for i, j in pairs)


lst = ["a", "b", "a"]

result = []
split_count = len(lst)
for i in range(split_count):
    for combination in combinations(range(1, split_count), i):
        parts = [part for part in partition(lst, combination)]
        if all(len(part) == len(set(part)) for part in parts):
            result.append(parts)

for parts in result:
    print(parts)

Output

[['a'], ['b', 'a']]
[['a', 'b'], ['a']]
[['a'], ['b'], ['a']]