Scala中如何生成元素和为指定值、单元素不超上限的最短半同构整数Iterable？

问题描述 #

给定目标总和maxSum和单个元素最大允许值maxElementValue，构造一个整数组成的Iterable，满足：

• 所有元素的和恰好等于maxSum
• 每个元素取值不超过maxElementValue
• 元素总个数尽可能少（整体尺寸最小）

输入输出示例 #

输入参数：

val maxSum = 47
val maxElementValue = 10

输出结果：

Iterable(10, 10, 10, 10, 7) // 累加和为47

其他参考示例：

// 示例1：目标和小于单元素最大值
输入：maxSum = 9, maxElementValue = 10
输出：Iterable(9)

// 示例2：目标和无法被单元素最大值整除
输入：maxSum = 11, maxElementValue = 5
输出：Iterable(5, 5, 1)

实现思路 #

要让元素个数最少，核心逻辑是尽可能让每个元素取到允许的最大值，避免拆分大数值导致元素数量增加：

1. 计算maxSum中包含多少个完整的maxElementValue（即整数除法的商quotient）
2. 计算扣除所有完整最大值后剩余的余数remainder
3. 生成quotient个等于maxElementValue的元素，若余数大于0则追加1个余数元素
   这种方式生成的元素总数就是理论最小值，等于ceil(maxSum / maxElementValue)的计算结果。

代码实现 #

def buildMinSizeIterable(maxSum: Int, maxElementValue: Int): Iterable[Int] = {
  // 基础参数校验，规避非法输入
  require(maxSum >= 0, "目标总和不能为负数")
  require(maxElementValue > 0, "单元素最大取值必须为正整数")

  if (maxSum == 0) return Iterable.empty

  val quotient = maxSum / maxElementValue
  val remainder = maxSum % maxElementValue

  val baseElements = Seq.fill(quotient)(maxElementValue)
  if (remainder > 0) baseElements :+ remainder else baseElements
}

效果验证 #

直接调用方法跑示例即可得到符合要求的结果：

// 测试第一个示例
buildMinSizeIterable(47, 10) // 输出：List(10, 10, 10, 10, 7)

// 测试第二个示例
buildMinSizeIterable(9, 10) // 输出：List(9)

// 测试第三个示例
buildMinSizeIterable(11, 5) // 输出：List(5, 5, 1)

内容的提问来源于stack exchange，提问作者Ramón J Romero y Vigil