Сплит-кортеж python в подзаголовках с ограничением емкости в стиле функционального программирования

Ответ 1

Вы можете инкапсулировать нефункциональную часть и вызвать ее из функционального кода:

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

Ответ 2

Я не мог с этим поделать, но написал что-то близкое к тому, что я делал бы в 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 вам нужно будет изобрести что-то действительно сложное, чтобы обойти сумма между приложениями.

Ответ 3

Здесь немного отличается подход от @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

Ответ 4

Я немного удивлен, что никто еще не использовал 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

Ответ 5

Я ждал первого ответа, чтобы обеспечить немного функциональный подход:

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 при запуске
• поскольку функция игнорирует последний элемент, я изменяю входные данные, чтобы добавить пороговое значение к предыдущим значениям, не отбрасывается
• Единственная простая вещь - вычисление 2 сумм и обнаружение индекса, из которого он превышает порог. Когда этот порог обнаружен, оба условия выполняются, и активируется третье условие: индекс хранения в mem. Поскольку append возвращает None, последнее условие выполняется всегда true
• Это ((n==i+1 and start[i]>=5) означает обнаружение одиночных значений, больших или равных 5.
• Остальная часть - тонкая настройка до тех пор, пока результат не будет таким же, как и процедурный подход, который теперь выглядит не так уж плохо:)

Ответ 6

Не уверен, зачем они нужны в кортежах, но если вы этого не сделаете, вы можете просто удалить кастинг 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,))

Ответ 7

Не знаю, считается ли это функциональным, но это самое близкое, о чем я мог подумать:

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

Ответ 8

Позволяет определить 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]

Ответ 9

Более общее решение:

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

Ответ 10

Мое решение, не очень чистое, но оно просто уменьшает:

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