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))

Nenhum comentário:

Postar um comentário