Lisp »Tips 'n Tricks »Funzioni ricorsive in AutoLISP »1 | 2 | 3 | 4 | 5 | 6 | 7 a , b , c , d , e

Permutazioni di n elementi

Le permutazioni di n elementi sono n! e con le funzioni ricorsive è possibile scrivere in AutoLISP un programma che mostra tutte le permutazioni di n elementi.

PERM è la traduzione di un programma in C.

Perm.c

/**************************************************
* Dal testo: C, Java, Laboratorio di Programmazione 
   Mc Graw Hill, 1997  
   Copyright 1997: A. Cisternino, G.Fiorentino, 
                   M.R.Lagana', F.Romani e F.Turini
***************************************************/ 

#include <stdio.h>

#define SZ 10
typedef int Vettore[SZ];

void perm(Vettore v, int k, int n);
void stampa(Vettore v, int n);
void scambia(Vettore v, int i, int j);

int main() {
  Vettore vett;
  int i;

  for (i = 0; i < 3; i++)
    vett[i] = i + 1;
  perm(vett, 0, 3);

  return 0;
}

void perm(Vettore v, int k, int n) {
  int i;

  if (k == n - 1)
    stampa(v, n);
  else
    for (i = k; i < n; i++) {
      scambia(v, i, k);
      perm(v, k + 1, n);
      scambia(v, i, k);
    }
}

void stampa(Vettore v, int n) {
  int i;

  for (i = 0; i < n; i++)
    printf("%3i", v[i]);
  putchar('\n');
}

void scambia(Vettore v, int i, int j) {
  int temp = v[i];

  if (i != j) {
      v[i] = v[j];
      v[j] = temp;
}

Perm.lsp

;;;
;;;    perm.lsp - 27 Febbraio 2004
;;;    (C) 2004 by Claudio Piccini.
;;;    www.cg-cad.com
;;;    
;;;    Permutazioni di n elementi
;;;

(defun permuta (ls k n i)
 (if (= k (- n 1))
  (stampa ls)
  (progn
   (setq i k)
   (while (< i n)
    (scambia i k)
    (permuta ls (+ k 1) n i)
    (scambia i k)
    (setq i (1+ i))
   )
  )
 )
)

(defun stampa (ls / e)
 (setq e 0)
 (repeat (length ls)
  (princ (nth e ls))
  (princ " ")
  (setq e (1+ e))
 )
 (princ "\n")
)

(defun scambia (i j / temp a b q lss)
 (setq temp (nth i ls))
 (if (/= i j)
  (progn
   (setq a (nth j ls))   
   (setq q 0)
   (repeat (length ls)
    (setq b (nth q ls))
    (cond
     ((= q i)
      (setq lss (append lss (list a)))
     )
     ((= q j)
      (setq lss (append lss (list temp)))
     )
     ((and (/= q i)(/= q j))
      (setq lss (append lss (list b)))
     )
    ) 
    (setq q (1+ q))
   )
   (setq ls lss)
   (setq lss nil)
  )
 )
)

(defun c:perm ( / x i k ls )
 (setvar "cmdecho" 0)
 (setq i 0)
 (setq k 0)
 (repeat 4
  (setq x (getint "\nNumero? "))
  (setq ls (append ls (list x)))
 )
 (permuta ls 0 4 i)
 (setvar "cmdecho" 1)
 (princ)
)
;;;eof

Test del LISP
Il lisp permette di inserire 4 numeri (per aumentare o diminuire n intervenire qui:

 (repeat 4
  (setq x (getint "\nNumero? "))
  (setq ls (append ls (list x)))
 )
 (permuta ls 0 4 i)

Command: perm
Numero? 1
Numero? 2
Numero? 3
Numero? 4

1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 3 2
1 4 2 3
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 3 1
2 4 1 3
3 2 1 4
3 2 4 1
3 1 2 4
3 1 4 2
3 4 1 2
3 4 2 1
4 2 3 1
4 2 1 3
4 3 2 1
4 3 1 2
4 1 3 2
4 1 2 3

Al posto dei numeri è possibile inserire dei caratteri, basta modificare il codice in questo modo:

 (repeat numero_di_caratteri
  (setq x (getstring "\nCarattere? "))
  (setq ls (append ls (list x)))
 )
 (permuta ls 0 numero_di_caratteri i)

Negli argomenti passati alla funzione (scambia) non c'è nel sorgente LISP l'argomento ls=lista - v=vettore in C ;)

Lisp »Tips 'n Tricks

Ultimo Aggiornamento_Last Update: 27 Febbraio 2004