Генерация целочисленных разделов - Преобразование кода Python с выходом в clojure

Question

Я пытаюсь сгенерировать целочисленные разделы для числа и наткнулся на это , которое выглядело довольно кратким и элегантным:

def partitions(n):
    # base case of recursion: zero is the sum of the empty list
    if n == 0:
        yield []
        return

    # modify partitions of n-1 to form partitions of n
    for p in partitions(n-1):
        yield [1] + p
        if p and (len(p) < 2 or p[1] > p[0]):
            yield [p[0] + 1] + p[1:]

Итак, я попытался преобразовать это в Clojure ис треском провалился:

(defn- partitions [n]
  (if (zero? n) []
      (for [p (partitions (dec n))]
        (let [res [(concat [1] p)]]
          (if (and (not (empty? p))
                   (or (< (count p) 2) (> (second p) (first p))))
            (conj res (into [(inc (first p))] (subvec p 1)))
            res)))))

^^ Выше неверно.Например:

eul=> (partitions 4)
()

Должен ли я думать о ленивых последовательностях?

У меня проблемы с рассуждениями о коде Python, и мои попытки его преобразования пока не увенчались успехом.Любая помощь в выяснении, как это сделать, приветствуется.

Answer 1

Поскольку активный конец раздела находится спереди, он должен быть списком, а не вектором.Это упрощает концы вашего кода.

В противном случае, придерживаясь вашей структуры, мы получаем, в Clojure, что-то вроде ...

(defn partitions [n]
  (if (zero? n)
    '(())
    (apply concat
      (for [p (partitions (dec n))]
        (let [res [(cons 1 p)]]
          (if (and (not (empty? p))
                   (or (< (count p) 2) (> (second p) (first p))))
            (conj res (cons (inc (first p)) (rest p)))
            res))))))

Это работает:

=> (partitions 4)
((1 1 1 1) (1 1 2) (2 2) (1 3) (4))

---

Где выпойти не так?Вы не смогли правильно распутать yield s.

• for возвращает последовательность векторов одного или двух разделов.Вы должны объединить их в одну последовательность.
• И ваш базовый случай также должен возвращать последовательность разделов, а не один пустой раздел, как вы пытаетесь это сделать.Алгоритм воспринимает его как пустую последовательность, которая распространяется по цепочке рекурсии.Отсюда и ваш результат.

Необходимо внести некоторые незначительные улучшения, но я отказался от них в пользу того, чтобы придерживаться вашего кода.

Answer 2

В библиотеке Tupelo реализована функция Python yield.Вот перевод:

(ns tst.demo.core
  (:use tupelo.core )

(defn partitions [n]
  (lazy-gen
    (if (zero? n)
      (yield [])
      (doseq [p (partitions (dec n))]
        (yield (glue [1] p))
        (when (and (not-empty? p)
                (or (< (count p) 2)
                  (< (first p) (second p))))
          (yield (prepend (inc (first p))
                   (rest p))))))))

(partitions 4) => 
    ([1 1 1 1] [1 1 2] [2 2] [1 3] [4])