Python split a list into n groups in all possible combinations of group length and elements within group
<p>I want to split a list into n groups in all possible combinations (allowing for variable group length). </p>

<p>Say, I have the following list:</p>

<pre><code>lst=[1,2,3,4]
</code></pre>

<p>If I specify n=2, the list could be divided either into groups of 1 element-3 elements or 2 elements-2 elements. Within those two ways of splitting the list, there are unique combinations of which elements go in each list. </p>

<p>With n=2, these would be:</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>With n=1 these would be:</p>

<pre><code>(1,2,3,4)
</code></pre>

<p>And with n=3 these would be:</p>

<pre><code>(1),(2),(3,4)
(1),(3),(2,4)
(1),(4),(2,3)
(2),(3),(1,4)
(2),(4),(1,3)
(3),(4),(1,2)
</code></pre>

<p>I am not interested in groups of length 0, and order within a group does not matter.</p>

<p>I found two similar questions, but they don't answer my question exactly.</p>

<p><a href="http://stackoverflow.com/questions/5360220/how-to-split-a-list-into-pairs-in-all-possible-ways">This</a> question splits a list into all combinations where each group is of length n (I found the answer by @tokland) to be particularly useful). However, I am not looking for all groups to be of the same length. </p>

<p>And then the first step of <a href="http://stackoverflow.com/questions/9088321/show-all-possible-groupings-of-a-list-given-only-the-amount-of-sublists-length">this</a> question gets unique combinations of split locations to split a list into n groups. However, list order is preserved here and unique combinations of elements within these groups is not determined.</p>

<p>I am looking for a combination of these two questions - a list is split into n groups in all possible combinations of group length as well as combinations of elements within a group.</p>

<p>Following the helpful links from @friendly_dog, I'm attempting to answer my own question by tweaking the functions used in <a href="http://stackoverflow.com/questions/19368375/set-partitions-in-python/30134039#30134039">this</a> post. I have a rough solution that works, although I fear it is not particularly efficient and could use some improvement. I end up generating many more sets of partitions than I need, and then filter out for the ones that differ only by sort order.</p>

<p>First, I take these 3 functions from <a href="http://stackoverflow.com/questions/19368375/set-partitions-in-python/30134039#30134039">Set partitions in Python</a>:</p>

<pre><code>import itertools
from copy import deepcopy

def slice_by_lengths(lengths, the_list):
    for length in lengths:
        new = []
        for i in range(length):
            new.append(the_list.pop(0))
        yield new

def partition(number):
    return {(x,) + y for x in range(1, number) for y in partition(number-x)} | {(number,)}

def subgrups(my_list):
    partitions = partition(len(my_list))
    permed = []
    for each_partition in partitions:
        permed.append(set(itertools.permutations(each_partition, len(each_partition))))

    for each_tuple in itertools.chain(*permed):
        yield list(slice_by_lengths(each_tuple, deepcopy(my_list)))
</code></pre>

<p>I then write a function that wraps the <code>subgrups</code> function and applies it to each permutation of my original list. I loop through these subgroup permutations and if they are equal in length to the desired number of partitions, I sort them in a way that allows me to identify duplicates. I'm not sure if there is a better approach to this.</p>

<pre><code>def return_partition(my_list,num_groups):
    filtered=[]
    for perm in itertools.permutations(my_list,len(my_list)):
        for sub_group_perm in subgrups(list(perm)):
            if len(sub_group_perm)==num_groups:
                #sort  within each partition
                sort1=[sorted(i) for i in sub_group_perm]
                #sort by first element of each partition
                sort2=sorted(sort1, key=lambda t:t[0])
                #sort by the number of elements in each partition
                sort3=sorted(sort2, key=lambda t:len(t))
                #if this new sorted set of partitions has not been added, add it
                if sort3 not in filtered:
                    filtered.append(sort3)
    return filtered
</code></pre>

<p>Running it on my original example list, I see that it produces the desired output, tested on two partitions and three partitions.</p>

<pre><code>&gt;&gt;&gt; for i in return_partition([1,2,3,4],2):
...     print i    
... 
[[1], [2, 3, 4]]
[[4], [1, 2, 3]]
[[1, 2], [3, 4]]
[[3], [1, 2, 4]]
[[1, 3], [2, 4]]
[[2], [1, 3, 4]]
[[1, 4], [2, 3]]
&gt;&gt;&gt; 

&gt;&gt;&gt; for i in return_partition([1,2,3,4],3):
...     print i        
... 
[[1], [4], [2, 3]]
[[3], [4], [1, 2]]
[[1], [2], [3, 4]]
[[1], [3], [2, 4]]
[[2], [4], [1, 3]]
[[2], [3], [1, 4]]
&gt;&gt;&gt; 
</code></pre>

python