代码之家 › 专栏 › 技术社区 › nakiya

生成整数分区-将python代码转换为clojure

clojure

nakiya · 技术社区 · 6 年前

我正在尝试为一个数字生成整数分区,但偶然发现 this 它看起来很简洁和优雅:

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代码,我很难进行推理,到目前为止,我对它的转换尝试都失败了。如果有什么能帮我解决这个问题,我将不胜感激。

2 回复 | 直到 6 年前

Alan Thompson 6 年前

Tupelo库实现了 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])

Thumbnail 6 年前

因为分区的活动端在前面,所以它最好是一个列表,而不是一个向量。这简化了代码的手指端。

否则,坚持你的结构,我们得到,在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 正确。

这个 for 返回一个或两个分区的向量序列。你必须将它们连接成一个序列。
基本情况也应该返回一系列分区-而不是一个空分区。算法将其作为一个空序列,它向递归链上传播自己。所以你的结果。

还有一些小的改进要做,但是我放弃了它们,转而更接近您的代码。

推荐文章

Freid001 · 具有最小和最大限制的架构?

6 年前

R u c k s a c k · 如何创建一个集合列表,其中没有两首连续的歌曲在同一个键中

6 年前

Evgeniy Berezovsky · lein uberjar导致“方法代码太大!”

6 年前

phlie · Hoplon With Castra加载后端时出错

6 年前

David Furnam · Clojure从数组中获取坐标

6 年前

podomunro · 如何在Clojure中按给定日期过滤JSON数据?

6 年前

Jdv · 将贴图M转换为贴图A数组,其中M中的键和值映射到A中元素中的新键

6 年前

Akisame · ClojureScript-外部文件中未定义名称goog

6 年前

Jeroen · 如何将惰性序列转换为映射?

6 年前

bpereira · 使用交换!而不是重置!在atom-clojure中

6 年前