241806_it-IT

liliconcom

Guida JSL: come creare tutte le permutazioni di un vettore o di una lista

Sto cercando di capire il modo migliore per scrivere del JSL per enumerare tutte le permutazioni di un vettore o di un elenco.  

 

Un algoritmo che ho trovato, che sembra promettente, è Algoritmo di Heap https://en.wikipedia.org/wiki/Heap%27s_algoritmo , ma non riesco proprio a capire come codificarlo.Qualcuno può aiutarmi qui?  

 

Mi rendo conto che maggiore è la dimensione di un vettore o di un elenco, la dimensione dell'output aumenterebbe in modo fattoriale (il numero di permutazioni di k elementi è k! ), quindi sono anche interessato a un modo per generare ciascun elemento nell'elenco delle permutazioni ed eseguire un'operazione su quella permutazione e quindi scartarla quando non è più necessaria per generare le permutazioni successive.  

Ri: Guida JSL: come creare tutte le permutazioni di un vettore o di un elenco

Ecco una funzione che ho creato sulla base dello script di 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 );

 

Ri: Guida JSL: come creare tutte le permutazioni di un vettore o di un elenco

Grazie per il codice a entrambi, è stato utile.La ricorsione mi fa sempre male la testa e sembra che JSL non ti consenta facilmente di eseguire la ricorsione in un modo che consenta di assegnare l'output della sequenza di permutazioni a una lista o matrice.  

 

Dopo aver utilizzato le funzioni del generatore, mi sono reso conto che ciò che volevo fare avrebbe richiesto troppo tempo di calcolo.  

 

Ecco il problema: esiste una misura di efficacia utilizzata per i vaccini che potrebbe non prevenire ma ridurre la gravità di una malattia chiamata frazione mitigata (MF).È descritto Qui .Si basa sulla statistica del test Wilcoxson Rank-Sum (W) per il confronto di due gruppi.Quindi quello che volevo fare era elencare tutti i possibili valori di W (utilizzando tutte le possibili permutazioni di ranghi) per due gruppi con determinate dimensioni del campione, e quindi ottenere da lì tutti i possibili valori di MF.Ciò che volevo davvero dimostrare era che i criteri che usiamo per MF per dimostrare l'efficacia equivalgono a un valore critico per la distribuzione di W sotto l'ipotesi nulla che la distribuzione per entrambi i gruppi sia la stessa.  

 

Il modo in cui ho risolto il mio problema è stato assumere una distribuzione sottostante per ciascun gruppo ed eseguire uno studio di simulazione per ottenere una distribuzione di MF con tali presupposti.(Inoltre, per campioni di dimensioni maggiori, W è asintoticamente normale sotto H0: (nessuna differenza nelle popolazioni), quindi questo è anche un altro modo per risolvere parte del problema).L'uso della simulazione però mi ha permesso di esaminare il potere anche sotto diverse ipotesi alternative, il che ha reso la mia analisi più completa.

  

Ri: Guida JSL: come creare tutte le permutazioni di un vettore o di un elenco

Seconda metà della tua domanda, come fare non memorizzare l'intera lista?

 

Ottima domanda; Credo che l'unica risposta offerta da JMP sia quella di far sì che il tuo codice venga chiamato da dove la soluzione di JIM esegue un print() o la mia soluzione esegue un write(). Se JMP offrisse un generatore o co-routine @XanGregg , potresti avere una soluzione più flessibile in cui il tuo codice potrebbe chiedere al generatore la sequenza successiva dal punto (o dai punti) in cui ne hai bisogno. Elencarli in una tabella in anticipo potrebbe essere la scelta migliore se ne hai bisogno.

 

Sei libero di condividere maggiori dettagli sul progetto? Il tempo necessario per guardarli tutti e 14! o 15! le permutazioni sono probabilmente proibitive. Se ti aspetti di trovare una risposta sufficientemente buona prima di esaminare tutte le permutazioni, forse utilizzare permutazioni casuali, magari con un algoritmo di ricottura, potrebbe essere una scelta migliore.

Ri: Guida JSL: come creare tutte le permutazioni di un vettore o di un elenco

// 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]

 

grazie per avermi fatto rivisitare la versione di wikipedia! L'ultima volta ho appena trovato una variante diversa che era più facile da convertire.

Ri: Guida JSL: come creare tutte le permutazioni di un vettore o di un elenco

Ho convertito la forma non ricorsiva del codice in JMP.Vedi se questo aiuta

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