Mostrar todas las agrupaciones posibles de una lista, dada solo la cantidad de sublistas (las longitudes son variables)

Problema

Paso 1 : dada una lista de números, genere todos los grupos posibles (en orden) dado solo el número final de grupos deseados.

Por ejemplo, si mi lista de números fuera 1 a 4, y quisiera 2 grupos finales, las posibilidades serían:

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

Paso 2 : Realizar operaciones aritméticas en esos grupos.

Por ejemplo, si elegimos la adición, los resultados finales serían:

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

Investigación previa y problemas similares

He visto numerosos ejemplos en SO y en otros lugares para problemas que involucran cantidades variables de grupos, que utilizan rangos y para bucles, a la:

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

Pero eso es lo opuesto a lo que quiero: allí, las longitudes de los grupos en sí están fijas, excepto la final, y el número de grupos oscila.

Esto no es tarea, solo un problema interesante que encontré. Idealmente, tendría que ser capaz de recorrer esas sublistas separadas para poder realizar las operaciones matemáticas, por lo que también deberían ser capturadas.

Tengo la sensación de que la solución involucrará a los instrumentos, pero parece que no puedo entender la combinatoria con aspecto de agrupación.

Edición / Extensión del Paso 2

Si quiero realizar diferentes operaciones en cada una de las particiones, ¿puedo enfocar esto de la misma manera? En lugar de especificar solo int. agregue , ¿puedo realizar otra combinación de todas las 4 operaciones principales? Es decir:

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

Terminaría con posibilidades de:

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

El orden de las operaciones puede ser ignorado .

Solución final

 #!/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) 

Paso 1 : la forma más fácil que he encontrado al pensar en dividir las listas en grupos así es tratar de obtener combinaciones de ubicaciones divididas. Aquí hay una implementación:

 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]]] 

Paso 2 : Primero necesitas convertir una lista como [[1], [2, 3, 4]] , a uno como [1, 234] . Puedes hacer esto con la siguiente función:

 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] 

Ahora puede realizar su operación en la lista resultante usando reduce() :

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

Solución completa: según la necesidad de referencia de edición para diferentes operadores:

 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 

Si está en Python 2.6 o inferior e itertools.combinations_with_replacement() no está disponible, puede usar la receta que se encuentra aquí .

Raymond Hettinger ha escrito una receta para encontrar todas las particiones de un iterable en n grupos:

 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) 

rendimientos

 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 

Paso 1:

Trabajé en todas las combinaciones posibles de los índices:

 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)) 

Ejemplo:

 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]] """ 

Paso 2:

Primero tenemos que transformar el grupo de dígitos en números:

 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] """ 

Y luego con reduce y el operator realizar la aritmética:
(Aunque este último subpaso no está realmente relacionado con su problema)

 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 """