241806_es-ES

liliconcom

Ayuda JSL: Cómo crear todas las permutaciones de un vector o una lista

Estoy tratando de encontrar la mejor manera de escribir JSL para enumerar todas las permutaciones de un vector o lista.  

 

Un algoritmo que he encontrado, que parece prometedor, es Algoritmo del montón https://en.wikipedia.org/wiki/Heap%27s_algorithm , pero parece que no puedo entender cómo codificar esto.¿Alguien puede ayudarme aquí?  

 

Me doy cuenta de que cuanto mayor sea el tamaño de un vector o lista, el tamaño de la salida crecerá factorialmente (¡el número de permutaciones de k elementos es k! ), por lo que también estoy interesado en una forma de generar cada elemento en la lista de permutaciones y realizar una operación en esa permutación y luego descartarla cuando ya no sea necesario para generar las siguientes permutaciones.  

Re: Ayuda JSL: Cómo crear todas las permutaciones de un vector o una lista

Aquí hay una función que creé basada en el guión de Craige.

</CODE></PRE><PRE><CODE class="">Names Default To Here( 1 );
Clear Log();

permutate = Function( {list},
 per = New Namespace();
 per:swap = Function( {targetList, firstPosition, secondPosition}, //returns a list with elements in firstPosition and secondPosition swapped
  {temp},
  temp = targetList[firstPosition];
  targetList[firstPosition] = targetList[secondPosition];
  targetList[secondPosition] = temp;
  Return( targetList );
 );
 per:generate = Function( {k},
  {i, temp},
  If( k == 1,
   Insert Into( per:result, Eval List( List( per:A ) ) ), //else
   per:generate( k - 1 );
        // Generate permutations for kth swapped with each k-1 initial
   For( i = 0, i < k - 1, i += 1, 
            // Swap choice dependent on parity of k (even or odd)
    If( Mod( k, 2 ) == 0,
     per:A = per:swap( per:A, k, i + 1 ), //else
     per:A = per:swap( per:A, 1, k )
    );
    per:generate( k - 1 );
   );
  )
 );
 per:result = {};
 per:A = list;
 per:generate( N Items( per:A ) );
 result = per:result;
 Delete Namespaces( per );
 Return( result );
);



A = {"a", "b", "c", "d"};
permutate( A );

 

Re: Ayuda JSL: Cómo crear todas las permutaciones de un vector o una lista

Gracias por el código a ambos, fue útil.La recursividad siempre me duele la cabeza y parece que JSL no te permite hacer recursividad fácilmente de una manera que permita asignar la salida de la secuencia de permutaciones a una lista o matriz.  

 

Después de usar las funciones del generador, me di cuenta de que lo que quería hacer requeriría demasiado tiempo de cálculo.  

 

Aquí está el problema: existe una medida de eficacia utilizada para las vacunas que puede no prevenir, pero sí reducir la gravedad de una enfermedad llamada fracción mitigada (MF).se describe aquí .Se basa en el estadístico de prueba de suma de rangos de Wilcoxson (W) para la comparación de dos grupos.Entonces, lo que quería hacer era enumerar todos los valores posibles de W (usando todas las permutaciones posibles de rangos) para dos grupos con tamaños de muestra determinados, y luego obtener de ahí todos los valores posibles de MF.Lo que realmente quería mostrar era que los criterios que estamos usando para que MF demuestre eficacia equivalen a un valor crítico para la distribución de W bajo la hipótesis nula de que la distribución para ambos grupos es la misma.  

 

La forma en que resolví mi problema fue asumir una distribución subyacente para cada grupo y hacer un estudio de simulación para obtener una distribución de MF bajo esos supuestos.(Además, para tamaños de muestra más grandes, W es asintóticamente normal bajo H0: (sin diferencia en las poblaciones), por lo que también es otra forma de resolver parte del problema).Sin embargo, el uso de la simulación me permitió examinar también el poder bajo diferentes hipótesis alternativas, lo que hizo que mi análisis fuera más completo.

  

Re: Ayuda JSL: Cómo crear todas las permutaciones de un vector o una lista

Segunda mitad de tu pregunta, ¿cómo? no almacenar la lista completa?

 

