Наиболее эффективный способ объединить список списков, чтобы получить группы элементов <=, но как можно ближе к длине X

Question

Скажем, у меня есть список списков, например:

 [ [ a1, a2, a3, a4, a5], [b1, b2, b3, b4, b5, b6, b7, b8], [c1, c2, c3, c4, c5, c6], [d1, d2, d3, d4] ]

Какой самый простой способ сравнить все длины элементов списка и объединить их в список списков с длинами, максимально близкими, но меньшечем или равно, x?

Так же с приведенным выше примером, и x = 12:

[ [a1, a2, a3, a4, a5, c1, c2, c3, c4, c5, c6], [b1, b2, b3, b4, b5, b6, b7, b8, d1, d2, d3, d4] ]

Порядок отдельных групп (например, a, b, c ...)в выводе это не важно, но отдельные группы не могут быть разбиты.

Я знаю, что могу, например, взять длину первой группы, а затем получить длину каждой последующей группы по порядку, и еслиих сумма = x, затем вытолкните эти списки и добавьте их элементы в возвращенный список, а если нет, то снова проработайте каждую группу, проверяя, равна ли сумма их длин = x-1, и если да, то выскочит и добавьте, и далее с суммой длин= x-2 и т. д. до тех пор, пока список ввода не станет пустым.

Что будет хорошо работать для небольших групп, как в приведенном примере, но как быть, когда длина списка ввода становится очень большой?Есть ли более эффективный метод / алгоритм?

Answer 1

Кажется, проблема с упаковкой в ​​бункер.

Мой жадный алгоритм с заменой и предварительной сортировкой должен работать, но вам нужно будет адаптировать длину подсписка к высоте изображения и вычислить начальный счетчик бинов из вашего x иобщая длина предметов.

Answer 2

Это решение не обязательно находит оптимальное по длине решение, так как рассматривает возможность объединения только двух списков, но работает в O (n).

#!/usr/bin/env python3

import sys
import random

def foo(xs, n):
    bins = {}
    mid = (n+1)//2

    # bin list positions by length
    for i, x in enumerate(xs):
        bucket = len(x)
        if bucket > n:
            raise RuntimeError("invalid input")

        bins.setdefault(bucket, []).append(i)

    # take out ones that are the desired length already
    out = [xs[x] for x in bins[n]] if n in bins else []
    bins.pop(n, None)

    # find complements for the upper half of buckets
    for i in list(bins.keys()):
        if i < mid:
            continue

        candidates = sorted([x for x in list(bins.keys()) if x <= n-i], reverse=True)

        while i in bins and bins[i]:
            x = bins[i].pop()

            for j in list(candidates):
                if j not in bins or not bins[j]:
                    candidates = candidates[1:]
                    continue

                y = bins[j].pop()
                if not bins[j]:
                    del bins[j]

                out.append(xs[x] + xs[y])
                break
            else:
                # complement not found
                out.append(xs[x])


    # add lists with no complements from the lower half
    out += [xs[y] for ys in bins.values() for y in ys]

    return out

_check_n = 0
def check(n, xs):
    ys = list(foo(xs, n))

    try:
        for y in ys:
            assert len(y) <= n
        print(".", end="")
        n+=1
        if n % 10 == 0:
            sys.stdout.flush()
    except:
        print("n, xs =", (n, xs))
        print("ys =", ys)
        raise

if __name__ == "__main__":
    n, xs = 12, [ ["a1", "a2", "a3", "a4", "a5"], ["b1", "b2", "b3", "b4", "b5", "b6", "b7", "b8"], ["c1", "c2", "c3", "c4", "c5", "c6"], ["d1", "d2", "d3", "d4"] ]
    check(n, xs)

    cases = 10**4
    max_n = 10**2
    max_input_len = 10**3

    for i in range(cases):
        n = random.randint(1, max_n)
        xs = [[1] * random.randint(1, n) for j in range(random.randint(1, max_input_len))]
        check(n, xs)