алгоритм перебора списков натуральных чисел фиксированного размера с одинаковой суммой

Question

Я ищу быстрый и эффективный алгоритм памяти для перебора всех возможных списков натуральных чисел одинакового размера (S) с заданной суммой (N).

например, если S = ​​3 и N = 4, результатом будет (у меня действительно неэффективное значение al go):

[0, 0, 4]
[0, 1, 3]
[0, 2, 2]
[0, 3, 1]
[0, 4, 0]
[1, 0, 3]
[1, 1, 2]
[1, 2, 1]
[1, 3, 0]
[2, 0, 2]
[2, 1, 1]
[2, 2, 0]
[3, 0, 1]
[3, 1, 0]
[4, 0, 0]

Не обязательно в таком порядке. Другой способ взглянуть на это - как разрезать число N на S. Алгоритм был бы идеальным, если бы я мог также установить максимум для каждого отдельного значения в списках.

Я бы использовал это для запуска многомерных массивов в другом порядке, чем в product(*indices).

Также генерирование всех комбинаций индексов и их сортировка по сумме будет слишком медленным / занимать память.

Answer 1

Нашел решение: оно основано на идее, что положительное число N - это строка единиц, а разбиение их на S частей - это вопрос размещения (S-1) разделителей в списке. Эти разделители могут повторяться с combinations(range(N + S - 1), S - 1). Следующим шагом является вычисление количества единиц до, между и после разделителей:

def partition(N, size):
    n = N + size - 1
    for splits in combinations(range(n), size - 1):
        yield [s1 - s0 - 1 for s0, s1 in zip((-1,) + splits, splits + (n,))]

Когда вы хотите ограничить каждый элемент в результате, вы можете отфильтровать нежелательные (конечно, не оптимально, но я хотел использовать combinations, потому что он, вероятно, реализован в C, и, следовательно, вероятно, намного быстрее, чем все, что я могу придумать в python). Простая версия:

def sized_partition_slow(N, sizes):
    size = len(sizes)
    n = N + size - 1
    for splits in combinations(range(n), size - 1):
        result = [s1 - s0 - 1 for s0, s1 in zip((-1,) + splits, splits + (n,))]
        if all(r < s for r, s in zip(result, sizes)):
            yield result

И более быстрая, но более сложная версия:

def sized_partition(N, sizes):
    size = len(sizes)
    n = N + size - 1
    for splits in combinations(range(n), size - 1):
        result = []
        for s, s0, s1 in zip(sizes, (-1,) + splits, splits + (n,)):
            r = s1 - s0 - 1
            if r >= s:
                break
            result.append(r)
        else:
            yield result

Я использовал это как ранний тест:

for indices in partition(4, 3):
    assert sum(indices) == 4
    assert all(0 <= i for i in indices)

for indices in sized_partition(4, [3, 3, 3]):
    assert sum(indices) == 4
    assert all(0 <= i < 3 for i in indices)

Кстати: от hip: вы можете сгенерировать решение задачи целочисленного разбиения, перебирая S (размер): как в:

def integer_partition(N, order=False):
    result = set()
    for size in range(1, N+1):
        for splits in combinations(range(1, N), size - 1):
            if order:
                p = tuple(s1 - s0 for s0, s1 in zip((0,) + splits, splits + (N,)))
            else:
                p = tuple(sorted(s1 - s0 for s0, s1 in zip((0,) + splits, splits + (N,))))
            result.add(p)
    return sorted(result, key=lambda r: (len(r), r))

Я немного адаптировал итератор combinations(), чтобы не давать нули. Это удваивает для тех же разделов с различными заказами, если order=False.

Answer 2

Я думаю, что это самый простой способ:

def elect(S,N,List):
    result_list = []
    for list_val in List:
        if sum(list_val) == N:
            if len(list_val) == S:
                result_list.append(list_val)

    return result_list

это работает при 1 se c для 1 миллиона списков. Если вы хотите закрепить путь, вы можете поместить другие операторы if, такие как if sum (list_val [0: N / 2])> N или len (list_val) / 2> S: такие операторы могут быстрее обнаруживать ситуации.

Другим способом является сортировка списков и поиск первой N числовой суммы. Если он больше, чем вы хотите, вы можете выбрать эти списки.