Количество K-разделов ряда

Question

Я застрял на написании алгоритма для получения количества отдельных разделов для числа $ n $ с размером раздела $ k $ . Важно, чтобы в разделах нет повторения. Например:

Перегородки размера 2 на номер 5:

.
• [4, 1]
• [3, 2]

Перегородки 3 размера 3 для номера 6 существует только о:

.
• [3, 2, 1]

Обратите внимание, что [2, 2, 2] не раздел, потому что он имеет повторяющееся использование 2.

Я в настоящее время внедрил динамический алгоритм, который находит количество разделов, которые позволяют повторить. Здесь $ m $ - это номер и $ n $ - это размер разделов.

def count_partitions(m, n):


    def e_at(i,j):
        if i == j and j == -1:
            return 1
        if i < j:
            return 0
        else:
            return p[i][j]

    p = [[-1 for _ in range(n)] for _ in range(m)]
    for i in range(m):
        p[i][0] = 1

    for i in range(m):
        for j in range(1, min(i + 1, n)):
            if i < 2*j:
                p[i][j] = e_at(i-1,j-1)
            else:
                p[i][j] = e_at(i-1, j-1) + e_at(i-j-1,j)

    return p[m-1][n-1]

.

У меня также есть программа для генерации всех различных отдельных k-разделов ряд $ n $

def generate_partitions(n, k):
    if n == 0:
        return []


    def rec_partition(m, b, n, a, l):
        if m == 0:
            l.append(conj_partition(a[:n]))
        else:
            c = a[n]
            for i in range(1, min(b,m) + 1):
                a[n] = i
                rec_partition(m-i, i, n+1, a, l)
            a[n] = c


    def has_double(l):
        for i in range(len(l) - 1):
            if l[i] == l[i+1]:
                return True
        return False

    l = []
    a = [0] * n

    a[0] = k
    rec_partition(n - k, k,1, a, l)

    return sorted([p for p in l if not has_double(p)], reverse=True)

.

До сих пор единственный способ, которым я нашел, чтобы получить количество отчетных K-разделов, заключается в том, чтобы генерировать их все и принимать длину возвращенного списка.

Однако я чувствую, что будет лучший способ получить сумму, не создавая их всех, изменив алгоритм динамического программирования выше. Но мне не повезло с этим.

У кого-нибудь есть идея, которая поможет?

Answer 1

Вы можете решить это с DP. Пусть $ dp [n] [k] [m] $ обозначает количество разделов $ n $ в $ k $ numbers, все из которых отличаются и на большинстве $ m $ . Тогда у нас есть рецидив

\ begin {align} Dp [n] [k] [m] &=sum_ {v= 1} ^ {m} dp [n-v] [k-1] [V-1] \\ &= Dp [n] [k] [m-1] + dp [n-m] [k-1] [V-M] \ end {align}

Поскольку мы можем принять цифры, образующие раздел из крупнейшего на наименьшее, поэтому всякий раз, когда мы берем некоторое количество, все номера, которые мы берем после этого, должны быть строго меньше. Базовый случай - $ dp [0] [0] [m]= 1 $ Для любого $ m $ И $ dp [x] [y] [m]= 0 $ всякий раз, когда $ x <0 $ или $ y <0 $ . Если вы заботитесь об заказе элементов в разделах, умножите результат на $ k! $ .

Мы можем рассчитать это повторение в $ \ mathcal {o} (n ^ {2} k) $ , но более жесткий анализ дает еще лучшее связанное: .

Для состояния $ (n ', k', m ') $ для достижения этого рецидива от $ Dp [n] [k] [n] $ , мы должны иметь $ m '\ leq \ frac {n-n'} {k-k '} \ leq \ frac {n} {k-k '} $ (поскольку наш номер уменьшился по $ n - n' $ , поэтому какой-то номер в текущем разделе суммы $ n - n '$ и размер $ k - k' $ должен быть максимально $ \ frac {n - n '} {k - k'} $ ). Но это означает, что для любого фиксированного $ k '$ есть больше $ \ frac {n ^ {2}} {k-k '} $ Доступные состояния DP, а также

\ Начало {Уравнение *} \ sum_ {k '= 0} ^ {k-1} \ frac {n ^ 2} {k-k'}=mathcal {o} (n ^ 2 \ log k) \ end {уравнение *}

Таким образом, фактическая сложность является $ \ mathcal {o} (n ^ 2 \ log k) $ .