0

I want to generate in Lisp the list of all permutations of a set. This is what I tried:

(defun ins(e n l)
    (cond
        ((equal n 1) (cons e l))
        (T (cons (car l) (ins e (1- n) (cdr l))))
    )
)

;; (print (ins '1 1 '(2 3)))
;; (print (ins '1 2 '(2 3)))
;; (print (ins '1 3 '(2 3)))

(defun insert(e n l)
    (cond
        ((equal n 0) nil)
        (T (cons (ins e n l) (insert e (1- n) l) ))
    )
)

;; (print (insert '1 3 '(2 3)))

(defun inserare(e l)
    (insert e (1+ (length l)) l)
)

;(print (inserare '1 '(2 3)))  -> ((2 3 1) (2 1 3) (1 2 3))

And from here I just can't make the final permutations function. I tried something like this:

(defun perm(L)
    (cond
        ((null L) nil)
        (T (append (perm (cdr L)) (inserare (car L) L)))  
    )
)

But this is not the good approach

hackermanwasd
  • 85
  • 4
  • See code around https://sourceforge.net/p/clocc/hg/ci/default/tree/src/cllib/math.lisp#l271 – sds Dec 21 '20 at 23:26
  • I see,but I wanted to do this pure recursively, without loops. And this also looks like a very proffesional Lisp code which is hard for me – hackermanwasd Dec 22 '20 at 00:04

1 Answers1

0

Here is one way.

First of all, if you have a list like (x . y) and you have the permutations of y you will need to create from them the permutations of (x . y). Well consider one of these permutations p, and let this be (p1 p2 ...). From this you will need to make a bunch of permutations including x: (x p1 p2 ...), (p1 x p2 ...), (p1 p2 x ...) ... (p1 p2 ... x).

So let's write a function to do this: a function which given some object and a list will 'thread' the object through the list creating a bunch of new lists with the object inserted at every point. For reasons that will become clear this function is going to take an extra argument which is the list of things to attach the new permutations to the front of. It's also going to use a little local function to do the real work.

Here it is:

(defun thread-element-through-list (e l onto)
  (labels ((tetl-loop (erofeb after into)
             (if (null after)
                 (cons (nreverse (cons e erofeb)) into)
               (tetl-loop (cons (first after) erofeb)
                          (rest after)
                          (cons (revappend (cons e erofeb) after) into)))))
    (tetl-loop '() l onto)))

I'm not going to explain the details of this function, but there are a couple of things worth knowing:

  • tetl-loop is thread-element-through-list-loop;
  • erofeb is before backwards, because the elements are in reverse order on it;
  • the nreverse is just a gratuitous hack because at that point erofeb is otherwise dead – there is effectively no mutation in this function.

And we can test it:

> (thread-element-through-list 1 '(2 3) '())
((2 3 1) (2 1 3) (1 2 3))

Now, OK, what we actually have is not just one permutation of y, we have a list of them. And we need to thread x through each of them, using `thread-element-through-list. So we need a function to do that.

(defun thread-element-through-lists (e ls onto)
  (if (null ls)
      onto
    (thread-element-through-lists
     e (rest ls)
     (thread-element-through-list e (first ls) onto))))

This also has an argument which defines what it's adding its results to, and you can see how this onto list now gets passed around to build the list.

And we can test this

> (thread-element-through-lists '1 '((2 3) (3 2)) '())
((3 2 1) (3 1 2) (1 3 2) (2 3 1) (2 1 3) (1 2 3))

Look at that carefully. I gave thread-element-through-lists, 1, and a list which was the permutations of (2 3), and it has turned out for me the permutations of (1 2 3). So what you now need to do (which I am not going to do for you) is to write a function which:

  • knows the permutations of () (which is () and of a single-element list (which is a list containing that list)`;
  • uses thread-elements-through-lists together with a recursive call to itself to compute the permutations of any longer list.
  • 1
    or we could [turn it inside out](https://stackoverflow.com/a/49907365/849891) and *uncons* a lot instead of consing. :) each permutation would be available separately, in its turn; we could copy them into the result list, or just process them one by one. – Will Ness Dec 22 '20 at 23:31
  • @WillNess: yes that's what I'd do in real life, or something like that. –  Dec 23 '20 at 12:00