creating permutation of a list in scheme

Question

I'm trying to write a function that creates the permutation of a list using just the basic list constructs (cons, empty, first, rest). I'm thinking of inserting the first value of the list everywhere in the recursive call of the rest of the list, but I'm having some trouble with my base case.

My code:

(define (permutation lst) 
   (cond
      [(empty? lst) (cons empty empty)]
      [else (insert_everywhere (first lst) (permutation (rest lst)))]))

(permutation (list 1 2)) gives me (list 1 2 empty 2 1 empty). Is there anything I can do to create a placeholder (such as empty) between the different combinations but not have the program interpret the placeholder as an element in the list?

Is my base case right?

Thanks!

Answer 1

I know it is an old post but following relatively simple and easy to understand solution based on random number checking could be of interest. It uses the permutation factorial formula to determine if all permutations have been collected.

(define (f n k)  ; lists will be from 0..(n-1)
  (define pl '()) ; all permutations list;
  (let loop ((ol '())) ; one permutation list; 
    (define a (random n))  ; 0 to n-1
    (if (member a ol) (loop ol)
        (begin (set! ol (cons a ol))
               (if (< (length ol) k) (loop ol)
                   (if (member ol pl) (loop '())
                       (begin (set! pl (cons ol pl))
                              (if(< (length pl)
                                    (/(factorial n)
                                      (factorial (- n k))))
                                 (loop '())
                                 pl ))))))))

(above code is in Racket- a Scheme derivative)

Testing:

(f 3 2)
(f 3 3)
(f 4 2)

Output:

'((2 1) (1 0) (0 1) (0 2) (1 2) (2 0))
'((2 1 0) (1 0 2) (0 1 2) (1 2 0) (0 2 1) (2 0 1))
'((2 1) (3 0) (1 0) (1 3) (3 2) (2 3) (0 3) (0 1) (0 2) (2 0) (1 2) (3 1))

Answer 2

The permutation algorithm isn't as simple as you imagine, it'll be really, really tricky to write just in terms of the basic list operations you mention, unless you write your own helpers that mirror built-in functions such as map, append (but why not use the built-ins in the first place?).

To get an idea of what needs to be done, take a look at the Rosetta Code page describing several possible solutions, look under the Scheme or Racket links. Here's an adaptation of one of the implementations from scratch shown in the linked page - and besides the basic list operations mentioned in the question, it uses append and map:

(define (permutations s)
  (cond [(empty? s) empty]
        [(empty? (rest s)) (list s)]
        [else
         (let splice [(l '()) (m (first s)) (r (rest s))]
           (append
            (map (lambda (x) (cons m x))
                 (permutations (append l r)))
            (if (empty? r)
                empty
                (splice (cons m l) (car r) (cdr r)))))]))

See how it works:

(permutations '(1 2 3))
=> '((1 2 3) (1 3 2) (2 1 3) (2 3 1) (3 2 1) (3 1 2))