SketchyLISP Reference |
Copyright (C) 2007 Nils M Holm |
<<[pair] | [Index] | [positive?]>> |
Conformance: SketchyLISP Extension
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) '()) (else (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)) (else (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))
<<[pair] | [Index] | [positive?]>> |