正整数划分算法详解：Python 实现允许和不允许重复元素的划分

正整数划分算法详解：Python 实现允许和不允许重复元素的划分

正整数划分是指将一个正整数 n 表示成一系列正整数之和：n=n1+n2+…+nk，其中 n1≥n2≥…≥nk≥1，k≥1。根据是否允许重复元素，正整数划分可以分为两种类型：

1. 允许包含相同元素的划分：例如，正整数 6 可以划分为 6、5+1、4+2、4+1+1 等。
2. 不允许包含相同元素的划分：例如，正整数 6 可以划分为 6、5+1、4+2、3+2+1 等。

递归实现正整数划分

可以使用递归的方法来求解正整数 n 的划分。具体步骤如下：

1. 定义一个函数 partition，接收两个参数：n 表示待拆分的正整数，target 表示当前拆分的目标值。
2. 在函数内部，首先判断如果 n 等于 0，说明已经完成了一种划分，打印出当前的划分情况，然后返回。
3. 然后使用一个 for 循环，从 1 到 target 进行遍历，表示当前拆分的元素的取值。
4. 在循环内部，调用 partition 函数递归拆分剩余的部分，传入参数 n-i 和 i，其中 n-i 表示剩余部分的值，i 表示当前拆分的元素。
5. 注意，为了避免重复的划分，我们限制当前拆分的元素不能大于等于上一个拆分的元素。

Python 代码实现

def partition(n, target):
    if n == 0:
        print(target)
        return
    for i in range(1, target + 1):
        if i <= target:
            partition(n - i, i)

def main(n):
    print('允许包含相同元素的划分情况：')
    partition(n, n)

    print('不允许包含相同元素的划分情况：')
    for i in range(1, n + 1):
        partition(n - i, i)

n = int(input('请输入一个正整数：'))
main(n)

示例输出

请输入一个正整数：6
允许包含相同元素的划分情况：
6
5 1
4 2
4 1 1
3 3
3 2 1
3 1 1 1
2 2 2
2 2 1 1
2 1 1 1 1
1 1 1 1 1 1
不允许包含相同元素的划分情况：
6
5 1
4 2
3 3

代码解读

• partition(n, target) 函数实现递归划分逻辑，通过不断减少 n 的值并调用自身来寻找所有可能的划分方案。
• main(n) 函数用于接收用户输入的正整数 n，并分别调用 partition 函数来计算允许和不允许重复元素的划分情况。
• 在不允许重复元素的划分中，for 循环的迭代范围从 1 到 n，并且在递归调用 partition 函数时，target 参数被设置为 i，即当前拆分的元素。这确保了每次递归调用时，拆分的元素都小于剩余部分的值，从而避免了重复元素的出现。

总结

本文详细介绍了正整数划分算法的原理和 Python 代码实现，并通过示例输出展示了两种划分方式的结果。通过对代码的理解和分析，读者可以深入掌握正整数划分的算法逻辑，并将其应用于实际问题中。