2

我知道有多种方法可以使用 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 子问题

4

2 回答 2

4

我们可以将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)。这就是导致异常的原因。
  • 给定xfrom的排列，xs并且，鉴于此，without的排列y是just 。xsx(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)。
  • removein扫描整个remove-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))
于 2015-08-09T21:45:03.013 回答
0

我们可以通过使用原始序列中项目的索引来添加对重复项的支持。函数 append-index 返回一个新序列，其中索引和值现在位于向量中。例如'(\a \b \c) -> '([0 \a] [1 \b] [2 \c] [3 \a])。

然后，您在 for 循环中使用此序列，当我们想要从原始项目中删除它时获取项目的索引，并在我们将其转换为尾部序列时获取值。

(defn remove-nth [coll n]
  (into (drop (inc n) coll) (reverse (take n coll))))

(defn append-index [coll]
  (map-indexed #(conj [%1] %2) coll))

(defn permutation [xs]
  (let [i-xs (append-index xs)]
  (if (= (count xs) 1)
    (list xs)
    (for [x i-xs
          y (permutation (remove-nth xs (first x)))]
      (cons (last x) y)))))

感谢上一篇文章，我自己也在为排列问题苦苦挣扎，并没有考虑使用 for 理解。

于 2017-09-09T15:01:10.670 回答