Path: csiph.com!news.swapon.de!fu-berlin.de!uni-berlin.de!not-for-mail
From: Oscar Benjamin <oscar.j.benjamin@gmail.com>
Newsgroups: comp.lang.python
Subject: Re: How to union nested Sets / A single set from nested sets?
Date: Thu, 7 Jan 2016 15:19:28 +0000
Lines: 65
Message-ID: <mailman.48.1452179990.2305.python-list@python.org>
References: <bd94920f139af986c1a304f5ce844f9d@kapsi.fi> <mailman.31.1452091523.2305.python-list@python.org> <568e23e5$0$1590$c3e8da3$5496439d@news.astraweb.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8
In-Reply-To: <568e23e5$0$1590$c3e8da3$5496439d@news.astraweb.com>
Precedence: list
Xref: csiph.com comp.lang.python:101340

On 7 January 2016 at 08:37, Steven D'Aprano <steve@pearwood.info> wrote:
> On Thu, 7 Jan 2016 01:45 am, Oscar Benjamin wrote:
>
>> On 4 January 2016 at 02:40, mviljamaa <mviljamaa@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