Оптимизация решения задачи на перестановки

Question

Нужно вывести на экран все сочетания с повторениями чисел от 0 до n длины n, сумма чисел в которых кратна n+1. Например, при n=3, программа должна вывести:

Вот решение полным перебором:

from itertools import combinations_with_replacement as cwr

n = int(input())
arr = range(0, n + 1)

for i in cwr(arr, n):
    if sum(i) % (n + 1) == 0:
        print(*i)

Для небольших n оно выполняется достаточно быстро, но все же не является оптимальным. За счет чего его можно оптимизировать?

Answer 1

Задача о наборе суммы с ограничением слагаемых и их числа. Рекурсивное решение.

Возможные дальнейшие оптимизации:

избавиться от перераспределения списка a[], сделать его глобальным, заполнять неиспользованый остаток нулями
вызывать calсsum в цикле только для тех значений i, для которых есть шанс получить решение (ограничения в range и сверху, и снизу)

def calcsum(s, idx, maxx, n, a):
    if s == 0:
        for i in range(idx, n):
            a[i] = 0
        print(a)
        return
    if idx >= n:
        return
    for i in range(min(s, maxx), 0, -1):
        a[idx] = i
        calcsum(s - i, idx + 1, i, n, a)

def nsums(n):
    a = [0]*n
    for t in range(n * n  // (n + 1) + 1):
        s = t * (n + 1)
        calcsum(s, 0, n, n, a)

nsums(3)

>>>
[0, 0, 0]
[3, 1, 0]
[2, 2, 0]
[2, 1, 1]
[3, 3, 2]

Answer 2

Сперва решим другой вопрос: как сильно можно оптимизировать решение задачи?

Текущее решение имеет сложность Cnk(2n, n) * n. Первый множитель - число сочетаний с повторениями, если длина сочетания n, а количество элементов в множестве n + 1. Второй множитель - вызов функции sum для списка из n элементов. Сложности проверки суммы и печати тоже укладываются в n.

Насколько может быть улучшена эта сложность? Для оценки я воспользуюсь фактом: сложность алгоритма не может быть лучше чем объём результата работы. Факт почти очевиден если примем что для печати одного элемента результата нужно постоянное время. Объём результата равен (Cnk(2n, n) / (n + 1)) * n. Первый множитель - число комбинаций у которых сумма делится на n + 1 (это можно доказать, я опускаю доказательство для краткости). Второй множитель - длина сочетания.

Собирая вместе обе оценки можно сказать: ваш алгоритм работает в n + 1 раз медленнее чем мог бы. Много это или мало? Скорее мало: объём печати растёт с n экспоненциально: если n увеличивается на единицу, количество сочетаний возрастает примерно в четыре раза. Уже для n = 16 время работы - минуты, для n = 19 - часы, для n = 21 - дни.

Если О-большое улучшить можно, константу скорее всего нет. Ваше решение очень простое. Почти весь код который работает в цикле написан на C и исполняется очень быстро - раз в десять-пятьдесят быстрее чем если бы он был написан на Питоне.

Код ниже имеет оптимальную сложность (Cnk(2n, n) / (n + 1)) * n (в терминах О-большого лучше написать Cnk(2n, n)):

def print_combinations(n):
     a = [0] * n

    def search(i, min_term, target):
        if i == n:
            print(*a)
            return

        r = range(max(min_term, target - (n - i - 1) * n), target // (n - i) + 1)
        assert len(r) > 0
        for term in r:
            a[i] = term
            search(i + 1, term, target - term)

    for t in range(0, n * n, n + 1):
        search(0, 0, t)

Этот код следует идее из ответа MBo: печатать сочетания для разных сумм (0, n + 1, 2(n + 1), ...) отдельно.

Лес из деревьев вызовов функции search для n = 4:

*           *                *           *
|         /   \           /  |  \        |
0        0     1        0    1    2      3
|       / \     \      /|   /|\   |      |
0      0   1     1    2 3  1 2 3  2      4
|     /|   |\    |    | |  | | |  |\     |
0    1 2   1 2   1    4 3  4 3 3  2 3    4
|    | |   | |   |    | |  | | |  | |    |
0    4 3   3 2   2    4 4  4 4 3  4 3    4

Во всех листьях search печатает сочетание - сложность n. Во внутренних узлах дерева время работы search пропорционально числу исходящих рёбер.

Оценим суммарное число рёбер во всех деревьях. Каждый путь в дереве завершается в листе (тоже самое можно сказать по другому - алгоритм не просматривает тупиковые поддеревья, про это assert в коде). Длина каждого пути в ребрах - n. Следовательно всего рёбер не более <число листьев> * n, а число листьев - это число комбинаций в результате: Cnk(2n, n) / (n + 1).

Общее время обработки внутренних узлов леса (Cnk(2n, n) / (n + 1)) * n. Общее время печати сочетаний оценивается той же формулой. Следовательно сложность оптимальная. А константа не самая лучшая - много операций, все на Питоне.

Для сравнения времена работы двух вариантов. Оптимальный быстрее, но разница не такая большая из-за констант:

      время работы    множитель       относительное
 n   cwr_sum search   времени (с)      ускорение

 1    1.38    2.28    *     0.0000001    0.61 
 2    2.18    4.70    *     0.0000001    0.46 
 3    4.94   11.3     *     0.0000001    0.44 
 4    1.51    3.22    *     0.000001     0.47 
 5    5.22    9.78    *     0.000001     0.53 
 6    1.90    3.06    *     0.00001      0.62 
 7    7.17   10.3     *     0.0001       0.70 
 8    2.80    3.54    *     0.001        0.79 
 9    1.15    1.24    *     0.01         0.93 
10    4.11    4.45    *     0.01         0.92 
11    1.66    1.58    *     0.1          1.05 
12    6.41    5.60    *     0.1          1.14 
13    2.63    2.03    *     1            1.30 
14   10.4     7.40    *     1            1.41 
15    4.19    2.75    *    10            1.52 
16    1.63    1.03    *   100            1.58 
17    6.60    3.83    *   100            1.72 
18    2.67    1.45    *  1000            1.84 
19   10.8     5.52    *  1000            1.96 
20    4.52    2.15    * 10000            2.10

БЛОГ НА HUSL

Оптимизация решения задачи на перестановки

Ответы (2 шт):