数字的k分区数量

Question

我陷入了编写一个算法，以获取数字 $ n $ 的不同分区的量，其中分区为size $ k $ 。重要的是分区中没有任何重复。 例如：

第5号2的分区为：

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

第6号的大小3的分区仅存在：

• [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]

.

我还有一个程序来生成数字 $ n $

的所有不同X级=“math-container”

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 $ 数字，所有这些都是不同的，最多 $ 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] \结束{对齐}

因为我们可以从最大到最小的数字将分区形成分区，因此每当我们采取一些数字时，我们就必须严格更小的所有数字。基本情况是 $ 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} $ （因为我们的号码由 $ n - n'$ ，因此当前分区中的某个数字总和 $ n - n'$ 和size $ k - k'$ 必须最多 $ \ frac {n - n'} {k - k'} $ ）。但这意味着对于任何固定的 $ k'$ ，有大多数 $ \ frac {n ^ {2}}。 {K-K'} $ 可达DP状态，以及

\ begin {等式*} \ sum_ {k'= 0} ^ {k-1} \ frac {n ^ 2} {k-k'}=mathcal {o}（n ^ 2 \ log k） \结束{arequation *}

因此，实际复杂性是 $ \ mathcal {o}（n ^ 2 \ log k）$ 。