我的 Clojure 排列实现有什么问题

Question

我知道使用 Clojure 解决排列的方法有多种。我尝试使用 Core.Logic 创建 DCG（定子句语法），但该库的 DCG 部分太实验性，无法工作。

在下面的代码中我尝试了两种不同的方法。一种是列表理解（已注释掉），这与我在 Haskell 中解决此问题的方式类似。

第二种方法使用 MapCat 将 cons/first 应用于递归调用排列的每个返回值。删除项目可确保我不会在每个位置多次使用相同的字母。

有人可以解释一下列表理解方法有什么问题以及 MapCat 方法有什么问题吗？在 Haskell 中推理此类问题要容易得多 - 我是否缺少一些关于 Clojure 的观点？

(defn remove-item [xs]
   (remove #{(first xs)} xs )
)

(defn permutation [xs]

  (if (= (count xs) 1)
      xs

     ;(for [x xs y (permutation (remove-item xs))
     ;          :let [z (map concat y)]]
     ;          z)                    

     (mapcat #(map cons first (permutation (remove-item %)) ) xs)

  )
)

编辑：@thumbnail 已经解决了评论中的 MapCat 子问题

Answer 1

我们可以将permutation函数简化为

(defn permutation [xs]
  (if (= (count xs) 1)
    xs
    (for [x xs
          y (permutation (remove-item xs))]
      (map concat y))))

尝试在任何复数上使用它都会产生java.lang.IllegalArgumentException: Don't know how to create ISeq from: ...您想要排列的任何内容。

有两个错误：

• permutation应该返回一系列序列，即使只有其中一个；xs应该如此(list xs)。这就是导致异常的原因。
• x给定from and的排列，鉴于此， without的xs排列就是。yxsx(cons x y)

修正这些后，我们有

(defn permutation [xs]
  (if (= (count xs) 1)
    (list xs)
    (for [x xs
          y (permutation (remove-item x xs))]
     (cons x y))))

例如，

(permutation (range 3))
;((0 1 2) (0 2 1) (1 0 2) (1 2 0) (2 0 1) (2 1 0))

仅当所有排列的事物都不同时，上述方法才有效。在另一个极端...

(permutation [1 1 1])
;()

还，

• count扫描整个序列。找出是否只有一个元素(seq (rest xs))比 更快(= (count xs) 1)。
• 并且removeinremove-item扫描整个序列。我们对此无能为力。

如果我们知道我们正在处理不同的事物，那么将它们作为一个集合来处理会更简单、更快：

(defn perm-set [xs]
  (case (count xs)
    0 '()
    1 (list (seq xs))
    (for [x xs, y (perm-set (disj xs x))]
      (cons x y)))

• 它也适用于空集。
• count是瞬时的并且disj几乎是恒定的时间，所以这更快。

因此：

(perm-set (set '()))
;()

(perm-set (set (range 3)))
;((0 1 2) (0 2 1) (1 0 2) (1 2 0) (2 0 1) (2 1 0))