给定 n(比如 3 个人)和 s(比如 100$),我们想在 n 个人中划分 s。
所以我们需要总和为 s 的所有可能的 n 元组
我的 Scala 代码如下:
def weights(n:Int,s:Int):List[List[Int]] = {
List.concat( (0 to s).toList.map(List.fill(n)(_)).flatten, (0 to s).toList).
combinations(n).filter(_.sum==s).map(_.permutations.toList).toList.flatten
}
println(weights(3,100))
这适用于 n 的小值。(n=1、2、3 或 4)。
超过 n=4,需要很长时间,实际上无法使用。
我正在寻找使用惰性评估/ Stream 来修改我的代码的方法。
我的要求:必须为 n 最多 10 工作。
警告:问题变得非常大非常快。我从 Matlab 得到的结果——
---For s =100, n = 1 thru 5 results are ---
n=1 :1 combinations
n=2 :101 combinations
n=3 :5151 combinations
n=4 :176851 combinations
n=5: 4598126 combinations
---