Как создать ленивую последовательность в clojure с использованием не-хвостовой рекурсии?

Question

Take проблема целое раздел, например, я могу написать следующий код, чтобы вывести все возможные разбиения положительного целого n:

(defn foo 
    ([n] (foo n n [])) 
    ([n k buf] 
    (if (zero? n) 
     (println buf) 
     (doseq [i (range 1 (inc (min n k)))] 
     (foo (- n i) i (conj buf i)))))) 

Затем (foo 5) выходы:

[1 1 1 1 1] 
[2 1 1 1] 
[2 2 1] 
[3 1 1] 
[3 2] 
[4 1] 
[5] 

Вопрос в том, как я мог написать функция bar, которая генерирует ленивый seq, содержащий такие результаты? Например, я хочу, чтобы (bar 5) генерировал ([1 1 1 1 1] [2 1 1 1] [2 2 1] [3 1 1] [3 2] [4 1] [5]).

Answer 1

Вот примерно эквивалентна функции генерации разделов в виде последовательности последовательностей:

(defn bar 
    ([n] (bar n n)) 
    ([n k] 
    (if (zero? n) 
    [[]] 
    (for [i (range 1 (inc (min n k))), tail (bar (- n i) i)] 
     (cons i tail))))) 

Например,

(bar 5) 
; ((1 1 1 1 1) (2 1 1 1) (2 2 1) (3 1 1) (3 2) (4 1) (5)) 

Как ленивый bar?

• for ленив.
• , чтобы сделать его более ленивым, оберните тело в lazy-seq.

---

У меня есть сомнения по поводу выше.

• Функция пересчитывается на глубину n.
• Обертывание тела в lazy-seq Я подозреваю, что просто кладет вверх по ленивым последовательностям, создавая так же глубокий рекурсивный стек вызовов при доступе к первому элементу .

Кроме того, повторно используются те же самые tail s; тем более, что (bar n k) одинаково для всех k >= n.

Если производительность этой функции является особой проблемой, существуют итеративные алгоритмы с постоянным временем на шаг. Как следует из комментария @ CharlesDuffy, они могут быть повторно отстроены, чтобы создать ленивые последовательности.

---

Зачем смотреть в хрустальный шар, когда вы можете прочитать книгу?

Стандартное пространство имен clojure.math.combinatorics, размещено here, содержит функцию partition, которая создает ленивую последовательность разделов любой последовательности объектов - быстро. Целочисленный раздел - это где мы подсчитываем элементы каждого раздела одинаковых объектов. Они выходят в обратном лексикографическом порядке.

Например

(map #(map count %) (combo/partitions (repeat 5 :whatever))) 
;((5) (4 1) (3 2) (3 1 1) (2 2 1) (2 1 1 1) (1 1 1 1 1)) 

Без сомнения, код может быть урезанным иметь дело только с этим случаем.

Answer 2

Рекурсивное решение. Есть несколько способов оптимизации, и код не самый лучший.

(defn partitions [n] 
    (loop [m n 
     res [(init-step n m)]] 
    (let [l (last res)] 
     (if (= m 1) 
     res 
     (if (last-step? (last res)) 
      (recur (- m 1) (vec (conj res (init-step n (- m 1))))) 
      (recur m (next-step res))))))) 


(defn init-step [n m] 
    (if (= n m) 
    [n] 
    (loop [res [m (- n m)]] 
     (let [l (last res) 
      f (first res)] 
     (if (<= l f) 
      res 
      (recur (vec (conj (vec (butlast res)) f (- l f))))))))) 

(defn next-step [res] 
    (let [input-vec (last res) 
     cnt (count input-vec) 
     i (.indexOf input-vec 1) 
     j (if (> i -1) (- i 1) (- cnt 1)) 
     m (- cnt j) 
     new-vec (conj (vec (take j input-vec)) (- (input-vec j) 1))] 
    (conj res (vec (concat new-vec (repeat m 1)))))) 


(defn last-step? [input-vec] 
    (if 
    (or (nil? input-vec) 
     (= (count input-vec) 1) 
     (= (input-vec 1) 1)) true 
    false)) 

(partitions 10) 
#=> [[10] [9 1] [8 2] [8 1 1] [7 3] [7 2 1] [7 1 1 1] [6 4] [6 3 1] [6 2 1 1] [6 1 1 1 1] [5 5] [5 4 1] [5 3 1 1] [5 2 1 1 1] [5 1 1 1 1 1] [4 4 2] [4 4 1 1] [4 3 1 1 1] [4 2 1 1 1 1] [4 1 1 1 1 1 1] [3 3 3 1] [3 3 2 1 1] [3 3 1 1 1 1] [3 2 1 1 1 1 1] [3 1 1 1 1 1 1 1] [2 2 2 2 2] [2 2 2 2 1 1] [2 2 2 1 1 1 1] [2 2 1 1 1 1 1 1] [2 1 1 1 1 1 1 1 1] [1 1 1 1 1 1 1 1 1 1]]