Permutaciones en Scheme

Este programa en Scheme calcula todas las permutaciones de una lista dada.

;; Calcula todas las permutaciiones de una lista

;;Leyenda ->
;;Para el manejo de listas tenemos
;;car -> Lista que resulta al incluir un objero en una lista.
;;cdr -> Lista que resulta al quitarle el primer elemento a una lista
;;pair? -> Si el objeto es de tipo "Par Punteado" devuelve tru, en otro caso, devuelve false.
;;select ->
;;map (Seguido por proc) -> Se le aplica proc a cada elemento de la lista
(define (perm xs)
(if (pair? xs)
(select (car xs) '() (cdr xs))
'(())))

;;Selecciona X como primer elemento de la lista
;;Lo agrega a las permutaaciones de la lista que va quedando representada por la lista de los elementos antes de X.

(define (select x revprefix postfix)
(mapconsapp x (perm (revapp revprefix postfix))
(if (pair? postfix)
(select (car postfix)
(cons x revprefix)
(cdr postfix))
'())))

;; Hace un map de X en la lista de listas xss y concatena el resto.

(define (mapconsapp x xss rest)
(if (pair? xss)
(cons (cons x (car xss)) (mapconsapp x (cdr xss) rest))
rest))

;; Voltea Xs y concatena el resto.
(define (revapp xs rest)
(if (pair? xs)
(revapp (cdr xs) (cons (car xs) rest))
rest))

Para utilizarla simplemente la llamamos desde nuestro interprete de Scheme ( En mi caso DrScheme) de la siguiente manera;

 > (perm ‘(1 2 3 4))
(list
 (list 1 2 3 4)
 (list 1 2 4 3)
 (list 1 3 2 4)
 (list 1 3 4 2)
 (list 1 4 2 3)
 (list 1 4 3 2)
 (list 2 1 3 4)
 (list 2 1 4 3)
 (list 2 3 1 4)
 (list 2 3 4 1)
 (list 2 4 1 3)
 (list 2 4 3 1)
 (list 3 1 2 4)
 (list 3 1 4 2)
 (list 3 2 1 4)
 (list 3 2 4 1)
 (list 3 4 1 2)
 (list 3 4 2 1)
 (list 4 1 2 3)
 (list 4 1 3 2)
 (list 4 2 1 3)
 (list 4 2 3 1)
 (list 4 3 1 2)
 (list 4 3 2 1))

 

Espero que les sirva. A mi me sirvió bastante …. … Read More >Permutaciones en Scheme

Deja un comentario

This site uses Akismet to reduce spam. Learn how your comment data is processed.