Элегантное и оптимизированное решение для функции, которая группирует списки под пороговой длиной в python

Question

Учитывая список L, например, [[1,1,1,1], [1,1,1], [1,1], [1]] и max_len=8 Я хотел бы создать новый список LN, как это [[[1, 1, 1, 1], [1, 1, 1]], [[1, 1], [1]]].

Итак, у меня есть список списки. Я хочу сгруппировать списки таким образом, чтобы сумма длин каждого списка была <= max_len. Вам нужно сохранить списки такими, как они есть, в том же порядке, чтобы можно было сгруппировать только последовательные списки. </p>

Я пытался сделать это наиболее Pythoni c и эффективным способом. Должно быть O (n). С помощью кого-то, у меня есть этот код:

def chunks(list_to_chunck, max_len):
    if any(len(sub_list) > max_len for sub_list in list_to_chunck):
        return None

    new_list = []
    while list_to_chunck:
        copy_list = [list_to_chunck.pop(0)]
        while list_to_chunck:
            if len(list_to_chunck[0]) + sum(len(sub_list) for sub_list in copy_list) <= max_len:
                copy_list.append(list_to_chunck.pop(0))
            else:
                break
        new_list.append(copy_list)

    return new_list

Answer 1

Вы можете использовать переменную size, чтобы отслеживать текущий размер последнего подсписка в списке вывода, и всякий раз, когда он будет превышать max_len после добавления текущего подсписка в итерации, добавляйте новый подсписок к выходу. Инициализируйте size значением, большим max_len, чтобы он всегда добавлял новый подсписок в первой итерации. При таком подходе сложность времени будет O (n) :

def chunks(lst, max_len):
    output = []
    size = max_len + 1
    for s in lst:
        size += len(s)
        if size > max_len:
            output.append([])
            size = len(s)
            if size > max_len:
                return
        output[-1].append(s)
    return output

, так что chunks([[1, 1, 1, 1], [1, 1, 1], [1, 1], [1]], 8) возвращает:

[[[1, 1, 1, 1], [1, 1, 1]], [[1, 1], [1]]]

Answer 2

Генераторное решение:

def group_subseqs(seq, max_len):
    curr_size = 0
    result = []
    for subseq in seq:
        len_subseq = len(subseq)
        if curr_size + len_subseq <= max_len:
            result.append(subseq)
            curr_size += len_subseq
        else:
            if result:
                yield result
                if len_subseq <= max_len:
                    result = [subseq]
                    curr_size = len_subseq
                else:
                    return
            else:
                return
    if result:
        yield result

работает так, как ожидалось (вроде ... перестает давать результат, если подсписок больше max_len вместо того, чтобы вообще ничего не выдавать):

a = [[1,1,1,1], [1,1,1], [1,1], [1]]
print(list(group_subseqs(a, 8)))
# [[[1, 1, 1, 1], [1, 1, 1]], [[1, 1], [1]]]

print(list(group_subseqs(a, 4)))
# [[[1, 1, 1, 1]], [[1, 1, 1]], [[1, 1], [1]]]

print(list(group_subseqs(a, 3)))
# []

print(list(group_subseqs(a[::-1], 3)))
# [[[1], [1, 1]], [[1, 1, 1]]]

Answer 3

Похоже, у вас нет никаких ограничений на общее количество списков, поэтому жадный подход подойдет:

def chunks(items, max_len):
    ret = [[]]
    remaining = max_len
    for i in items:
        if len(i) > remaining:
            ret.append([])
            remaining = max_len
            if len(i) > remaining:
                return None  # Could raise on impossible
        ret[-1].append(i)
        remaining -= len(i)
    return ret

на вашем примере:

items = [[1,1,1,1], [1,1,1], [1,1], [1]]
assert chunks(items, 8) == [[[1, 1, 1, 1], [1, 1, 1]], [[1, 1], [1]]]

Просмотр других ответы, это в значительной степени соответствует, поэтому я хотел добавить менее читабельный вариант, без гарантии длины =)

def chunks(items, max_len):
    count = [0, 0]
    def group(item): 
        count[1] += len(item)
        if count[1] >= 8:
            count[0] += 1
            count[1] = 0
        return count[0]
    return [list(v) for k, v in itertools.groupby(data, key=group)]

Answer 4

Вот эскиз подхода, который будет O (N). Создает новый список и не изменяет оригинал. Он не обрабатывает все крайние случаи, но это должно помочь вам:

In [1]: data = [[1,1,1,1], [1,1,1], [1,1], [1]]
   ...:

In [2]: def chunks(nested, maxlen):
   ...:     total = 0
   ...:     result = []
   ...:     piece = []
   ...:     for sub in nested:
   ...:         length = len(sub)
   ...:         if total + length > maxlen:
   ...:             result.append(piece)
   ...:             piece = [sub]
   ...:             total = length
   ...:         else:
   ...:             piece.append(sub)
   ...:             total += length
   ...:     if piece:
   ...:         result.append(piece)
   ...:     return result
   ...:

In [3]: chunks(data, 8)
Out[3]: [[[1, 1, 1, 1], [1, 1, 1]], [[1, 1], [1]]]