0

I am trying to pick up some Common Lisp. I'm accustomed to curly-brackets imperative languages, and am still having trouble wrapping my head around Lisp-style thinking and syntax.

Below is a permutations function I'm trying to write. It is currently broken.

If I run this function with

(permutations '(1 2 3))

I can see at the breakpoint labeled "and here" that lists such as (2 3), (3 2), (1 3) are being generated at that point. But then by running a trace in SLIME I see that the the permutation function is returning (2), (3), and (1) after that call (first item in the lisp). The top level function then just returns nil (which I also don't understand).

(defun permutations (coll) (if (= 1 (length coll)) (print (list (first coll))) (loop for el in coll do (map 'list #'(lambda (combos) (if (break "you got here with arguments ~:S." (listp combos)) (cons el combos) (break "and here: ~:S " (list el combos)))) (permutations (remove el coll)) ))))

What am I doing wrong here? Thanks in advance for any help.

EDIT: Here is what I have after changing the function in response to jlahd's comments. This returns (((1 ((2 3))) (1 ((3 2)))) ((2 ((1 3))) (2 ((3 1)))) ((3 ((1 2))) (3 ((2 1))))) when called with the original example. Haven't figured out how to fix the nested list thing yet.

(defun permutations (coll) (if (= 1 (length coll)) (print (list (first coll))) (loop for el in coll collect (map 'list #'(lambda (combos) (list el combos)) (permutations (remove el coll)) ))))

EDIT: Ok, thanks everyone for the help here! Here is what I have after Rörd and wxvxw's comments. This runs and returns ((1 2 . 3) (1 3 . 2) (2 1 . 3) (2 3 . 1) (3 1 . 2) (3 2 . 1)). I'm not exactly sure what the "dotted pair" notation here means as compared to a plain list, but otherwise this seems good.

(defun permutations (coll) (if (not (cdr coll)) (list (first coll)) (loop for el in coll nconc (mapcar #'(lambda (combos) (cons el combos)) (permutations (remove el coll)) ))))
Improve this question
5
  • 1
    Use an editor to indent your code correctly. That improves readability a lot. Commented Sep 14, 2013 at 21:03
  • Use the loop keyword nconc instead of collect to append the lists generated by the map into a single list. Commented Sep 14, 2013 at 21:17
  • Also, use cons instead of list to add a single element to the beginning of a list. Commented Sep 14, 2013 at 21:18
  • Also, (map 'list ...) is equivalent to (mapcar ...). (= 1 (length some-list)) is an inherently bad idea, because it's invariant (not (cdr some-list)) will at all times be faster or the same speed. Also, package alexandria has a function to compute permutations. You may want to take a look at how it's done there. Commented Sep 14, 2013 at 21:31
  • You get the dot if the second argument to cons is not a list. A "proper list" is a chain of pairs in which the last second element of a pair is nil/() (these are different representations of the same value). If it's anything else, it's a "dotted list". Commented Sep 14, 2013 at 22:17

1 Answer 1

Reset to default
2

You are discarding all data you gather in the loop. Change do to collect and you are much further.

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

Okay, thanks. If I do that the function returns ((NIL NIL) (NIL NIL) (NIL NIL)), which is progress.
Oh yes. You are also not handling the latter break correctly but discarding results there. Just get rid of the if along with the breaks.
Ah my bad -- for some reason I thought that the break functions returned their arguments. Really stupid. With that stuff removed the function returns (((1 ((2 3))) (1 ((3 2)))) ((2 ((1 3))) (2 ((3 1)))) ((3 ((1 2))) (3 ((2 1))))) . I need some way to give it a choice between consing on to an old list and creating a new so I don't get these nested lists. I was trying to do this with the if statement, but the conditional argument to the if statement was always nil apparently.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.