python - 算法 : how to split list data into fixed size sub-lists without having separate numbers

Question

我有一道算法题要问你。不需要应用程序上下文，我会给你一个直接的例子。

这是一个可能的输入:input = [ 1, 1, 1, 2, 2, 2, 2, 3, 3, 4, 4, 4 ]。 假设批量大小为 5。 这里的想法是输出最大大小为 5 的列表，而没有单独的数字，简而言之:2 个相同的数字不能在单独的子列表中。 示例输出:[ [1, 1, 1], [2, 2, 2, 2], [3, 3, 4, 4, 4] ]

假设:数字总是排序的，batch_size 总是大于可能的数字数量

你有比我刚刚找到的更优雅的解决方案吗？

i = 0
batch_size = 5
res = []
while i < len(input):
    # Retrieve the data list according to the batch size
    data = input[i: i + size]
    # Increment the index
    i += size
    # See what's the next output looks like
    future_data = input[i: i + size]
    if future_data and future_data[0] == data[-1]:
        # So we count how many times this number appears in our current list 
        # and subtract that from our index
        cp = data.count(data[-1])
        i -= cp
        # Then remove from the current list all occurrence of that number
        data = data[:-cp]
    res.append(data)

编辑:根据@juanpa.arrivillaga 的回答:

感谢大家的 react 和回答。

我继续第 2 集，我在这里给了你我的简化问题，我认为你的解决方案就足够了，尽管你的回应，我不知道如何使 @juanpa.arrivillaga 的解决方案适应我的数据格式，事实上输入看起来更像是:

input = { 
    'data_1' : { 
        'id': [1, 1, 1, 2, 2, 2, 2, 3, 3, 4, 4, 4], 
        'char': ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L'] 
    }
}

!'id' 和 'char' 值列表的大小必须相等!

输出必须如下所示:

[ 
    [1, 'A', 1, 'B', 1, 'C'], 
    [2, 'D', 2, 'E', 2, 'F', 2, 'G'], 
    [3, 'H', 3, 'I', 4, 'J', 4, 'K', 4, 'L'] 
]

我知道数据结构不是最优的，不幸的是我没有手，因此无法更改...

还是和之前一样的约束(batch size 只作用于 id，我够清楚了吧？)

Answer 1

以下是我将如何一次性完成此操作:

>>> import itertools
>>> batch_size = 5
>>> result = [[]]
>>> input_data = [ 1, 1, 1, 2, 2, 2, 3, 3, 4, 4, 4 ]
>>> for _, g in itertools.groupby(input_data):
...     current = list(g)
...     if len(result[-1]) + len(current) <= batch_size:
...         result[-1].extend(current)
...     else:
...         result.append(current)
...
>>> result
[[1, 1, 1], [2, 2, 2, 3, 3], [4, 4, 4]]

让我们将其分解为中间步骤以帮助理解，首先，这是 itertools.groupby 热切评估的内容:

>>> import itertools
>>> batch_size = 5
>>> grouped = [list(g) for k,g in itertools.groupby([ 1, 1, 1, 2, 2, 2, 3, 3, 4, 4, 4 ])]
>>> grouped
[[1, 1, 1], [2, 2, 2], [3, 3], [4, 4, 4]]

然后，简单地建立你的结果，这是一个子列表列表。如果它可以放入当前子列表，则将该组添加到子列表，否则，附加一个由该组组成的新子列表(我们可以假设它不大于​​ batch_size):

>>> result = [[]]
>>> for group in grouped:
...     if len(result[-1]) + len(group) <= batch_size:
...         result[-1].extend(group)
...     else:
...         result.append(group[:])
...
>>> result
[[1, 1, 1], [2, 2, 2, 3, 3], [4, 4, 4]]

上面对数据进行了两次传递，发布的第一个示例进行了一次传递。

请注意，如果使用 itertools.groupby 感觉像是在“作弊”，您可以实现一些相对容易的方法来解决这种情况:

def simple_groupby(data):
    it = iter(data)
    empty = object()
    current = next(it, empty)
    if current is empty:
        return
    prev = current
    acc = [current]
    for current in it:
        if prev == current:
            acc.append(current)
        else:
            yield acc
            acc = [current]
        prev = current
    yield acc