title: how find all groups of subsets of set A? Set partitions in Python
body: <p>I want to find an algorithm that given a set <code>A</code> to find all groups of subsets that satisfy the following condition:</p>
  
  <blockquote>
    <p>x ∪ y ∪ .... z = A, where x, y, ... z ∈ Group</p>
  </blockquote>
  
  <p>and </p>
  
  <blockquote>
    <p>∀ x,y ∈ Group: x ⊆ A, y ⊆ A, x ∩ y = ∅ = {}</p>
  </blockquote>
  
  <p>and </p>
  
  <blockquote>
    <p>∀ x ∈ Group: x != ∅</p>
  </blockquote>
  
  <p>Note: I hope to define it well, I'm not good with math symbols</p>
  
  <p>I made the following approach to search groups of two subsets only:</p>
  
  <pre><code>from itertools import product, combinations
  
  def my_combos(A):
    subsets = []
    for i in xrange(1, len(A)):
      subsets.append(list(combinations(A,i)))
    combos = []
    for i in xrange(1, 1+len(subsets)/2):
      combos.extend(list(product(subsets[i-1], subsets[-i])))
    if not len(A) % 2:
      combos.extend(list(combinations(subsets[len(A)/2-1], 2)))
    return [combo for combo in combos if not set(combo[0]) &amp; set(combo[1])]
  
  my_combos({1,2,3,4})
  </code></pre>
  
  <p>I get the following output, these are all groups composed of two subsets</p>
  
  <pre><code>[
    ((1,), (2, 3, 4)), 
    ((2,), (1, 3, 4)), 
    ((3,), (1, 2, 4)), 
    ((4,), (1, 2, 3)), 
    ((1, 2), (3, 4)), 
    ((1, 3), (2, 4)), 
    ((1, 4), (2, 3))
  ]
  </code></pre>
  
  <p>..... but, groups composed of one, three, four subsets .... </p>
  
  <p><strong>Question:</strong></p>
  
  <p>how may i find a general solution? </p>
  
  <p>for example the following expected output:</p>
  
  <pre><code>my_combos({1,2,3,4})
  
  [
    ((1,2,3,4)),
    ((1,2,3),(4,)),
    ((1,2,4),(3,)),
    ((1,3,4),(2,)),
    ((2,3,4),(1,)),
    ((1,2),(3,4)),
    ((1,3),(2,4)),
    ((1,4),(2,3)),
    ((1,2),(3,),(4,)),
    ((1,3),(2,),(4,)),
    ((1,4),(2,),(3,)),
    ((1,),(2,),(3,4)),
    ((1,),(3,),(2,4)),
    ((1,),(4,),(2,3)),
    ((1,),(4,),(2,),(3,))
  ]
  </code></pre>