Алгоритм поиска списка заданного точечного продукта и другого списка

Question

Мне нужно написать функцию findL который берет список L₁ целых чисел и искомое произведение n и возвращает список L₂ неотрицательных целых чисел, такой что L₁ · L₂ = n. (Под "точечным произведением" я подразумеваю сумму попарных произведений; например, [1,2] · [3,4] = 1·3+2·4 = 11.)

Так, например, findL(11, [1,2]) может вернуться SOME [3,4], Если нет возможного списка, я вернусь NONE,

Я использую функциональный язык. (Конкретно Standard ML, но точный язык не так важен, я просто пытаюсь придумать алгоритм FP.) То, что я написал до сих пор:

Допустим, у меня есть findL(n, L1):

1. если L1 = [], я возвращаю NONE.
2. если L1 = [x] (список длины 1)
   • если (n >= 0 и x > 0 и n mod x = 0), вернуть SOME [n div x]
   • еще вернуть НЕТ
3. Если длина L1 больше 1, я возвращаюсь к findL (n, L[1:]). Если это возвращает список L2, я возвращаю [1] сцепленный с L2. Если рекурсивный вызов возвращает NONE, я сделал еще один рекурсивный вызов для findL (0, L[1:]) и добавил [n div x] к результату, если он не был NONE. Это работает на многих входах, но не на других.

Мне нужно изменить часть 3, но я не уверен, что у меня есть правильная идея. Буду признателен за любые советы!

Answer 1

Если вы не хотите сказать, что пустые списки во входных данных всегда плохие (даже n = 0 со списком []), я бы рекомендовал возвращать что-то другое для пустого списка в зависимости от того, достигли ли вы 0 в конце (все было вычтено) или нет, затем повторять при получении любого непустого списка, а не в специальном случае списка из одного элемента.

Что касается третьего шага, вам нужно протестировать каждое возможное положительное целое число, кратное первому элементу вашего списка ввода, пока они не превысят n, а не только первый и последний. Первое полученное значение, отличное от None, достаточно хорошее, поэтому вы просто добавляете множитель (не кратный) к списку возврата. Если все дает вам Nones, вы возвращаете None.

---

Я не знаю SML, но вот как я это сделаю в Haskell:

import Data.Maybe (isJust, listToMaybe)

-- Find linear combinations of positive integers
solve :: Integer -> [Integer] -> Maybe [Integer]
-- If we've made it to the end with zero left, good!
solve 0 []     = Just []
-- Otherwise, this way isn't the way to go.
solve _ []     = Nothing
-- If one of the elements of the input list is zero, just multiply that element by one.
solve n (0:xs) = case solve n xs of
                      Nothing -> Nothing
                      Just ys -> Just (1:ys)
solve n (x:xs) =   listToMaybe                    -- take first solution if it exists
                 . map (\ (m, Just ys) -> m:ys)   -- put multiplier at front of list
                 . filter (isJust . snd)          -- remove nonsolutions
                 . zip [1 ..]                     -- tuple in the multiplier
                 . map (\ m -> solve (n - m) xs)  -- use each multiple
                 $ [x, x + x .. n]                -- the multiples of x up to n

Вот это решение 11 с [1, 2] а также 1 с [1, 2],