How to union nested Sets / A single set from nested sets?

[Oscar Benjamin]

On 7 January 2016 at 08:37, Steven D'Aprano <steve at pearwood.info> wrote:
> On Thu, 7 Jan 2016 01:45 am, Oscar Benjamin wrote:
>
>> On 4 January 2016 at 02:40, mviljamaa <mviljamaa at kapsi.fi> wrote:
>>> I'm forming sets by set.adding to sets and this leads to sets such as:
>>>
>>> Set([ImmutableSet(['a', ImmutableSet(['a'])]), ImmutableSet(['b', 'c'])])
>>>
>>> Is there way union these to a single set, i.e. get
>>>
>>> Set(['a', 'b', 'c'])
>>
>> Where are you getting Set and ImmutableSet from? Is that sympy or
>> something?
>
> Set and ImmutableSet were the original versions from Python 2.3 before the
> builtins. They're still available up to Python 2.7 (gone in 3):
>
>
> py> import sets
> py> sets.Set
> <class 'sets.Set'>
>
> but that's just for backwards compatibility, you should use the built-in
> versions if you can.

Okay, thanks Steve.

Then I translate the OP's problem as how to go from

    S = set([frozenset(['a', frozenset(['a'])]), frozenset(['b', 'c'])])

to

    set(['a', 'b', 'c'])

This is not just a union of the elements of the set since:

    In [7]: {x for fs in S for x in fs}
    Out[7]: set(['a', 'c', 'b', frozenset(['a'])])

The reason for this is that there are multiple levels of nesting. I
assume that the OP wants to recursively get all the elements from all
the nested sets and create a set out of those. Here's a breadth-first
search that can do that:

def flat_nested(tree):
  flat = set()
  stack = [iter(tree)]
  while stack:
    branch = stack.pop(0)
    for x in branch:
      if isinstance(x, frozenset):
        stack.append(iter(x))
      else:
        flat.add(x)
  return flat

And now:

    In [15]: flat_nested(S)
    Out[15]: set(['a', 'c', 'b'])

--
Oscar