(permute integer list) => list
(permute* integer list) => list
Purpose
Create permutations of sets.
Permute creates permutations without repetition,
and permute* creates permutations with repetition.
The result is a list of sets (lists).
Arguments
| n |
size of sets to create |
| set |
source set |
Dependencies
Example
(permute 2 '(a b c))
=> ((a b) (b a) (a c) (c a) (b c) (c b))
(permute* 2 '(a b c))
=> ((a a) (a b) (a c) (b a) (b b)
(b c) (c a) (c b) (c c))
(load "combine.scm")
(define (permute n set)
(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 (set)
(cond
((null? set) '())
((null? (cdr set)) (list set))
((null? (cddr set)) (rotations set))
(else (apply append
(map (lambda (rotn)
(map (lambda (x)
(cons (car rotn) x))
(permutations (cdr rotn))))
(rotations set))))))))
(apply append (map permutations (combine n set)))))
(define (permute* n set)
(cond
((zero? n) '())
((= n 1) (map list set))
(else (apply append
(map (lambda (x)
(map (lambda (sub)
(cons x sub))
(permute* (- n 1) set)))
set)))))
Copyright (C) 2007 Nils M Holm <nmh @ t3x . org>