在函数编程风格中具有容量限制的子元中拆分python元组

Question

我在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例如使用或类似的东西)

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

Answer 2

我无法帮助它,但写了一些接近我在Haskell中所做的事情(我认为仍然有些pythonic):

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你需要发明一些非常复杂的东西,以传递应用程序之间的总和.

Answer 3

我有点惊讶还没有人使用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