t3x.org / sketchy / prog / permute.html
SketchyLISP Stuff Copyright (C) 2006 Nils M Holm

permute

Conformance: R5RS

Purpose: Generate permutations of a set.

Arguments:
X - set

Implementation:

(define (permute x)
  (letrec

    ((rotate (lambda (x)
      (append (cdr x) (list (car x)))))

    (rotations (lambda (x)
      (letrec
        ((rot (lambda (x n)
          (cond ((null? n) '())
            (#t (cons x (rot (rotate x)
                             (cdr n))))))))
        (rot x x))))

    (permutations (lambda (lst)
      (cond ((null? lst) '())
        ((null? (cdr lst)) (list lst))
        ((null? (cddr lst)) (rotations lst))
        (#t (apply append
              (map (lambda (rotn)
                     (map (lambda (x)
                            (cons (car rotn) x))
                       (permutations (cdr rotn))))
                (rotations lst))))))))

    (permutations x)))

Example:

(permute '(a b c)) 
=> ((a b c) (a c b) (b c a) (b a c) (c a b) (c b a))