CODEWITHSUNDEEP
variableshaskellindexinglinear-equation
Miguel
Miguel

Reputation: 103

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

I want to solve the following problem in Haskell:

Let n be a natural number and let A = [d_1 , ..., d_r] be a set of positive numbers.

I want to find all the positive solutions of the following equation:

n = Sum d_i^2 x_i.

For example if n= 12 and the set A= [1,2,3]. I would like to solve the following equation over the natural numbers:

x+4y+9z=12.

It's enough to use the following code:

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

My problem is if n is not fixed and also the set A are not fixed. I don't know how to "produce" a certain amount of variables indexed by the set A.

Upvotes: 0

Views: 308

Answers (2)

Random Dev
Random Dev

Reputation: 52290

Instead of a list-comprehension you can use a recursive call with do-notation for the list-monad.

It's a bit more tricky as you have to handle the edge-cases correctly and I allowed myself to optimize a bit:

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)

it works like this:

  • It's keeping track of the remaining sum in the first argument
  • when there this sum is 0 where are obviously done and only have to return 0's (first case) - it will return a list of 0s with the same length as the ds
  • if the remaining sum is not 0 but there are no d's left we are in trouble as there are no solutions (second case) - note that no solutions is just the empty list
  • in every other case we have a non-zero n (remaining sum) and some ds left (third case):
    • now look for the maximum number that you can pick for x (maxN) remember that x * d^2 should be <= n so the upper limit is n / d^2 but we are only interested in integers (so it's floor)
    • try all from x from 0 to maxN
    • look for all solutions of the remaining sum when using this x with the remaining ds and pick one of those xs
    • combine x with xs to give a solution to the current subproblem

The list-monad's bind will handle the rest for you ;)

examples

λ> 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]]

remark

this will fail when dealing with negative numbers - if you need those you gonna have to introduce some more cases - I'm sure you figure them out (it's really more math than Haskell at this point)

Upvotes: 3

ErikR
ErikR

Reputation: 52049

Some hints:

Ultimately you want to write a function with this signature:

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

Examples:

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

Step 2. Define solutions recursively based on the structure of the list:

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

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

Upvotes: 1

Related Questions