title: Partition N items into K bins in Python lazily
body: <p>Give an algorithm (or straight Python code) that yields all partitions of a collection of N items into K bins such that each bin has at least one item. I need this in both the case where order matters and where order does not matter. </p>
  
  <p>Example where order matters</p>
  
  <pre><code>&gt;&gt;&gt; list(partition_n_in_k_bins_ordered((1,2,3,4), 2))
  [([1], [2,3,4]), ([1,2], [3,4]), ([1,2,3], [4])]
  
  &gt;&gt;&gt; list(partition_n_in_k_bins_ordered((1,2,3,4), 3))
  [([1], [2], [3,4]), ([1], [2,3], [4]), ([1,2], [3], [4])]
  
  &gt;&gt;&gt; list(partition_n_in_k_bins_ordered((1,2,3,4), 4))
  [([1], [2], [3], [4])]
  </code></pre>
  
  <p>Example where order does not matter</p>
  
  <pre><code>&gt;&gt;&gt; list(partition_n_in_k_bins_unordered({1,2,3,4}, 2))
  [{{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>These functions should produce lazy iterators/generators, not lists. Ideally they would use primitives found in <code>itertools</code>. I suspect that there is a clever solution that is eluding me. </p>
  
  <p>While I've asked for this in Python I'm also willing to translate a clear algorithm. </p>