Бонус задача No. 2

[svilenbs]

Реализирайте функция:

generate :: (Eq a, Enum a, Num a) => a -> a -> [[a]]
generate n m = ...

която по зададени n и m, намира всички целочислени, неотрицателни решения на уравнението

x1 + x2 + ... xn = m

Примерен вход и изход

Main> generate 3 2 == [[0,0,2],[0,1,1],[0,2,0],[1,0,1],[1,1,0],[2,0,0]] 
True

Уточнения по задачата.

1. Не се признават решения, които имат повече от 80 символа на ред.
2. Признава се първото коректно решение на задачата.
3. Признава се всяко следващо решение, което е по-кратко от предходното (по брой символи като не броим имената на променливите :) ) или поправя грешка от предходното. За тази цел пишете коментари ако има проблем от предходното решение.
4. Ако сте съгласни с решение на задача, можете да му дадете палец нагоре.
5. Не се признават решения с коментар, които са били модифицирани.

Срок за решения: 8ми ноември 2020г.

[dimitroffangel]

generateSolutions result arr length left index 
  | index == length - 1 = [(changeIthElement arr index left)]
  | left == 0 = [arr]
  | otherwise = 
        let ithElement = arr !! index
        in  result ++
            (concat [ 
                        generateSolutions [] (changeIthElement arr index x) length (left - x) (index + 1) 
                        | x  <- [ithElement .. left]
                    ]
            )

changeIthElement arr index withValue = 
    (take index arr) ++ [withValue] ++ (drop (index + 1) arr)


generate 0 m = []
generate n m = generateSolutions [] [0 | x <- [1.. n]] n m 0

[spiderjako]

Опитвах се цял ден без монади, щеше ми се по колкото се може по-кратък начин с list comprehension, но не ми се получи, поздравления на Ангел!

П.п. намерих replicateM някъде из форумите, счетох, че все пак може и това решение да е полезно някому

import Control.Monad

generate n m = 
    [ x | x <- (replicateM n [0..m]), sum x == m ]

[ichko]

@dimitroffangel една идея прекалено императивно ми идва решението с тези индексирания, иначе е супер.

[ichko]

@spiderjako по-кратно от това решение едва ли ще се намери 😄. Иначе ще е бавничко, с тази филтация над всички комбинации 😄.

[googleson78]

Ето по-кратко :Р

generate n m = 
    filter ((==m) . sum) $ sequence $ replicate n [0..m]

(нужно ти е само Applicative инстанцията, не ти трябва Monad - ако ползваш sequenceA, т.е. replicateA n mx = sequenceA $ replicate n mx)

[ichko]

Ето и мое решение, мисля че бие по скорост 😄

generate 1 m = [[m]]
generate n m = [nth : r | nth <- [0..m], r <- generate (n - 1) (m - nth)]