title: Iterator over all partitions into k groups?
body: <p>Say I have a list L. How can I get an iterator over all partitions of K groups?</p>
  
  <p>Example: L = [ 2,3,5,7,11, 13], K = 3</p>
  
  <p>List of all possible partitions of 3 groups:</p>
  
  <pre><code>[ [ 2 ], [ 3, 5], [ 7,11,13] ]
  [ [ 2,3,5 ], [ 7, 11], [ 13] ]
  [ [ 3, 11 ], [ 5, 7], [ 2, 13] ]
  [ [ 3 ], [ 11 ], [ 5, 7, 2, 13] ]
  etc...
  </code></pre>
  
  <p><strong>=== UPDATE ===</strong></p>
  
  <p>I was working on a solution which seems to be working, so I will just copy paste it</p>
  
  <pre><code># -*- coding: utf-8 -*-
  
  import itertools 
  
  # return ( list1 - list0 )
  def l1_sub_l0( l1, l0 ) :
      """Substract two lists"""
      #
      copy_l1 = list( l1 )
      copy_l0 = list( l0 )
  
      #
      for xx in l0 :
          #
          if copy_l1.count( xx ) &gt; 0 :
              #
              copy_l1.remove( xx )
              copy_l0.remove( xx )
  
      #
      return [ copy_l1, copy_l0 ]
  
  
  #
  def gen_group_len( n, k ) :
      """Generate all possible group sizes"""
  
      # avoid doubles
      stop_list = []
      #
      for t in itertools.combinations_with_replacement( xrange( 1, n - 1 ), k - 1 ) :
          #
          last_n = n - sum( t )
  
          # valid group size
          if last_n  &gt;= 1 :
              res = tuple( sorted( t + ( last_n, ) ) )
              #
              if res not in stop_list :
                  yield res
                  stop_list.append( res )
  
  
  # group_len = (1, 1, 3)
  
  def gen( group_len, my_list ) :
      """Generate all possible partitions of all possible group sizes"""
  
      #
      if len( group_len ) == 1 :
          yield ( tuple( my_list ), )
  
      #
      else :
  
          # need for a stop list if 2 groups of same size
          stop_list = []
  
          #
          for t in itertools.combinations( my_list, group_len[ 0 ] ) :
              #
              reduced_list = l1_sub_l0( my_list, t )[ 0 ]
  
              #
              for t2 in gen( group_len[ 1: ], reduced_list ) :
                  #
                  tmp = set( ( t, t2[ 0 ] ) )
                  #
                  if tmp not in stop_list :
                      yield ( t, ) + t2
                      # avoid doing same thing twice
                      if group_len[ 1 ] == group_len[ 0 ] :
                          stop_list.append( tmp )
  
  
  #
  my_list = [ 3,5,7,11,13 ]
  n = len( my_list )
  k = 3
  
  #
  group_len_list = list( gen_group_len( n, k ) )
  print "for %i elements, %i configurations of group sizes" % ( n, len(  group_len_list ) )
  print group_len_list
  
  #
  for group_len in group_len_list :
      #
      print "group sizes", group_len
      #
      for x in gen( group_len, my_list ) :
          print x
      #
      print "==="
  </code></pre>
  
  <p>Output: </p>
  
  <pre><code>for 5 elements, 2 configurations of group sizes
  [(1, 1, 3), (1, 2, 2)]
  group sizes (1, 1, 3)
  ((3,), (5,), (7, 11, 13))
  ((3,), (7,), (5, 11, 13))
  ((3,), (11,), (5, 7, 13))
  ((3,), (13,), (5, 7, 11))
  ((5,), (7,), (3, 11, 13))
  ((5,), (11,), (3, 7, 13))
  ((5,), (13,), (3, 7, 11))
  ((7,), (11,), (3, 5, 13))
  ((7,), (13,), (3, 5, 11))
  ((11,), (13,), (3, 5, 7))
  ===
  group sizes (1, 2, 2)
  ((3,), (5, 7), (11, 13))
  ((3,), (5, 11), (7, 13))
  ((3,), (5, 13), (7, 11))
  ((5,), (3, 7), (11, 13))
  ((5,), (3, 11), (7, 13))
  ((5,), (3, 13), (7, 11))
  ((7,), (3, 5), (11, 13))
  ((7,), (3, 11), (5, 13))
  ((7,), (3, 13), (5, 11))
  ((11,), (3, 5), (7, 13))
  ((11,), (3, 7), (5, 13))
  ((11,), (3, 13), (5, 7))
  ((13,), (3, 5), (7, 11))
  ((13,), (3, 7), (5, 11))
  ((13,), (3, 11), (5, 7))
  ===
  </code></pre>