How to get all combinations of list groupings of at least a certain size?

Question

Given a list in python (or java, I'm trying to do this in both languages), how can I get all the different ways to split a list into different groupings given that each grouping must be a least a certain size? I think that getting a the combinations of split locations is the best way to go about it.

An example input of a list and min size is

[1,2,3], 2

and the corresponding output should be

[[1,2], [1,3], [2,3], [1,2,3]]

Answer 1

EDIT

Based upon OP's new input/output requirements, it's just a couple of lines:

def groupings(lst, min_size):
    results = [tuple(lst)]
    for i in range(min_size, len(lst)):
        results.extend(combinations(lst, i))
    return results

ORIGINAL

(Based on an incorrect assumption that OP wanted all possible partitions given a minimum partition size.)

So itertools.combinations() should be a starting point. For example,

>>> list(combinations('ABCD', 2))
[('A', 'B'), ('A', 'C'), ('A', 'D'), ('B', 'C'), ('B', 'D'), ('C', 'D')]

So that gives one piece of your answer. The output of your grouping for 'ABCD' with min size set to 2 is:

[['A', 'B', 'C', 'D']]
[['A', 'D'], ['B', 'C']]
[['A', 'C'], ['B', 'D']]
[['A', 'B'], ['C', 'D']]

So the high-level process should be roughly:

results = []
remaining = [([], list)] # Start without any groups and the full list

while remaining not empty:

    groups, list = remaining.pop()

    if len(list) >= min_size:
        results.append(groups + list)

    for size in min_size to len(list) - 1:

        for combo in combinations:
           new <- (groups + combo, list - combo)

           if new will not cause duplicates:
               remaining.append(new)

Here is some code that seems to work. To avoid duplicates, and handle the cases where the original list might have duplicates, I modified the code from itertools.combinations, rather than just using the method.

def groupings(lst, min_size):

    lst = list(lst)

    # List for storing our final groupings
    results = []

    # Unfinished grouping, tuple storing the group and remaining sub-list
    # Initialize with the empty group and original list
    remaining = [([], lst)]

    # Continue as long as we have unfinished groupings
    while len(remaining):

        # Get an unfinished grouping 
        current_group, current_lst = remaining.pop()
        n = len(current_lst)

        # If the last part of the list is big enough,
        # then record the grouping
        if n >= min_size:
            results.append(current_group + [current_lst])

        # Otherwise, discard it
        else:
            continue

        # Helper set for getting remainder below
        all_indices = set(range(n))

        # Iterate the group length from min_size to the length of our current list
        for r in range(min_size, n - 1):

            # This is a modified version of itertools.combinations()
            # http://docs.python.org/3.3/library/itertools.html#itertools.combinations

            # Add the first combination to our remaining list
            indices = list(range(r))
            remainder = current_lst[r:]
            group = current_group + [current_lst[:r]]
            remaining.append((group, remainder))

            while True:
                for i in reversed(range(r)):
                    if indices[i] != i + n - r:
                        break
                else:
                    break

                indices[i] += 1
                for j in range(i+1, r):
                    indices[j] = indices[j-1] + 1

                # If one of the remaining indexes is less than the minimum used index,
                # then a different iteration will handle it, so discard this one
                min_index = min(indices)
                remainder = []
                for i in all_indices.difference(indices):
                    remainder.append(current_lst[i])
                    if i < min_index:
                        break
                else:
                    # Add this combination to our remaining list
                    group = current_group + [[current_lst[i] for i in indices]]
                    remaining.append((group, remainder))

    return results

The results:

>>> groupings('ABCDE', 2)
[['A', 'B', 'C', 'D', 'E']]
[['A', 'D', 'E'], ['B', 'C']]
[['A', 'C', 'E'], ['B', 'D']]
[['A', 'C', 'D'], ['B', 'E']]
[['A', 'B', 'E'], ['C', 'D']]
[['A', 'B', 'D'], ['C', 'E']]
[['A', 'B', 'C'], ['D', 'E']]
[['A', 'E'], ['B', 'C', 'D']]
[['A', 'D'], ['B', 'C', 'E']]
[['A', 'C'], ['B', 'D', 'E']]
[['A', 'B'], ['C', 'D', 'E']]

Answer 2

In Python, you could do this recursively:

def partition(lst, minsize=1):
    yield [lst]
    for n in range(minsize, len(lst)-minsize+1):
        for p in partition(lst[n:], minsize):
            yield [lst[:n]] + [l for l in p]

For example:

>>> lst = [1, 2, 3, 4, 5, 6, 7]
>>> partition(lst, 3)
[[[1, 2, 3, 4, 5, 6, 7]], 
 [[1, 2, 3], [4, 5, 6, 7]], 
 [[1, 2, 3, 4], [5, 6, 7]]]
>>> list(partition(lst, 2))
[[[1, 2, 3, 4, 5, 6, 7]], [[1, 2], [3, 4, 5, 6, 7]], 
 [[1, 2], [3, 4], [5, 6, 7]], [[1, 2], [3, 4, 5], [6, 7]], 
 [[1, 2, 3], [4, 5, 6, 7]], [[1, 2, 3], [4, 5], [6, 7]], 
 [[1, 2, 3, 4], [5, 6, 7]], [[1, 2, 3, 4, 5], [6, 7]]]