/usr/lib/s9fes/permute.scm is in scheme9 2010.11.13-2.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 | ; Scheme 9 from Empty Space, Function Library
; By Nils M Holm, 2009
; See the LICENSE file of the S9fES package for terms of use
;
; (permute integer list) ==> list
; (permute* integer list) ==> list
;
; (load-from-library "permute.scm")
;
; Create k-permutations of the elements of the given list. K (the
; size of the permutations) is specified in the integer argument.
; PERMUTE creates permutations without repetition and PERMUTE*
; creates permutations with repetition.
;
; 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-from-library "combine.scm")
(define (permute n set)
(letrec
((rotate
(lambda (x)
(append (cdr x) (list (car x)))))
(rotations
(lambda (x)
(letrec
((rot (lambda (x n)
(if (null? n)
'()
(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)))))
|