Creating an n-sized permutation with scheme using only basic constructs

Is it possible to generate n-sized permutations of a list us开发者_StackOverflowing only the basic scheme constructs?

---

With define you can do it like this (without define the answer would be no, because you'll need to use recursion):

First define a function that takes a list of lists and a value and returns a list of lists where the given item has been prepended to each list in the original list of lists.

This can be done by writing a simple recursive function that uses cons to prepend the item to the first list (using car to get the first list) and then uses cons again to prepend the extended list to the result of calling the function on the other lists (i.e. on the cdr of the list of lists). If the list is empty (and thus doesn't have a car and cdr), return the empty list.

You'll also need a function that removes a given item from a list. This can also be done by defining a simple recursive function that takes an item and a list. At each step the `car´ of the given list should be prepended to the result of the recursive call if it is not equal to the item that is to be deleted. If it is equal, the result of the recursive call should be returned directly.

Further you'll need a function to concatenate lists. This can also be implemented recursively without too much trouble.

Then define a function that given a list of lists and an item calls the previous function with the item and each sublist as its argument.

Now define the a function that creates n-sized permutations. This function should take the number n and a list. If n is 0, it should return the empty list. Otherwise it should call itself recursively for each item x in the list with (- n 1) as the new value for n and the result of removing x from the list as the new value for the list. Then the results of the recursive calls should be concatenated.

---

This is an explanation of the code found in Rosetta, although, I have changed the variable names to help make it more readable, and added my explanation of the code below. I did check to see if the code works in DrRacket, and it does.

Before defining permute, two helper functions are required namely, seq and insert.

seq builds a list containing a sequence of numbers. For example (seq 0 3) -> (0 1 2 3). The elements (numbers) in the list are used in the insert function to insert the carItem at various positions in the 'cdr' list.

(define (seq start end) 
  (if (= start end) 
      (list end)    ; if start and end are the same number, we are done
      (cons start (seq (+ start 1) end)) 
      )
  )

insert generates a list with the carItem inserted in the "n"th position of the cdrList. For example, (insert '(b c) 0 'a) -> '(a b c) and (insert '(b c) 2 'a) -> '(b c a).

(define (insert cdrList n carItem)
  (if (= 0 n)
      (cons carItem cdrList) ; if n is 0, prepend carItem to cdrList
      (cons (car cdrList)  
            (insert (cdr cdrList) (- n 1) carItem))))

Finally, as for the main function permute, it uses insert and seq in a recursive manner. For example, when plist = '(b,c) the lambda evals to the following:

; (map (lambda (n)
;    (insert '(b c) n 'a))
;    '(0 1 2)) -> output of seq function given n = 2, which is length of '(b c)
; '((a b c) (b a c) (b c a)) ---> will be the output

(define (permute mylist)
  (if (null? mylist)
      '(())
      (apply append (map (lambda (plist)
                           (map (lambda (n)
                                  (insert plist n (car mylist)))
                                (seq 0 (length plist))))
                         (permute (cdr mylist))))))

(permute '(a b c))

If the above nested lambdas makes your head spin (it did for me), find below, IMHO, a more readable "define" version, thanks to Matthias Felleisen:

(define (permute mylist)
  (cond 
    [(null? mylist) '(())]
    [else 
      (define (genCombinationsFor plist)
      (define (combineAt n) (insert plist n (car mylist)))
        (map combineAt (seq 0 (length plist))))
        (apply append (map genCombinationsFor (permute (cdr mylist))))]))