Python中不使用欧拉恒等式求整数分拆p(n,k)取最大值对应的k值

分拆示例 #

整数分拆指将正整数拆分为若干正整数的和，不计顺序，p(n,k)表示将n拆分为k个正整数之和的方案数，示例如下：
n=4的分拆：

4 = 4                 p(4,1) = 1
  = 1+3, 2+2          p(4,2) = 2
  = 1+1+2             p(4,3) = 1
  = 1+1+1+1           p(4,4) = 1

max(p(4, k)) = 2，对应取值k = 2
n=5的分拆：

5 = 5                 p(5,1) = 1
  = 1+4, 2+3          p(5,2) = 2
  = 1+1+3, 1+2+2      p(5,3) = 2
  = 1+1+1+2           p(5,4) = 1
  = 1+1+1+1+1         p(5,5) = 1

max(p(5, k)) = 2，对应取值k = 2和3

基础公式 #

整数分拆总数p(n)满足公式：p(n) = Σp(n, k) for ∀k: 0<k<=n
示例计算：

• p(4) = p(4, 1) + p(4, 2) + p(4, 3) + p(4, 4) = 1 + 2 + 1 + 1 = 5
• p(5) = p(5, 1) + p(5, 2) + p(5, 3) + p(5, 4) + p(5, 5) = 1 + 2 + 2 + 1 + 1 = 7

原有实现 #

此前使用欧拉恒等式p(n, k) = p(n-1, k-1) + p(n-k, k)编写的Python代码如下，可计算整数分拆总数：

# p(n, k) = p(n-1, k-1) + p(n-k, k)
N = int(input())
p = [[0]*(N+1) for i in range(N+1)]
for i in range(N+1):
    p[i][1] = 1
    p[i][i] = 1
for n in range(2, N+1):
    for k in range(2, n+1):
        p[n][k] = p[n-1][k-1] + p[n-k][k]
print(sum(p[-1])) 
for x in p:
    print(x[1:])
    print(sum(x))

需求与新实现 #

需求：不使用欧拉恒等式，求解使得p(n,k)取最大值的所有k值。

实现思路 #

通过回溯法生成n的所有不重复整数分拆，直接统计每个分拆项数k对应的方案数，最后筛选出方案数最大值对应的所有k值，全程不使用欧拉递推公式。

代码实现 #

def get_max_k(n):
    # count[k]存储p(n,k)的数值
    count = [0] * (n + 1)

    # 回溯生成分拆：last保证分拆项非降，避免重复计数；remain为剩余待拆分数值；current_len为当前分拆的项数
    def backtrack(last, remain, current_len):
        if remain == 0:
            count[current_len] += 1
            return
        # 下一个拆分项不小于上一个，不大于剩余值
        for num in range(last, remain + 1):
            backtrack(num, remain - num, current_len + 1)
    
    backtrack(1, n, 0)
    max_p = max(count)
    # 收集所有符合条件的k值
    max_ks = [k for k in range(1, n + 1) if count[k] == max_p]
    return max_p, max_ks

# 测试调用
if __name__ == "__main__":
    n = int(input("请输入正整数n："))
    max_p_val, target_ks = get_max_k(n)
    print(f"max(p({n},k)) = {max_p_val}，对应的k值为：{target_ks}")

测试验证 #

• 输入4，输出为max(p(4,k)) = 2，对应的k值为：[2]，和示例一致
• 输入5，输出为max(p(5,k)) = 2，对应的k值为：[2, 3]，和示例一致

内容的提问来源于stack exchange，提问作者user16657590