Reconstruct this generator to yield sorted nested tuples instad of nested lists

Question

I currently have the folliwng generator that yields nested lists (to construt the set of partitions of a set), but i actualy need it to output nested tuples. I currently use a to_tuple hack, but could you help me to make it 'natively' inside the generator ?

def _partition(collection):
    #from here : https://stackoverflow.com/questions/19368375/set-partitions-in-python/61141601"
    if len(collection) == 1:
        yield [ collection ]
        return
    first = collection[0]
    for smaller in _partition(collection[1:]):
        # insert `first` in each of the subpartition's subsets
        for n, subset in enumerate(smaller):
            yield smaller[:n] + [[ first ] + subset]  + smaller[n+1:]
        # put `first` in its own subset
        yield [ [ first ] ] + smaller

def to_tuple(lst):
    return tuple(to_tuple(i) if isinstance(i, list) else i for i in lst)


## using it 
exemple = [0,0,1,4]
pp = [sorted(p) for p in _partition(exemple)]
result = to_tuple(pp)

Dmitrii Altukhov · Accepted Answer · 2020-06-23T13:49:20.990

Here's what I've got:

def _partition(collection):
    # from here: https://stackoverflow.com/questions/19368375/set-partitions-in-python/61141601"
    collection = tuple(collection)
    if len(collection) == 1:
        yield (collection,)
        return
    first = collection[0]
    for smaller in _partition(collection[1:]):
        # insert `first` in each of the subpartition's subsets
        for n, subset in enumerate(smaller):
            yield tuple(sorted(
                smaller[:n]
                + (tuple(sorted((first,) + subset)),)
                + smaller[n + 1 :]
            ))
        # put `first` in its own subset
        yield tuple(sorted(((first,),) + smaller))

With

example = [0, 0, 1, 4]
for p in _partition(example):
    print(p)

the output would be:

((0, 0, 1, 4),)
((0,), (0, 1, 4))
((0, 0), (1, 4))
((0,), (0, 1, 4))
((0,), (0,), (1, 4))
((0, 0, 1), (4,))
((0, 1), (0, 4))
((0,), (0, 1), (4,))
((0, 0, 4), (1,))
((0, 1), (0, 4))
((0,), (0, 4), (1,))
((0, 0), (1,), (4,))
((0,), (0, 1), (4,))
((0,), (0, 4), (1,))
((0,), (0,), (1,), (4,))

And in unsorted case

example = [2, 0, 1, 4]
for p in _partition(example):
    print(p)

it outputs

((0, 1, 2, 4),)
((0, 1, 4), (2,))
((0, 2), (1, 4))
((0,), (1, 2, 4))
((0,), (1, 4), (2,))
((0, 1, 2), (4,))
((0, 1), (2, 4))
((0, 1), (2,), (4,))
((0, 2, 4), (1,))
((0, 4), (1, 2))
((0, 4), (1,), (2,))
((0, 2), (1,), (4,))
((0,), (1, 2), (4,))
((0,), (1,), (2, 4))
((0,), (1,), (2,), (4,))

Finally, with repeated elements:

example = [1, 2, 2]
for p in _partition(example):
    print(p)

output:

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

To remove the duplicates you can run set(_partition(example))

For the sorting on the outer level, I don't think it can be done with generators since we're getting elements one by one and can't compare them before the generator is exhausted.

It's better. The result is sorted inside each part of each partition, but the partitions themselves are not sorted. for `example = [1,2,2]` i obtain two outputs `((1,2),(2,))` and `((2,),(1,2))`, which i'd like to come as the same. Would it be possible to sort also one level up ? (i dont mean sorting in the outper level, but just reproducing the output of the example i gave up (sorting after the generator). But maybe it's not doable, you are right. — lrnv, Jun 23 '20 at 13:22
Ok, I added another level of sorting. Now to remove duplicates you can just run `set(_partition(example))`. Another option would be to keep track of the seen partitions but I'm not sure how to implement this with recursion. — Dmitrii Altukhov, Jun 23 '20 at 13:42
And now it's perfect. Indeed, i want to use Counter() and not set(). I did not found the right mathematical logic into these counts, but it will probably be a lot faster if i manage to find one. — lrnv, Jun 23 '20 at 14:03
Yes, it's quite complicated maths to compute a number of set partitions — Dmitrii Altukhov, Jun 23 '20 at 15:12

Reconstruct this generator to yield sorted nested tuples instad of nested lists

1 Answers1

Linked