Развернуть вложенность в рекурсивной карте в clojure
У меня возникли проблемы с развертыванием вложенной структуры результатов этой функции. Я думаю, что он выполняет обход правильно, но результаты глубоко вложены.
Функция пытается пройти по списку и найти все возможные пути в списке, где числовое расстояние между соседними элементами равно 1, 2 или 3. Например, чтобы перейти от первого элемента 1, только к следующему элементу 4 шаг 3 будет работать. Но для следующего шага мы можем либо взять 1 от 4 до 5, либо два от 4 до 6 (пропустив 5), либо три от 4 до 7 (пропустив 5 и 6).
Мой вопрос состоит из двух частей: 1) что я могу сделать, чтобы предотвратить глубокую вложенность? и 2) есть ли другой способ структурировать код, чтобы предотвратить глубокую вложенность в первую очередь?
(def l0 (1 4 5 6 7 10 11 12 15 16 19 22))
(defn next-path-with-step [chain step]
(let [looking-at (first chain)
next-path (drop-while (fn [a]
(not (= (- a looking-at) step)))
chain)]
(if (empty? next-path)
nil
next-path)))
(defn find-chains [chains prefix]
(if (empty? chains)
prefix
(map (fn [chain]
(let [head (first chain)
next-paths (filter #(not (nil? %))
(map (partial next-path-with-step chain) [1 2 3]))]
(find-chains next-paths (conj prefix head))))
chains)))
Чтобы запустить его:
(find-chains [l0] [])
Я получаю следующие результаты:
(((((((((((([1 4 5 6 7 10 11 12 15 16 19 22]))))) (((([1 4 5 6 7 10 12 15 16 19 22]))))))) ((((((([1 4 5 7 10 11 12 15 16 19 22]))))) (((([1 4 5 7 10 12 15 16 19 22]))))))) (((((((([1 4 6 7 10 11 12 15 16 19 22]))))) (((([1 4 6 7 10 12 15 16 19 22]))))))) ((((((([1 4 7 10 11 12 15 16 19 22]))))) (((([1 4 7 10 12 15 16 19 22])))))))))
Я пытаюсь получить внутренние последовательности в виде списка. Что-то вроде:
([1 4 5 6 7 10 11 12 15 16 19 22]
[1 4 5 6 7 10 12 15 16 19 22]
[1 4 5 7 10 11 12 15 16 19 22]
[1 4 5 7 10 12 15 16 19 22]
[1 4 6 7 10 11 12 15 16 19 22]
[1 4 6 7 10 12 15 16 19 22]
[1 4 7 10 11 12 15 16 19 22]
[1 4 7 10 12 15 16 19 22])
@amalloy, ты прав! Он недостаточно эффективен для решения проблемы (истощает кучу). Я начал этот путь с приведенного короткого примера, чтобы посмотреть, смогу ли я получить те же результаты, что и они, поскольку я знал, что у меня возникнут проблемы с рекурсией и построением списка. Я боролся с вложенными списками, хотел знать, где был мой пробел.
![Учебная записка [Medium] Leetcode#22 Generate Parentheses](https://i.imgur.com/Hl2feR7b.png)
Ответы 1
вот небольшие изменения, которые решат эту проблему за вас:
(defn find-chains [chains prefix]
(if (empty? chains)
[prefix] ;; return chain wrapped in a vector to avoid flattening
;; use mapcat instead of map to flatten internal find-chains calls
(mapcat (fn [chain]
(let [head (first chain)
next-paths (filter #(not (nil? %))
(map (partial next-path-with-step chain) [1 2 3]))]
(find-chains next-paths (conj prefix head))))
chains)))
user> (find-chains [l0] [])
;;=> ([1 4 5 6 7 10 11 12 15 16 19 22]
;; [1 4 5 6 7 10 12 15 16 19 22]
;; [1 4 5 7 10 11 12 15 16 19 22]
;; [1 4 5 7 10 12 15 16 19 22]
;; [1 4 6 7 10 11 12 15 16 19 22]
;; [1 4 6 7 10 12 15 16 19 22]
;; [1 4 7 10 11 12 15 16 19 22]
;; [1 4 7 10 12 15 16 19 22])
фу! Такое простое изменение. Я немного смущен, что не мог этого видеть!
leetwinski дал вам хорошее решение проблемы, как указано, но я должен сказать, что был бы удивлен, если бы этот алгоритм был достаточно эффективным, чтобы вовремя решить проблему появления кода, над которой вы работаете - это быстрее, чем перебор 2 ^ 100 возможных решений, но все же нужно посмотреть каждое реальное решение один раз. Решением для моего ввода было 14-значное число, слишком много, чтобы производить их все по одному.