Задача
Шаг 1 : Учитывая список чисел, сгенерируйте все возможные группировки (по порядку), учитывая только конечное число желаемых групп.
Например, если мой список чисел был от 1 до 4, и я хотел 2 заключительные группы, возможности были бы:
[1], [2,3,4]
[1,2], [3,4]
[1,2,3], [4]
Шаг 2 : Выполнить арифметические операции над этими группами.
Например, если мы выберем дополнение, окончательные результаты будут такими:
1 + 234 = 235
12 + 34 = 46
123 + 4 = 127
Предыдущие исследования и подобные проблемы
Я видел множество примеровна SO и в других местах для проблем, связанных с переменной , составляет групп, которые используют диапазоны и для циклов, а-ля:
print [num_list[i:i+groups] for i in range(0,len(num_list),groups)]
Но это как бы наоборот того, что я хочу - там,длина самих групп фиксирована, за исключением последней, а количество групп колеблется.
Это не домашняя работа, а просто интересная проблема, с которой я столкнулся.В идеале мне нужно было бы иметь возможность перебирать эти отдельные подсписки для выполнения математических операций, поэтому их также нужно было бы захватывать.
У меня есть ощущение, что решение будет включать itertools,но я не могу понять комбинаторику с аспектом группировки.
Редактирование / расширение шага 2
Если я хочу выполнить другой операции на каждом из разделов, могу ли я подойти к этому так же?Вместо того, чтобы указывать только int. add , могу ли я каким-то образом выполнить еще одну комбинацию всех основных четырех операций?Т.е.:
symbol_list = ['+','-','*','/']
for op in symbol_list:
#something
Я бы в конечном итоге имел возможность:
1 + 2 * 34
1 * 2 - 34
1 / 2 + 34
etc.
Порядок операций можно игнорировать .
Окончательное решение
#!/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)