Show all possible groupings of a list, given only the amount of sublists (lengths are variable)

Question

Problem

Step 1: Given a list of numbers, generate all possible groupings (in order) given only the final number of desired groups.

For example, if my list of numbers were 1 to 4, and I wanted 2 final groups, the possibilities would be:

[1], [2,3,4]

[1,2], [3,4]

[1,2,3], [4]

Step 2: Perform arithmetic operations on those groups.

For example, if we chose addition, the final results would be:

1 + 234 = 235
12 + 34 = 46
123 + 4 = 127

Prior Research and Similar Problems

I've seen numerous examples on SO and elsewhere for problems involving variable amounts of groups, which utilize ranges and for loops, a la:

print [num_list[i:i+groups] for i in range(0,len(num_list),groups)]

But that's kind of the reverse of what I want - there, the lengths of the groups themselves are fixed save for the final one, and the number of groups oscillates.

This isn't homework, just an interesting problem I came across. Ideally, I'd need to be able to iterate over those separate sublists in order to perform the mathematical operations, so they'd need to be captured as well.

I have a feeling the solution will involve itertools, but I can't seem to figure out the combinatorics with grouping aspect.

Edit/Extension of Step 2

If I want to perform different operations on each of the partitions, can I still approach this the same way? Rather than specifiying just int.add, can I somehow perform yet another combination of all the main 4 operations? I.e.:

symbol_list = ['+','-','*','/']
for op in symbol_list:
   #something

I'd wind up with possibilities of:

1 + 2 * 34
1 * 2 - 34
1 / 2 + 34
etc.

Order of operations can be ignored.

Final Solution

#!/usr/bin/env python

import sys
from itertools import combinations, chain, product

# fixed vars
num_list = range(_,_) # the initial list
groups = _ # number of groups
target = _ # any target desired
op_dict = {'+': int.__add__, '-': int.__sub__,
           '*': int.__mul__, '/': int.__div__}

def op_iter_reduce(ops, values):
    op_iter = lambda a, (i, b): op_dict[ops[i]](a, b)
    return reduce(op_iter, enumerate(values[1:]), values[0])

def split_list(data, n):
    for splits in combinations(range(1, len(data)), n-1):
        result = []
        prev = None
        for split in chain(splits, [None]):
            result.append(data[prev:split])
            prev = split
        yield result

def list_to_int(data):
    result = 0
    for h, v in enumerate(reversed(data)):
        result += 10**h * v
    return result

def group_and_map(data, num_groups):
    template = ['']*(num_groups*2 - 1) + ['=', '']
    for groups in split_list(data, num_groups):
        ints = map(list_to_int, groups)
        template[:-2:2] = map(str, ints)
        for ops in product('+-*/', repeat=num_groups-1):
            template[1:-2:2] = ops
            template[-1] = str(op_iter_reduce(ops, ints))
            if op_iter_reduce(ops, ints) == target:
                print ' '.join(template)

group_and_map(num_list, groups)

Andrew Clark · Accepted Answer · 2012-02-01T00:41:04.200

Step 1: The easiest way I have found to think of splitting lists into groups like that is to try to get combinations of split locations. Here is an implementation:

def split_list(data, n):
    from itertools import combinations, chain
    for splits in combinations(range(1, len(data)), n-1):
        result = []
        prev = None
        for split in chain(splits, [None]):
            result.append(data[prev:split])
            prev = split
        yield result

>>> list(split_list([1, 2, 3, 4], 2))
[[[1], [2, 3, 4]], [[1, 2], [3, 4]], [[1, 2, 3], [4]]]
>>> list(split_list([1, 2, 3, 4], 3))
[[[1], [2], [3, 4]], [[1], [2, 3], [4]], [[1, 2], [3], [4]]]

Step 2: First you need to convert a list like [[1], [2, 3, 4]], to one like [1, 234]. You can do this with the following function:

def list_to_int(data):
    result = 0
    for i, v in enumerate(reversed(data)):
        result += 10**i * v
    return result

>>> map(list_to_int, [[1], [2, 3], [4, 5, 6]])
[1, 23, 456]

Now you can perform your operation on the resulting list using reduce():

>>> import operator
>>> reduce(operator.add, [1, 23, 456])  # or int.__add__ instead of operator.add
480

Complete solution: Based on edit referencing need for different operators:

def op_iter_reduce(ops, values):
    op_dict = {'+': int.__add__, '-': int.__sub__,
               '*': int.__mul__, '/': int.__div__}
    op_iter = lambda a, (i, b): op_dict[ops[i]](a, b)
    return reduce(op_iter, enumerate(values[1:]), values[0])

def group_and_map(data, num_groups):
    from itertools import combinations_with_replacement
    op_dict = {'+': int.__add__, '-': int.__sub__,
               '*': int.__mul__, '/': int.__div__}
    template = ['']*(num_groups*2 - 1) + ['=', '']
    op_iter = lambda a, (i, b): op_dict[ops[i]](a, b)
    for groups in split_list(data, num_groups):
        ints = map(list_to_int, groups)
        template[:-2:2] = map(str, ints)
        for ops in combinations_with_replacement('+-*/', num_groups-1):
            template[1:-2:2] = ops
            template[-1] = str(op_iter_reduce(ops, ints))
            print ' '.join(template)

>>> group_and_map([1, 2, 3, 4], 2)
1 + 234 = 235
1 - 234 = -233
1 * 234 = 234
1 / 234 = 0
12 + 34 = 46
12 - 34 = -22
12 * 34 = 408
12 / 34 = 0
123 + 4 = 127
123 - 4 = 119
123 * 4 = 492
123 / 4 = 30

If you are on Python 2.6 or below and itertools.combinations_with_replacement() is not available, you can use the recipe linked here.

