4

我记得以前写过一个 Python 程序来做同样的事情。我记得认为该算法很聪明,但现在尝试在 Clojure 中从内存中实现它我遇到了一些问题。

我对 Clojure 还很陌生,所以我知道我可能没有以最好的方式做到这一点。

下面我使用单词“herps”作为测试,它应该返回该单词所有可能组合的列表。我终于得到了正确的组合,但它们是嵌套的,我想要一个单词的平面列表。我认为这是因为 for 返回一个 lazy seq,但我不知道如何解决它。

(ns combos.core
  (:gen-class))
(use '[clojure.string :only [join]])

(defn rmletter [in letter]
    (join (remove #(= letter %) in)))

(defn combo [total in]
    (if (= (count in) 1)
        (concat total (list in))
        (for [item in] 
            (do
            (if (= (count in) 5) (print "top: "))
            (combo (concat total (list item)) (rmletter in item)))
        )))

(defn -main
  "I don't do a whole lot ... yet."
  [& args]
  ;; work around dangerous default behaviour in Clojure
  (alter-var-root #'*read-eval* (constantly false))
  (doseq [item (combo nil "herps")] (print "item:")(println item))
  (println "Hello, World!"))

这是输出:

top: item:((((h e r p s) (h e r s p)) ((h e p r s) (h e p s r)) ((h e s r p) (h
e s p r))) (((h r e p s) (h r e s p)) ((h r p e s) (h r p s e)) ((h r s e p) (h
r s p e))) (((h p e r s) (h p e s r)) ((h p r e s) (h p r s e)) ((h p s e r) (h
p s r e))) (((h s e r p) (h s e p r)) ((h s r e p) (h s r p e)) ((h s p e r) (h
s p r e))))
top: item:((((e h r p s) (e h r s p)) ((e h p r s) (e h p s r)) ((e h s r p) (e
h s p r))) (((e r h p s) (e r h s p)) ((e r p h s) (e r p s h)) ((e r s h p) (e
r s p h))) (((e p h r s) (e p h s r)) ((e p r h s) (e p r s h)) ((e p s h r) (e
p s r h))) (((e s h r p) (e s h p r)) ((e s r h p) (e s r p h)) ((e s p h r) (e
s p r h))))
top: item:((((r h e p s) (r h e s p)) ((r h p e s) (r h p s e)) ((r h s e p) (r
h s p e))) (((r e h p s) (r e h s p)) ((r e p h s) (r e p s h)) ((r e s h p) (r
e s p h))) (((r p h e s) (r p h s e)) ((r p e h s) (r p e s h)) ((r p s h e) (r
p s e h))) (((r s h e p) (r s h p e)) ((r s e h p) (r s e p h)) ((r s p h e) (r
s p e h))))
top: item:((((p h e r s) (p h e s r)) ((p h r e s) (p h r s e)) ((p h s e r) (p
h s r e))) (((p e h r s) (p e h s r)) ((p e r h s) (p e r s h)) ((p e s h r) (p
e s r h))) (((p r h e s) (p r h s e)) ((p r e h s) (p r e s h)) ((p r s h e) (p
r s e h))) (((p s h e r) (p s h r e)) ((p s e h r) (p s e r h)) ((p s r h e) (p
s r e h))))
top: item:((((s h e r p) (s h e p r)) ((s h r e p) (s h r p e)) ((s h p e r) (s
h p r e))) (((s e h r p) (s e h p r)) ((s e r h p) (s e r p h)) ((s e p h r) (s
e p r h))) (((s r h e p) (s r h p e)) ((s r e h p) (s r e p h)) ((s r p h e) (s
r p e h))) (((s p h e r) (s p h r e)) ((s p e h r) (s p e r h)) ((s p r h e) (s
p r e h))))
Hello, World!
4

3 回答 3

1

我喜欢这些小谜题,不禁打了个高尔夫球:

(定义 perms1 [xs]
  (如果不是(下一个 xs)
    [xs]
    (->> [[] xs]
      (迭代 (fn [[a [x & b]]] ;; xs 的所有拆分的 seq
                 [(co​​nj ax) b]))
      (暂时第二次)
      (mapcat (fn [[a [x & b]]]]
                (map #(cons x %) ;; cons 分割点到其余的每个梳子上
                     (perms1 (concat ab))))))))

注意 perms1 通过在输出序列中生成重复组合来处理输入集合中的重复项。如果我们确定输入中没有重复,我们可以通过使用集合来保存集合中的剩余项目来稍微收紧代码:

(定义 perms2 [xs]
  (如果不是(下一个 xs)
    [xs]
    (地图猫(fn [x]
              (地图缺点
                   (重复 x)
                   (perms2 (disj (set xs) x))))
            xs)))

原始解决方案中的嵌套 seq 是因为您的组合始终返回一个 seq,并且 for 始终返回其主体返回的 seq,因此您最终得到 seqs of seq,嵌套到递归的深度。请注意我的解决方案如何使用 mapcat 而不是 for 来避免这个问题。对 for 的结果调用 (apply concat ...) 是另一种扁平化结果的方法。

于 2013-05-08T06:11:50.447 回答
1

我怀疑您需要在apply concat某个地方输入答案。

正确生成排列的完整答案并不严格,如果满足您的需要,请使用clojure.math.combinatorics 。值得描述一个简短的算法:

(defn perms [v]
  (cond (= 1 (count v)) v                        ; one permutation is it's self 
        (= 2 (count v)) [[(second v) (first v)]  ; two items is [[ab][b a]]
                         [(first v) (second v)]]
        :default
        (apply concat                   
               (for [i (range (count v))]        ; take the first item     
                 (->> (assoc v i (v 0))          ; add it in each position 
                      (#(subvec % 1))            ; find the permutations of 
                      perms                      ; the rest of each of them 
                      (mapv #(conj % (nth v i)))))))) ; then stick the 
                                                 ; one that was assoced back
                                                 ; onto the start of each of them 

有更好的方法来计算这一点,这种简单的递归方法让我觉得是解决问题的一种相当简单的方法。重要的一点是assoc使用 works 的调用,因为它是持久的并且不会破坏其他每个递归分支使用的版本。

hello.exp> (pprint (perms (vec "1234")))                                                                                                                                           
([\4 \3 \2 \1]                                                                                                                                                                     
 [\3 \4 \2 \1]                                                                                                                                                                     
 [\4 \2 \3 \1]                                                                                                                                                                     
 [\2 \4 \3 \1]                                                                                                                                                                     
 [\2 \3 \4 \1]                                                                                                                                                                     
 [\3 \2 \4 \1]                                                                                                                                                                     
 [\4 \3 \1 \2]                                                                                                                                                                     
 [\3 \4 \1 \2]                                                                                                                                                                     
 [\4 \1 \3 \2]                                                                                                                                                                     
 [\1 \4 \3 \2]                                                                                                                                                                     
 [\1 \3 \4 \2]                                                                                                                                                                     
 [\3 \1 \4 \2]                                                                                                                                                                     
 [\4 \1 \2 \3]                                                                                                                                                                     
 [\1 \4 \2 \3]                                                                                                                                                                     
 [\4 \2 \1 \3]                                                                                                                                                                     
 [\2 \4 \1 \3]                                                                                                                                                                     
 [\2 \1 \4 \3]                                                                                                                                                                     
 [\1 \2 \4 \3]                                                                                                                                                                     
 [\1 \3 \2 \4]                                                                                                                                                                     
 [\3 \1 \2 \4]                                                                                                                                                                     
 [\1 \2 \3 \4]                                                                                                                                                                     
 [\2 \1 \3 \4]                                                                                                                                                                     
 [\2 \3 \1 \4]                                                                                                                                                                     
 [\3 \2 \1 \4])                                                                                                                                                                    
nil                                                                                                                                                                                
hello.exp> (count (perms (vec "hello")))  
120

在实践中,使用组合库中的惰性烫发来避免像这个版本那样破坏堆栈。

于 2013-05-07T23:08:21.947 回答
1

这是我的解决方案。

(defn but-nth [s i]
  [(get s i) (into [] (concat (take i s) (take-last (dec (- (count s) i)) s)))])

(defn combs [sofar r]
  (if (empty? r)
    sofar
    (for [[c z] (map (partial but-nth r) (range (count r)))]
      (combs (conj sofar c) z))))

(defn r-combs [s]
  (map (fn [x] (apply str x)) (partition (count s) (flatten (combs [] (vec s))))))

(r-combs "herps")
于 2014-05-08T21:17:32.223 回答