CODEWITHSUNDEEP
clojurefunctional-programmingclojure-core.logic
slimbo
slimbo

Reputation: 2759

What is wrong with my Clojure implementation of permutations

I know that there are multiple ways to solve permutations using Clojure. I have tried creating a DCG (definite clause grammar) using Core.Logic but the DCG part of the library is too experimental and didn't work.

In the code below I try two different approaches. One is a list comprehension (commented out), which is similar to the way I would solve this problem in Haskell.

The second approach uses MapCat to apply cons/first to each return value from the recursive call to permutation. Remove item makes sure that I don't use the same letter more than once for each position.

Can someone please explain what is wrong with the list comprehension approach and what is wrong with the MapCat approach. It is much easier to reason about this kind of problem in Haskell - is there some perspective I am missing about 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)

  )
)

Edit: @thumbnail solved the MapCat sub-problem in the comments already

Upvotes: 3

Views: 570

Answers (2)

Ian Davies
Ian Davies

Reputation: 1

We can add support for duplicates by working with the index of the items in the original sequence. The function append-index returns a new sequence where the index and value are now in a vector. For example '(\a \b \c) -> '([0 \a] [1 \b] [2 \c] [3 \a]).

You then work with this sequence within the for loop, taking the index of the item when we want to remove it from the original and taking the value when we cons it to the tail sequence.

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

Thanks to the previous post, I was struggling with the permutation problem myself and had not considered using a for comprehension.

Upvotes: 0

Thumbnail
Thumbnail

Reputation: 13473

We can simplify the permutation function to

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

Attempting to use it on anything plural produces java.lang.IllegalArgumentException: Don't know how to create ISeq from: ... whatever you are trying to permute.

There are two errors:

  • permutation should return a sequence of sequences, even when there is only one of them; so xs should be (list xs). This is what causes the exception.
  • The permutation for a given x from xs and, given that, a permutation y of xs without xis just (cons x y).

With these corrected, we have

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

For example, 

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

The above works only if all the permuted things are different. At the other extreme ...

(permutation [1 1 1])
;()

Also,

  • count scans the whole of a sequence. To find out if there is only one element, (seq (rest xs)) is faster than (= (count xs) 1).
  • And the remove in remove-item scans the whole sequence. There is little we can do to mend this.

If we know that we are dealing with distinct things, it is simpler and faster to deal with them as a set: 

(defn perm-set [xs]
  (case (count xs)
    0 '()
    1 (list (seq xs))
    (for [x xs, y (perm-set (disj xs x))]
      (cons x y)))
  • It works for empty sets too.
  • count is instant and disj is almost constant time, so this is faster.

Thus:

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

Upvotes: 5

Related Questions