3

I'm writing a function that takes a list and returns a list of permutations of the argument.

I know how to do it by using a function that removes an element and then recursively use that function to generate all permutations. I now have a problem where I want to use the following function:

(define (insert-everywhere item lst)
  (define (helper item L1 L2)
    (if (null? L2) (cons (append L1 (cons item '())) '())
        (cons (append L1 (cons item L2)) 
              (helper item (append L1 (cons (car L2) '())) (cdr L2)))))
  (helper item '() lst))

This function will insert the item into every possible location of the list, like the following:

(insert-everywhere 1 '(a b))

will get:

'((1 a b) (a 1 b) (a b 1))

How would I use this function to get all permutations of a list?

I now have:

(define (permutations lst)
  (if (null? lst) 
      '()
      (insert-helper (car lst) (permutations (cdr lst)))))

(define (insert-helper item lst)
  (cond ((null? lst) '())
        (else (append (insert-everywhere item (car lst)) 
                    (insert-helper item (cdr lst))))))

but doing (permutations '(1 2 3)) just returns the empty list '().

Greg Hewgill
  • 951,095
  • 183
  • 1,149
  • 1,285
Eric Mercer
  • 55
  • 1
  • 5
  • Related: https://stackoverflow.com/questions/20319593/creating-permutation-of-a-list-in-scheme – Flux Oct 12 '18 at 00:09

2 Answers2

4

Here is a function, that generates all permutations of numbers with size 'size' , that it consisted of the elements in the list 'items'

(define (generate-permutations items size)
  (if (zero? size)
      '(())
      (for/list ([tail (in-list (generate-permutations items (- size 1)))]
                 #:when #t
                 [i (in-list items)]
                 #:unless (member i tail))
        (cons i tail))))
Svante
  • 50,694
  • 11
  • 78
  • 122
vtodorova
  • 209
  • 2
  • 12
4

First, construct a family of related examples:

(permutations      '()) = ???
(permutations     '(z)) = ???
(permutations   '(y z)) = ???
(permutations '(x y z)) = ???

Figure out how each answer is related to the one before it. That is, how can you calculate each answer given the previous answer (for the tail of the list) and the new element at the head of the list?

Ryan Culpepper
  • 10,495
  • 4
  • 31
  • 30
  • I see, so each answer is the car of the current list inserted into all places of all the permutations of the previous list. How would I apply the insert-everywhere function to every permutation of the previous list then? – Eric Mercer Feb 16 '12 at 08:42
  • @EricMercer, sounds like a good job for an auxiliary function. – Ryan Culpepper Feb 16 '12 at 10:34
  • I am sorry, can you clarify? I am still not sure what to do? – Eric Mercer Feb 17 '12 at 00:59
  • @EricMercer, you just described a sub-problem: given a value and a list of lists, produce a list of lists of that value inserted into each possible position of each list in the input list. Handle it by defining an auxiliary function. Start by creating a family of related examples, etc etc. Note that your auxiliary function doesn't need to know anything about *permuations*; the input list-of-lists could be anything. Your auxiliary function might even need its own auxiliary function(s). – Ryan Culpepper Feb 17 '12 at 02:04
  • I wrote the auxiliary function and the permutations function, but something is still not working. When I do (permutations '(1 2 3)) it just gives me the empty list '() See my edited post for the two new functions – Eric Mercer Feb 17 '12 at 05:42
  • @EricMercer You're close. Think about the `(permutations '(1))` case. – Lindsey Kuper Feb 17 '12 at 06:15
  • Oh I got it, duh, the base case wasn't being properly handled. Thanks to everyone who helped! – Eric Mercer Feb 17 '12 at 06:27