🚀 go-pugleaf

Wenceslao <wrequejod@uned.es> writes:

> Estoy intentando hacer una funcion recursiva para obtener todas las
> permutaciones de elementos de un vector, es un vector de "puntos", calulo
> una combinacion (dejando primero y ultimo intactos, es un programa para
> obtener la ruta mas corta recorriendo varios puntos) y calculo la
> distancia, si la distancia es menor que con la que empeze, la guardo y sigo
> intentando....
> Pero creo que tengo un problema con esto de la recursividad, a ver si veis
> algun fallo de esos MUY_GORDOS.....
> Esta es la funcion ....
>
>
> double FindShortestPath(int size, Point arr[])
> {
>   Point a;
>   double minimum=TotalPathDistance(6,arr);
>   for (int i=1;i<size-1;i++)
>   {
>    for(int j=1;j<size-1;j++)
>    {
>      a=arr[j];
>      arr[j]=arr[j+1];
>      arr[j+1]=a;
>     // cout<<TotalPathDistance(6,arr)<<endl;
>      if(TotalPathDistance(6,arr)<minimum)
>      {
>        minimum=TotalPathDistance(6,arr);
>
>      }
>      else
>      {
>           FindShortestPath(size-j,arr);
>      }
>    }
>    }
> return minimum;
> }

Deberias tratar de separar los dos problemas:

    - generar permutaciones,

    - calcular la ruta m�s corta.


Si quieres ver un ejemplo de generar permutaciones en C++, vease la
clase BpArrangementSansRepeat de mi biblioteca bpcombi:

cvs -z3 -d :pserver:anonymous@cvs.informatimago.com:/usr/local/cvs/public/chrooted-cvs/cvs co common/bpcombi





Si realmente quieres una funcion recursiva, aqui tienes:

(defun permute (vector index action)
  (cond
   ((zerop index)  (funcall action vector))
   (t  (permute vector (1- index) action)
       (dotimes (i index)
         (rotatef (aref vector index) (aref vector i))
         (permute vector (1- index) action)
         (rotatef (aref vector index)  (aref vector i))))))

(permute #(0 1 2) 2 (function print))
-->
#(0 1 2) 
#(1 0 2) 
#(2 1 0) 
#(1 2 0) 
#(0 2 1) 
#(2 0 1) 


Luego se puede calcular la longitud de una ruta:

(defstruct (point (:conc-name) (:type list))  x y)
(defun square (x) (* x x))
(defun length-of-path (path)
  (loop for i from 0
        for j from 1 below (length path)
        for p = (aref path i)
        for q = (aref path j)
        sum (sqrt (+ (square (- (x p) (x q))) (square (- (y p) (y q)))))))

Y f�cilmente se puede encuentrar la ruta m�s corta:

(defun find-shortest-path (points)
  (let ((minlen nil)
        (minpath nil))
    (permute points
             (1- (length points))
             (lambda (permutation)
               (let ((pathlen (length-of-path permutation)))
                 (when (or (null minlen) (< pathlen minlen))
                   (setf minlen  pathlen
                         minpath (copy-seq permutation))))))
    (values minlen minpath)))
  
(find-shortest-path  #((10 2) (11 7) (14 5) (16 0) (18 9) (20 9)))
-->
22.68598 ;
#((16 0) (10 2) (11 7) (14 5) (18 9) (20 9))

-- 
__Pascal Bourguignon__                     http://www.informatimago.com/
-----BEGIN GEEK CODE BLOCK-----
Version: 3.12
GCS d? s++:++ a+ C+++ UL++++ P--- L+++ E+++ W++ N+++ o-- K- w--- 
O- M++ V PS PE++ Y++ PGP t+ 5+ X++ R !tv b+++ DI++++ D++ 
G e+++ h+ r-- z? 
------END GEEK CODE BLOCK------