求解和生成由给定集合 (Haskell) 索引的变量的方程式

Question

我想在Haskell中解决以下问题：

设n为自然数，A = [d_1 , ..., d_r]为一组正数。

我想找出下列方程的所有正解：

n = Sum d_i^2 x_i.

例如如果n= 12和集合A= [1,2,3]。我想用自然数求解以下方程：

x+4y+9z=12.

用下面的代码就够了:

[(x,y,z) | x<-[0..12], y<-[0..12], z<-[0..12], x+4*y+9*z==12]

我的问题是如果 n 不固定并且集合 A 也不固定。我不知道如何"produce"一定数量的变量被集合A索引。

Answer 1

一些提示：

最终你想用这个签名写一个函数：

solutions :: Int -> [Int] -> [ [Int] ]

示例：

solutions 4 [1,2]  == [ [4,0], [0,1] ]
  -- two solutions: 4 = 4*1^2 + 0*2^2,  4 = 0*1^2 + 1*2^2

solutions 22 [2,3]  == [ [1,2] ]
  -- just one solution: 22 = 1*2^2 + 2*3^2

solutions 10 [2,3]  == [ ]
  -- no solutions

第2步. 根据列表的结构递归定义solutions:

solutions x [a] = ...
  -- This will either be [] or a single element list

solutions x (a:as) = ...
  -- Hint: you will use `solutions ... as` here

Answer 2

您可以使用带有 do-notation 的递归调用来代替列表理解。

这有点棘手，因为您必须正确处理边缘情况，我允许自己进行一些优化：

solve :: Integer -> [Integer] -> [[Integer]]
solve 0 ds = [replicate (length ds) 0]
solve _ [] = []
solve n (d:ds) = do
  let maxN = floor $ fromIntegral n / fromIntegral (d^2)
  x <- [0..maxN]
  xs <- solve (n - x * d^2) ds
  return (x:xs)

它是这样工作的：

它正在跟踪第一个参数中的剩余金额
当这个总和是 0 显然已经完成并且只需要 return 0（第一种情况）时 - 它会 return 一个长度相同的 0 列表ds
如果剩余的金额不是 0 但没有 d 的剩余，我们就有麻烦了，因为没有解决方案（第二种情况） - 请注意，没有解决方案只是空的名单
在所有其他情况下，我们有一个非零 n（剩余总和）和一些 ds 剩余（第三种情况）：
- 现在寻找您可以为 x (maxN) 选择的最大数量，记住 x * d^2 应该是 <= n 所以上限是 n / d^2 但我们只对整数感兴趣（所以它是 floor）
- 尝试从 x 从 0 到 maxN
- 在将此 x 与剩余的 ds 一起使用时寻找剩余总和的所有解决方案，然后选择其中一个 xs
- 结合x和xs给出当前子问题的解

list-monad 的绑定将为您处理剩下的事情 ;)

例子

λ> solve 12 [1,2,3]
[[0,3,0],[3,0,1],[4,2,0],[8,1,0],[12,0,0]]

λ> solve 37 [2,3,4,6]
[[3,1,1,0],[7,1,0,0]]

备注

这在处理负数时会失败 - 如果你需要这些，你将不得不引入更多的案例 - 我相信你会弄清楚它们（在这一点上它比 Haskell 更数学）

求解和生成由给定集合 (Haskell) 索引的变量的方程式

Solving and producing and equation with variables indexed by a given set (Haskell)

variables

indexing

haskell

linear-equation

例子

备注