Nueve reinas con SAS (y R también)

No sé si habéis visto la película argentina Nueve reinas. Trata de unos timadores que engatusan a incautos para sacarles la platica.

Pero no voy a hablar de esas nueve reinas sino de las ocho de Solve Eight Queens Puzzle With SAS Macro. De su introducción extraigo y traduzco:

The Little SAS Book contiene un excelente ejemplo para ilustrar las diferencias entre SAS como lenguaje de programación y C++ mostrando lo complicado que puede resultar procesar conjuntos de datos con un lenguaje de propósito general. Son 28 líneas de código C++ y 5 de SAS para leer un fichero delimitado e imprimirlo por pantalla. Es un ejemplo perfecto de cómo SAS es un lenguaje de cuarta generación con un alto nivel de abstracción y expresividad.

Queremos revisar esta comparación bajo otra perspectiva mostrando cómo SAS es el lenguaje perfecto para manejar estructuras de datos complejas y lo fácil que resulta implementar con él algoritmos complejos.

(Nota: con R basta una línea para leer e imprimir un conjunto de datos delimitado: print( read.table( "fichero.txt", sep = ";" )).)

En particular, muestra un pedazo de código para resolver el problema de las ocho reinas. El problema se reduce a encontrar una permutación \sigma de los números 1:n tales que


\forall i \ne j, \left| i - j \right| \ne \left| \sigma(i) - \sigma(j) \right|

El código de SAS con el que resuelven este problema es así de estético, expresivo y comprensible:

%Macro FirstOf(List);%Scan(&List,1)%Mend;
%Macro RestOf(List);
  %Local lth;
  %Let lth=%Length(%FirstOf(&List));
  %If %Length(&List)><h %Then %Left(%Substr(&List,%Eval(1+<h)));
%Mend;

%Macro OkToAdd(Element,At=,To=,StartAt=);
  %If &To eq %str() or &Element eq %str() %Then 1;
  %Else %If %Sysfunc(Abs(%Eval(%FirstOf(&To)-&Element)))=
    %Sysfunc(Abs(%Eval(&At-&StartAt))) %Then %Do; 0 %Return;%End;
  %Else 
    %OkToAdd(&Element,At=&At,To=%RestOf(&To),StartAt=%eval(1+&StartAt));
%Mend;

%Macro qIter(PartialSolution=,List=,Level=,CounterName=);
  %Local item preFix sufFix;
  %If &List eq %str() %Then %Do;%Let &CounterName=%eval(1+&&&CounterName);
    %Put &&&CounterName [&PartialSolution];
  %End;
  %Else %Do;
    %let preFix=;%let item=%FirstOf(&List);%let sufFix=%RestOf(&List);
    %Do %Until (&preFix eq &List);   
      %If %OkToAdd(&item,At=&Level,To=&PartialSolution,StartAt=1) %Then
        %qIter(PartialSolution=&PartialSolution &item, 
          List=&preFix &sufFix,
          Level=%eval(&Level+1),
          CounterName=&CounterName
        );
        %let preFix=&preFix &item;%let item=%FirstOf(&sufFix);
        %let sufFix=%RestOf(&sufFix);
    %End;
  %End;
%Mend;

%let c=0;
%qIter(PartialSolution=,List=1 2 3 4 5 6 7 8,Level=1,CounterName=c)

Pero me he entretenido en implementar el mismo algoritmo con R y he aquí el resultado:

perm <- function( p, l ){
  foo <- function( x )
    ( a <- length( p ) ) == 0 || all( abs( a:1 ) != abs( l[x] - p ) )
 
  if ( length(l) == 0 ) 
    cat( p, "\n" )
  else 
    invisible( sapply( Filter( foo, 1:length(l) ), 
      function( i ) perm( c( p, l[i]), l[-i] ) ) )
}
 
perm(c(),1:8 )

No hay más color que el del resaltador de sintaxis, creo. Y en cuanto a la introducción del artículo, serán mis lectores los que habrán de decidir si tiene más que ver con las nueve que con las ocho reinas.

4 comentarios sobre “Nueve reinas con SAS (y R también)

  1. Francisco Javier Molina Lopez 25 enero, 2012 18:24

    Yo sustituiria lo de abs ( a + 1 – 1 : a ) por a : 1.

    Tambien comentar que lo que hace

    perm ( p, l ) es intentar aumentar la permutacion p por la derecha con nuevos componentes ( los de l ), de manera que se verifique la condicion que aparece en la formula del articulo ( para todo i distinto de j, … ).

    perm ( p, l ) hace esto llamandose a si misma recursivamente y en cada interacion recursiva intentando ampliar p con un unico elemento de l. En cada llamada que se hacer a perm ( p, l ), la permutacion p verifica la condicion que antes mencionaba.

    Gracias, datanalytics, por el codigo.

  2. edwin 6 febrero, 2012 3:10

    Muy ilustrativo, y comprensible, da gusto leer codigo asi

Los comentarios están desabilitados.