求生成和为100的5个5的倍数全排列的Python解决方案

核心思路 #

原脚本生成所有5个正整数和为100的排列（约460万种），但我们只需要5的倍数的情况，可通过变量替换大幅缩小计算范围：
设每个数为 5a_i（a_i 是正整数），则 5(a₁+a₂+a₃+a₄+a₅)=100，即转化为找5个正整数和为20的全排列，最后将每个元素乘5即可。这样总结果数仅约2300种，计算量骤减。

方案一：修改递归函数直接生成目标排列 #

直接限制递归中每次取的数为5的倍数，且保证剩余数满足非零5的倍数的要求：

def sum_k_multiples_of_5(n, k):
    if n == 1:
        yield (k,)
    else:
        # 剩余n-1个数每个至少为5，因此当前数最大为k - 5*(n-1)
        max_x = k - 5 * (n - 1)
        # 从5开始，步长为5遍历所有可能的5的倍数
        for x in range(5, max_x + 1, 5):
            for sub_result in sum_k_multiples_of_5(n - 1, k - x):
                yield (x,) + sub_result

# 生成所有结果并验证
result = list(sum_k_multiples_of_5(5, 100))
print(f"总排列数：{len(result)}")
# 打印示例结果
print("示例排列：", result[:5])

方案二：先求正整数排列再转换 #

先生成5个正整数和为20的排列，再将每个元素乘5，逻辑更直观：

def sum_k_positive(n, k):
    if n == 1:
        yield (k,)
    else:
        # 剩余n-1个数每个至少为1，当前数最大为k - (n-1)
        max_x = k - (n - 1)
        for x in range(1, max_x + 1):
            for sub_result in sum_k_positive(n - 1, k - x):
                yield (x,) + sub_result

# 转换为5的倍数的排列
result = [tuple(num * 5 for num in item) for item in sum_k_positive(5, 20)]
print(f"总排列数：{len(result)}")
print("示例排列：", result[:5])

方案三：用迭代工具组合+排列（更高效） #

先找所有5个正整数和为20的无序组合，再生成每个组合的唯一排列，避免重复计算：

from itertools import combinations_with_replacement, permutations

# 筛选所有和为20的5个正整数的无序组合
valid_combinations = []
for combo in combinations_with_replacement(range(1, 17), 5):
    if sum(combo) == 20:
        valid_combinations.append(combo)

# 生成每个组合的唯一排列并转换为5的倍数
result = []
for combo in valid_combinations:
    # 用set去重重复排列（因组合含重复元素）
    unique_perms = set(permutations(combo))
    for perm in unique_perms:
        result.append(tuple(num * 5 for num in perm))

print(f"总排列数：{len(result)}")
print("示例排列：", result[:5])

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