Thank you, this works well too. The enumeration part has me a bit confused - need to look over that. As per the edit, I'm trying to figure out how to add a loop over all 4 main arithmetic operations. So instead of adding all of them, I could try all permutations of a + b -c, a * b / c, etc. — Brett Woodward, Jan 31 '12 at 23:57
@BrettWoodward - Would you want to maintain order of operations or always calculate from left to right (should `1 + 2 * 34` actually calculate `(1 + 2) * 34` instead of the normal `1 + (2 * 34)`). — Andrew Clark, Feb 01 '12 at 00:05
In this case, OoO can be ignored. As in, always left to right. I was thinking of using lambda for that, but not sure how to iterate over different operators. — Brett Woodward, Feb 01 '12 at 00:14
@BrettWoodward - Okay, my recent edit now works by iterating over basic math operators. — Andrew Clark, Feb 01 '12 at 00:42
That's superb, thank you. I was struggling for the past few hours over something though - it didn't seem to be creating all the permutations I needed. I wound up swapping out combinations_with_replacement for product - that generates all possible repetitive arithmetic operators. And I got it to work. Fantastic, thanks all. — Brett Woodward, Feb 01 '12 at 03:19

unutbu · Answer 2 · 2012-02-01T10:43:49.760

Raymond Hettinger has written a recipe for finding all partitions of an iterable into n groups:

import itertools
import operator

def partition_indices(length, groups, chain = itertools.chain):
    first, middle, last = [0], range(1, length), [length]    
    for div in itertools.combinations(middle, groups-1):
        yield tuple(itertools.izip(chain(first, div), chain(div, last)))

def partition_into_n_groups(iterable, groups, chain = itertools.chain):
    # http://code.activestate.com/recipes/576795/
    # author: Raymond Hettinger
    # In [1]: list(partition_into_n_groups('abcd',2))
    # Out[1]: [('a', 'bcd'), ('ab', 'cd'), ('abc', 'd')]
    s = iterable if hasattr(iterable, '__getitem__') else tuple(iterable)
    for indices in partition_indices(len(s), groups, chain):
        yield tuple(s[slice(*x)] for x in indices)

def equations(iterable, groups):
    operators = (operator.add, operator.sub, operator.mul, operator.truediv)
    strfop = dict(zip(operators,'+-*/'))
    for partition in partition_into_n_groups(iterable, groups):
        nums_list = [int(''.join(map(str,item))) for item in partition]
        op_groups = itertools.product(operators, repeat = groups-1)
        for op_group in op_groups:
            nums = iter(nums_list)
            result = next(nums)
            expr = [result]
            for op in op_group:
                num = next(nums)
                result = op(result, num)
                expr.extend((op, num))
            expr = ' '.join(strfop.get(item,str(item)) for item in expr)
            yield '{e} = {r}'.format(e = expr, r = result)

for eq in equations(range(1,5), groups = 2):
    print(eq)

yields

1 + 234 = 235
1 - 234 = -233
1 * 234 = 234
1 / 234 = 0.0042735042735
12 + 34 = 46
12 - 34 = -22
12 * 34 = 408
12 / 34 = 0.352941176471
123 + 4 = 127
123 - 4 = 119
123 * 4 = 492
123 / 4 = 30.75

Thank you, this also works well. I'm trying to work through the syntax there. As per the edit, I'm trying to figure out how to add a loop over all 4 main arithmetic operations. So instead of adding all of them, I could try all permutations of a + b -c, a * b / c, etc. — Brett Woodward, Jan 31 '12 at 23:57

Rik Poggi · Answer 3 · 2012-02-01T00:10:37.267

Step 1:

I worked on all the possible combinations of the indexes:

from itertools import combinations

def cut(lst, indexes):
    last = 0
    for i in indexes:
        yield lst[last:i]
        last = i
    yield lst[last:]


def generate(lst, n):
    for indexes in combinations(list(range(1,len(lst))), n - 1):
        yield list(cut(lst, indexes))

Example:

for g in generate([1, 2, 3, 4, 5], 3):
    print(g)
"""
[[1], [2], [3, 4, 5]]
[[1], [2, 3], [4, 5]]
[[1], [2, 3, 4], [5]]
[[1, 2], [3], [4, 5]]
[[1, 2], [3, 4], [5]]
[[1, 2, 3], [4], [5]]
"""

Step 2:

First we have to transform the group of digits in numbers:

for g in generate(list(range(1,6)), 3):
    print([int(''.join(str(n) for n in n_lst)) for n_lst in g])
"""
[1, 2, 345]
[1, 23, 45]
[1, 234, 5]
[12, 3, 45]
[12, 34, 5]
[123, 4, 5]
"""

And then with reduce and operator perform the arithmetic:
(Although this last sub-step is not really related to your problem)

from functools import reduce
import operator
op = operator.mul

for g in generate(list(range(1,6)), 3):
    converted = [int(''.join(str(n) for n in n_lst)) for n_lst in g]
    print(reduce(op, converted))
"""
690
1035
1170
1620
2040
2460
"""

Thank you, this works well. As per the edit, I'm trying to figure out how to add a loop over all 4 main arithmetic operations. So instead of adding all of them, I could try all permutations of a + b -c, a * b / c, etc. — Brett Woodward, Jan 31 '12 at 23:56
@BrettWoodward: It really depends on what operations you want to do, anyway you can put them all in a list or a dict, like: `{'+': operator.add, ...}` and choose the one you want. I've updated my answer with link to `operator` and `reduce` documentation. *Anyway if you continue extending your problem, you'll never get it solved! ;)* — Rik Poggi, Feb 01 '12 at 00:11

Show all possible groupings of a list, given only the amount of sublists (lengths are variable)

Problem

Final Solution

3 Answers3

Linked