title: Union sets of lists/sets in Python
body: <p>I'm writing a small function for finding all the subsets of a list of numbers S, the output is a list of lists.</p>
  
  <pre><code>def subsets(S):
      if S is None or len(S) == 0:
          return [[]]
  
      output_list = []
      sub = [[[], [S[0]]]]
      for i in xrange(1, len(S)):
          without_ith = sub[i - 1]
          with_ith = [element + [S[i]] for element in without_ith]
  
          # convert to set of tuples, for set union
          without_set = set(tuple(element) for element in without_ith)
          with_set = set(tuple(element) for element in with_ith)
          new_set = without_set | with_set
  
          # convert back to list of lists
          new = list(list(element) for element in new_set)
          sub.append(new)
  
      # sort each sublist into non-descending order
      # output_list = [sorted(element) for element in sub[-1]]
      for element in sub[-1]:
          output_list.append(sorted(element))
      return output_list
  </code></pre>
  
  <p>The algorithm is described in the accepted answer of this post: <a href="https://stackoverflow.com/questions/728972/finding-all-the-subsets-of-a-set">Finding all the subsets of a set</a></p>
  
  <p>The thing that annoys me is the conversion from list of lists to set of tuples, and then perform the union of two sets of tuples, and convert back to list of lists. All these happens in every iteration. The reason is that in Python, sets must contain immutable objects, which are hashable, in order to perform set operations with other sets. But lists and sets are mutable and unhashable, tuples or frozensets are required as element of such sets. For my code, I mutate the element lists first and convert them to tuples for the union, and then convert back to lists. I wonder if there is a work-around? It looks not very clean and efficient. </p>
  
  <p>(And a minor doubt is the list comprehension I commented out <code># output_list = [sorted(element) for element in sub[-1]]</code>. I'm using PyCharm and it suggests replacing the list comprehension with a for loop. Any reason? I thought list comprehension is always better.)</p>