Permutações

Uma subrotina para permutações.

Ver…

(defun permuteme (lst / global recursive subst2 swap)
(
setq
;função que substitui um elemento por outro numa lista:
subst2 (lambda (lst pos elm / tmp)
(
repeat pos
(Setq tmp (cons (car lst) tmp)
lst (cdr lst)))
(
append (reverse tmp) (list elm) (cdr lst)))

;função que inverte as posições de 2 elementosnuma lista:
swap (lambda (lst p1 p2)
(
subst2 (subst2 lst p2 (nth p1 lst)) p1 (nth p2 lst)))

;função recursiva que cria as permutações
recursive (lambda ( k / i len)
(
setq len (length lst))
(
if (= k len)
(
setq global (cons lst global))
(
progn
(setq i k)
(
repeat ( len k)
(
setq lst (swap lst i k))
(
recursive (1+ k))
(
setq lst (swap lst i k)
i (1+ i)))))))
;inicia a função recursiva, ela cria a lista global:
(recursive 0)

;devolve a lista de permutações:
global)

Com ela é possível criar uma lista com todas as permutações possíveis de uma lista, exemplo: (permuteme ‘(a b c d)) retorna:
((D A B C) (D A C B) (D C A B) (D C B A) (D B A C) (D B C A) (C D B A) (C D A B) (C A D B) (C A B D) (C B D A) (C B A D) (B D A C) (B D C A) (B C D A) (B C A D) (B A D C) (B A C D) (A D B C) (A D C B) (A C D B) (A C B D) (A B D C) (A B C D))

Deixe um comentário

Carrinho de compras
Rolar para cima