У меня есть некоторый кортеж в python. Предел пропускной способности, например, равен 5. Я хочу разбить кортеж в подмножествах, ограниченный суммой из них:
Например:
input: (3, 1, 4, 2, 2, 1, 1, 2) and capacity = 5
output: (3, 1) (4) (2, 2, 1) (1, 2) #each subtuple is less than 5, order safe.
Я ищу красивое выразительное решение этой задачи, предпочтительнее в функциональном стиле программирования (например, с помощью itertools.dropwhile или что-то в этом роде)
Вы можете инкапсулировать нефункциональную часть и вызвать ее из функционального кода:
from itertools import groupby
class GroupBySum:
def __init__(self, maxsum):
self.maxsum = maxsum
self.index = 0
self.sum = 0
def __call__(self, value):
self.sum += value
if self.sum > self.maxsum:
self.index += 1
self.sum = value
return self.index
# Example:
for _, l in groupby((3, 1, 4, 2, 2, 1, 1, 2), GroupBySum(5)):
print(list(l))
Я не мог с этим поделать, но написал что-то близкое к тому, что я делал бы в Haskell (хотя я все еще несколько питонов):
def take_summed(xs, cap):
if len(xs) <= 1:
return xs, ()
else:
x, *rest = xs
if x > cap:
return (), xs
else:
init, tail = take_summed(rest, cap - x)
return (x,) + tuple(init), tail
def split(xs, cap=5):
if len(xs) <= 1:
yield xs
else:
chunk, rest = take_summed(xs, cap)
yield chunk
if rest != ():
yield from split(rest, cap)
Не стесняйтесь разделить функции на подзадачи. Результат:
In [45]: list(split((3, 1, 4, 2, 2, 1, 1, 2), 5))
Out[45]: [(3, 1), (4,), (2, 2, 1), (1, 2)]
Проблема с тем, чтобы сделать это короче, заключается не в том, что он не выполним без побочных эффектов, а в том, что вам нужно нести дополнительное накопленное состояние, поэтому даже при использовании reduce вам нужно будет изобрести что-то действительно сложное, чтобы обойти сумма между приложениями.
Здесь немного отличается подход от @Jean, который срезает входной кортеж вместо создания меньших списков с добавлением и предлагает небольшое повышение производительности:
def group_by_capacity(tup, capacity=5):
t = iter(tup)
curr, s = 0, next(t)
for i, v in enumerate(t, 1):
if s + v > capacity:
yield tup[curr:i]
curr = i
s = v
else:
s += v
yield tup[curr:]
>>> list(group_by_capacity((3, 1, 4, 2, 2, 1, 1, 2)))
[(3, 1), (4,), (2, 2, 1), (1, 2)]
Некоторое время:
In [35]: from random import randrange
In [36]: start = tuple((randrange(1,5) for _ in range(100000)))
In [37]: %%timeit
....: list(group_by_capacity(start))
....:
10 loops, best of 3: 47.4 ms per loop
In [38]: %%timeit
....: list(generate_tuple(start))
....:
10 loops, best of 3: 61.1 ms per loop
Я немного удивлен, что никто еще не использовал itertools.accumulate с ключевой функцией. Во всяком случае, моя запись:
from itertools import groupby, accumulate
def sumgroup(seq, capacity):
divided = accumulate(enumerate(seq),
lambda x,y: (x[0],x[1]+y[1])
if x[1]+y[1] <= capacity else (x[0]+1,y[1]))
seq_iter = iter(seq)
grouped = groupby(divided, key=lambda x: x[0])
return [[next(seq_iter) for _ in g] for _,g in grouped]
Существует множество вариантов, например. вы можете использовать zip(seq, divided), чтобы избежать seq_iter и т.д., но это был первый способ, который пришел на ум. Это дает мне
In [105]: seq = [3, 1, 4, 2, 2, 1, 1, 2]
In [106]: sumgroup(seq, 5)
Out[106]: [[3, 1], [4], [2, 2, 1], [1, 2]]
и согласуется с результатом GroupBySum:
In [108]: all(sumgroup(p, 5) == [list(l) for _, l in groupby(p, GroupBySum(5))]
...: for width in range(1,8) for p in product(range(1,6), repeat=width))
...:
...:
Out[108]: True
Я ждал первого ответа, чтобы обеспечить немного функциональный подход:
start = (3, 1, 4, 2, 2, 1, 1, 2)
def generate_tuple(inp):
current_sum = 0
current_list = []
for e in inp:
if current_sum + e <= 5:
current_list.append(e)
current_sum += e
else:
if current_list: # fixes "6" in first position empty tuple bug
yield tuple(current_list)
current_list = [e]
current_sum = e
yield tuple(current_list)
print([i for i in generate_tuple(start)])
результат:
[(3, 1), (4,), (2, 2, 1), (1, 2)]
EDIT: я нашел полный функциональный подход, используя эффект памяти, иначе это не выполнимо. Это уродливо, и мне больно, только когда я думаю, как я это объясню. Я немного запустил набор входных данных или это было бы слишком легко
start = (6, 7, 3, 1, 4, 2, 2, 1, 1, 2, 3, 1 ,3, 1, 1)
теперь код. 3 линии, получить аспирин, вам понадобится столько, сколько я сделал:
mem=[0,0]
start = start + (5,)
print([start[mem[-2]:n] for i in range(0,len(start)) for n in range(i+1,len(start)) if ((n==i+1 and start[i]>=5) or (sum(start[mem[-1]:n])<=5 and sum(start[mem[-1]:n+1])>5)) and not mem.append(n)])
Я попытаюсь объяснить.
mem и устанавливается на 0,0 при запускеmem. Поскольку append возвращает None, последнее условие выполняется всегда true((n==i+1 and start[i]>=5) означает обнаружение одиночных значений, больших или равных 5.Не уверен, зачем они нужны в кортежах, но если вы этого не сделаете, вы можете просто удалить кастинг tuple(...):
def chunkit(tpl, capacity):
ret = []
cur = []
for x in tpl:
if sum(cur) + x > capacity:
ret.append(tuple(cur))
cur = [x]
else:
cur.append(x)
if cur != []:
ret.append(tuple(cur))
return tuple(ret)
Несколько примеров:
In [24]: chunkit((3, 1, 4, 2, 2, 1, 1), 5)
Out[24]: ((3, 1), (4,), (2, 2, 1), (1,))
In [25]: chunkit((3, 1, 4, 2, 2, 1, ), 5)
Out[25]: ((3, 1), (4,), (2, 2, 1))
In [26]: chunkit((3, 1, 4, 2, 2, 1, 5), 5)
Out[26]: ((3, 1), (4,), (2, 2, 1), (5,))
In [27]: chunkit((3, 1, 4, 2, 2, 1, 5, 6), 5)
Out[27]: ((3, 1), (4,), (2, 2, 1), (5,), (6,))
In [28]: chunkit((3, 1, 4, 2, 2, 1, 5, 6, 1, 6), 5)
Out[28]: ((3, 1), (4,), (2, 2, 1), (5,), (6,), (1,), (6,))
Не знаю, считается ли это функциональным, но это самое близкое, о чем я мог подумать:
def groupLimit(iterable, limit):
i, cSum = 0, 0
def pred(x):
nonlocal i, cSum, limit
i, cSum = (i + 1, x) if (x + cSum) > limit else (i, cSum + x)
return i if x <= limit else -1
return (tuple(g) for k, g in itertools.groupby(iterable, pred) if k != -1)
Это также будет сортировать одиночные значения, превышающие предел. Если это не означает, что последние две строки могут быть изменены на:
return i
return (tuple(g) for k, g in itertools.groupby(iterable, pred))
Пример:
t = (3, 1, 6, 2, 2, 1, 1, 2)
a = groupLimit(t,5)
print(tuple(a))
# version 1 -> ((3, 1), (2, 2, 1), (1, 2))
# version 2 -> ((3, 1), (6,), (2, 2, 1), (1, 2))
Позволяет определить powerset с помощью itertools
from itertools import chain, combinations
def powerset(lst):
for subset in chain.from_iterable(combinations(lst, r) for r in range(len(lst)+1)):
yield subset
Тогда мы можем сделать это в однострочном
[subset for subset in powerset(input) if sum(subset)<=capacity]
Более общее решение:
def groupwhile(iterable,predicate,accumulator_function):
continue_group = False
iterator = iter(iterable)
try:
accumulated = next(iterator)
except StopIteration:
return
current_group = [accumulated]
for item in iterator:
continue_group = predicate(accumulated,item)
if continue_group:
current_group.append(item)
accumulated = accumulator_function(accumulated,item)
else:
yield current_group
accumulated = item
current_group = [item]
yield current_group
#your case
assert (list(groupwhile(
(3, 1, 4, 2, 2, 1, 1, 2),
lambda previous_sum,item: previous_sum + item <= 5,
lambda previous_sum,item: previous_sum + item,
))) == [[3, 1], [4], [2, 2, 1], [1, 2]]
#equivalent to groupby with key not set
assert (list(groupwhile(
(3, 1, 4, 2, 2, 1, 1, 2),
lambda previous_item,item: previous_item == item,
lambda _,item: item,
))) == [[3], [1], [4], [2, 2], [1, 1], [2]]
#break on duplicates
assert (list(groupwhile(
(3, 1, 4, 2, 2, 1, 1, 2),
lambda previous_item,item: previous_item != item,
lambda _,item: item,
))) == [[3, 1, 4, 2], [2, 1], [1, 2]]
#start new group when the number is one
assert (list(groupwhile(
(3, 1, 4, 2, 2, 1, 1, 2),
lambda _,item: item != 1,
lambda _1,_2: None,
))) == [[3], [1, 4, 2, 2], [1], [1, 2]]
Мое решение, не очень чистое, но оно просто уменьшает:
# int, (int, int, ...) -> ((int, ...), ...)
def grupBySum(capacity, _tuple):
def _grupBySum(prev, number):
counter = prev['counter']
result = prev['result']
counter = counter + (number,)
if sum(counter) > capacity:
result = result + (counter[:-1],)
return {'counter': (number,), 'result': result}
else:
return {'counter': counter, 'result': result}
result = reduce(_grupBySum, _tuple, {'counter': (), 'result': ()}).values()
return result[1] + (result[0],)
f = (3, 1, 4, 2, 2, 1, 1, 2)
h = grupBySum(5, f)
print(h) # -> ((3, 1), (4,), (2, 2, 1), (1, 2))