Is there a better way to implement this algorithm to return a list of all combinations of alphabetic word order?

Question

I remember in the past I wrote a Python program that did the same thing. I remember how the algorithm was considered smart, but now it is trying to implement it from memory in Clojure. I am having some problems.

I'm new to Clojure, so I know that I'm probably not doing it in the best way.

Below I use the word "herps" as a test, and it should return a list of all possible combinations of the word. I finally get the combinations correctly, but they are nested, and I need a flat list of words. I think, because to return lazy seq , but I'm not sure how to get around it.

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

And here is the conclusion:

 top: item:((((herps) (hersp)) ((heprs) (hepsr)) ((hesrp) (h espr))) (((hreps) (hresp)) ((hrpes) (hrpse)) ((hrsep) (h rspe))) (((hpers) (hpesr)) ((hpres) (hprse)) ((hpser) (h psre))) (((hserp) (hsepr)) ((hsrep) (hsrpe)) ((hsper) (h spre)))) top: item:((((ehrps) (ehrsp)) ((ehprs) (ehpsr)) ((ehsrp) (e hspr))) (((erhps) (erhsp)) ((erphs) (erpsh)) ((ershp) (e rsph))) (((ephrs) (ephsr)) ((eprhs) (eprsh)) ((epshr) (e psrh))) (((eshrp) (eshpr)) ((esrhp) (esrph)) ((esphr) (e sprh)))) top: item:((((rheps) (rhesp)) ((rhpes) (rhpse)) ((rhsep) (r hspe))) (((rehps) (rehsp)) ((rephs) (repsh)) ((reshp) (r esph))) (((rphes) (rphse)) ((rpehs) (rpesh)) ((rpshe) (r pseh))) (((rshep) (rshpe)) ((rsehp) (rseph)) ((rsphe) (r speh)))) top: item:((((phers) (phesr)) ((phres) (phrse)) ((phser) (p hsre))) (((pehrs) (pehsr)) ((perhs) (persh)) ((peshr) (p esrh))) (((prhes) (prhse)) ((prehs) (presh)) ((prshe) (p rseh))) (((psher) (pshre)) ((psehr) (pserh)) ((psrhe) (p sreh)))) top: item:((((sherp) (shepr)) ((shrep) (shrpe)) ((shper) (s hpre))) (((sehrp) (sehpr)) ((serhp) (serph)) ((sephr) (s eprh))) (((srhep) (srhpe)) ((srehp) (sreph)) ((srphe) (s rpeh))) (((spher) (sphre)) ((spehr) (sperh)) ((sprhe) (s preh)))) Hello, World! 

Answer 1

I suspect you need to find apply concat in your answer somewhere.

The full answer to creating permutations properly is not easy, use clojure.math.combinatorics if it suits your needs. It is worth describing a short algorithm:

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

There are much better ways to do this, this simple recursive method just amazes me as a pretty clojure way to solve the problem. One of the important points is calling assoc with the jobs, because it is persistent and does not crash the version used by each of the other recursive branches.

 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 

In practice, use the lazy permanent form of the combinatorics library to avoid flushing the stack, as this version will do.

Answer 2

I like these little puzzles and I can't help but play golf:

  (defn perms1 [xs]
   (if-not (next xs)
     [xs]
     (- >> [[] xs]
       (iterate (fn [[a [x & b]]] ;; seq of all splits of xs
                  [(conj ax) b]))
       (take-while second)
       (mapcat (fn [[a [x & b]]]
                 (map # (cons x%) ;; cons split point onto each comb of the rest
                      (perms1 (concat ab)))))))) 

Note. perms1 processes repeating elements in an input collection, creating repeating combinations in the output sequence. If we are sure that there are no duplicates in the input, we can tighten the code a bit using the set to store the remaining elements in the collection:

  (defn perms2 [xs]
   (if-not (next xs)
     [xs]
     (mapcat (fn [x]
               (map cons
                    (repeat x)
                    (perms2 (disj (set xs) x))))
             xs))) 

Nested seqs in your original solution are related to the fact that your combo always returns seq and always returns seq of what its body returns, so you end up in seqs seqs nested in the depth of your recursion. Notice how my solutions use mapcat instead of avoiding this problem. Calling (apply concat ...) on for results would be another way to smooth out the results.

Answer 3

Here is my solution.

 (defn but-nth [si] [(get si) (into [] (concat (take is) (take-last (dec (- (count s) i)) s)))]) (defn combs [sofar r] (if (empty? r) sofar (for [[cz] (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")