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

Question

我知道使用Clojure解决排列问题的方法有很多种。我尝试了使用Core.Logic创建DCG（确定性子句语法），但是库中的DCG部分太过实验性，没有奏效。

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

第二种方法使用MapCat将cons/first应用到每个递归调用permutation的返回值上。Remove item确保我不会在每个位置上重复使用相同的字母。

请问有人能解释一下列表推导式方法和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 子问题

- slimbo

---

@amalloy - 我的问题不是关于如何在Clojure中解决排列问题。除了stackoverflow的回答外，还有许多在线样本排列代码。我的问题是关于我尝试的实现为什么不起作用 - 我错过了什么更深层次的概念。这里有很多人提出了半熟的问题 - 这是一个真正尝试理解Clojure工作原理和一个真正的问题。 - slimbo

@stevemacn，你可以用更具体的标题再次提出问题，比如“我的Clojure排列实现有什么问题？” - Diego Basch

@stevemacn (partial cons x) 相当于 #(cons x %) 或 (fn [coll] (cons x coll))。它将 x 添加到其顺序参数中，map 通过s中其他所有内容的 perm 运行。封闭的 mapcat 连接将此过程应用于将s的每个元素视为序列的结果。因此，该函数接受一个set参数，但返回一个sequences序列。你应该知道 - 你基本上写了它 :)。 - Thumbnail

@stevemacn，你对(partial cons x)的理解是正确的；而(disj s x)则是将元素x从集合s中移除。顺便说一下，从你的代码中我可以感受到Haskell可以将非空集合解构为任意成员x和剩余的集合xs。在Clojure中尝试这样做，xs将会是一个序列，而不是一个集合。你可以在ClojureDocs或Grimoire上查找标准函数，如partial或conj。最后，如果你想继续讨论，请遵循@amalloy的建议，在其他地方重新开启一个修订后的问题。 - Thumbnail

@slimbo 如果这个问题已经在评论中得到了回答，最好写一个真正的“答案”。 - Jon Surrell

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)。这就是造成异常的原因。
• 给定xs中的一个x，以及假设没有x的xs的排列y，那么给定x的排列就是(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) 更快。
• remove-item 中的 remove 扫描整个序列。我们很难对此进行修复。

---

如果我们知道处理的是不同的事物，则将它们视为集合会更简单、更快：

(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))

- Thumbnail

Answer 2

我们可以通过使用原始序列中项目的索引来添加重复项的支持。函数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推导式。

- Ian Davies