Gran pregunta; Creo que la única respuesta que ofrece JMP es hacer que su código se llame desde donde la solución de JIM imprime () o mi solución escribe (). Si JMP ofreciera un generador o co-rutinas @XanGregg , podría tener una solución más flexible en la que su código podría pedirle al generador la siguiente secuencia desde el punto (o puntos) donde la necesita. Enumerarlos en una tabla con anticipación podría ser la mejor opción si lo necesita.

 

¿Eres libre de compartir más detalles sobre el proyecto? ¡El tiempo necesario para mirar los 14! o 15! Las permutaciones son probablemente prohibitivas. Si espera encontrar una respuesta suficientemente buena antes de observar todas las permutaciones, tal vez usar permutaciones aleatorias, tal vez con un algoritmo de recocido, podría ser una mejor opción.

Re: Ayuda JSL: Cómo crear todas las permutaciones de un vector o una lista

// Heap's algorithm from https://en.wikipedia.org/wiki/Heap%27s_algorithm
// note: the above uses 0-based arrays, JMP uses 1-based. The above also 
// must be using call-by-reference and JMP uses call-by-value. below uses
// a global array A rather than trying to find a way to pass the array by
// reference. For similar reasons, swap(x,y) is expanded in-line.

generate = Function( {k},
 {i, temp},
 If( k == 1,
  Write( "\!n", A );//
 , //else
  // Generate permutations with kth unaltered
  // Initially k == length(A)
  generate( k - 1 );
        // Generate permutations for kth swapped with each k-1 initial
  For( i = 0, i < k - 1, i += 1, 
            // Swap choice dependent on parity of k (even or odd)
   If( Mod( k, 2 ) == 0,
    temp = A[i + 1];
    A[i + 1] = A[k];
    A[k] = temp;
   , //else
    temp = A[1];
    A[1] = A[k];
    A[k] = temp;
   );
   generate( k - 1 );
  );
 )
);

A = [1 2];
generate( N Cols( A ) );

A = {"a", "b", "c"};
generate( N Items( A ) );

A = 1 :: 4;
generate( N Cols( A ) );

[1 2]
[2 1]
{"a B C"}
{"b", "a", "c"}
{"taxi"}
{"a", "c", "b"}
{"b", "c", "a"}
{"c", "b", "a"}
[1 2 3 4]
[2 1 3 4]
[3 1 2 4]
[1 3 2 4]
[2 3 1 4]
[3 2 1 4]
[4 2 1 3]
[2 4 1 3]
[1 4 2 3]
[4 1 2 3]
[2 1 4 3]
[1 2 4 3]
[1 3 4 2]
[3 1 4 2]
[4 1 3 2]
[1 4 3 2]
[3 4 1 2]
[4 3 1 2]
[4 3 2 1]
[3 4 2 1]
[2 4 3 1]
[4 2 3 1]
[3 2 4 1]
[2 3 4 1]

 

¡Gracias por hacerme volver a visitar la versión de Wikipedia! La última vez encontré una variación diferente que era más fácil de convertir.

Re: Ayuda JSL: Cómo crear todas las permutaciones de un vector o una lista

Convertí la forma no recursiva del código a JMP.A ver si esto ayuda

generate = Function( {n, A}, 
    //c is an encoding of the stack state. c[k] encodes the for-loop counter for when generate(k+1, A) is called
 
 c = {};

 For( i = 1, i <= n, i++, c[i] = 1 );
 Print( A );
    
    //i acts similarly to the stack pointer
 i = 1;
 While( i <= n,
  If( c[i] < i,
   If( Mod( i, 2 ) == 0, 
                //swap(A[0], A[i])
    temp = A[1];
    A[1] = A[i];
    A[i] = temp;
   , 
                //swap(A[c[i]], A[i])
    temp = A[c[i]];
    a[c[i]] = a[i];
    a[i] = temp;
   );
   Print( A );
            //Swap has occurred ending the for-loop. Simulate the increment of the for-loop counter
   c[i] = c[i] + 1; 
            //Simulate recursive call reaching the base case by bringing the pointer to the base case analog in the array
   i = 1;
  , 
        //else
   //Calling generate(i+1, A) has ended as the for-loop terminated. Reset the state and simulate popping the stack by incrementing the pointer.
   c[i] = 1;
   i = i + 1;
  )
 );
);