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!

looks like accidental flattening of the resulting list of lists. the error is most probably in `insert_everywhere` but the code is not included in the post. as to the algorithm, see also [this](https://stackoverflow.com/q/49848994/849891) Common Lisp entry -- it should be possible to translate its code to Scheme. — Will Ness, May 26 '19 at 17:12
just stumbled by pure chance on [an old answer of mine](https://stackoverflow.com/a/22164928/849891) with a similar looking pseudocode.... — Will Ness, May 27 '19 at 06:55

Óscar López · Answer 1 · 2013-12-02T03:35:09.797

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

I upvoted your answer because it's correct, but I think the OP is trying to follow the HtDP design recipe. There is a reference solution to this in HtDP, and I glanced at it when looking at the OP's previous question, but yeah, it's not the kind of answer you might expect. — C. K. Young, Dec 02 '13 at 03:56

rnso · Answer 2 · 2016-10-24T02:41:28.777

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

score 0 · Answer 3 · answered May 01 '20 at 00:22

0

There is no mistake in your base case Try using map and lambda

#lang scheme
(define (permutations items)
  (if (null? items) '(())
      (apply append
             (map (lambda (element)
            (map (lambda (permutation)
               (cons element permutation))
             (permutations (remove element items))))
          items))))

answered May 01 '20 at 00:22

Navya Vadakapuram

1

2

There was no reason to create a second answer; you should have just edited your first answer. Now you should delete the _other_ answer. – ad absurdum May 01 '20 at 00:49

creating permutation of a list in scheme

3 Answers3

Linked