241806_fr-FR

liliconcom

Aide JSL : Comment créer toutes les permutations d'un vecteur ou d'une liste

J'essaie de trouver la meilleure façon d'écrire du JSL pour énumérer toutes les permutations d'un vecteur ou d'une liste.  

 

Un algorithme que j'ai trouvé et qui semble prometteur est Algorithme du tas https://en.wikipedia.org/wiki/Heap%27s_algorithm , mais je n'arrive pas à comprendre comment coder cela.Quelqu'un peut-il m'aider ici ?  

 

Je me rends compte que plus la taille d'un vecteur ou d'une liste est grande, la taille de la sortie augmenterait de manière factorielle (le nombre de permutations de k éléments est k ! ), je suis donc également intéressé par un moyen de générer chaque élément de la liste des permutations et d'effectuer une opération sur cette permutation, puis de la supprimer lorsqu'elle n'est plus nécessaire pour générer la ou les permutations suivantes.  

Re : Aide JSL : Comment créer toutes les permutations d'un vecteur ou d'une liste

Voici une fonction que j'ai créée basée sur le script 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 : Aide JSL : Comment créer toutes les permutations d'un vecteur ou d'une liste

Merci pour le code, vous deux, cela a été utile.La récursivité me fait toujours mal à la tête, et il semble que JSL ne vous permet pas facilement de faire de la récursivité d'une manière qui permet d'attribuer la sortie de la séquence de permutations à une liste ou une matrice.  

 

Après avoir utilisé les fonctions du générateur, j'ai réalisé que ce que je voulais faire prendrait trop de temps de calcul.  

 

Voici le problème : il existe une mesure d’efficacité utilisée pour les vaccins qui peut non pas prévenir mais réduire la gravité d’une maladie appelée fraction atténuée (MF).Il est décrit ici .Il est basé sur la statistique du test Wilcoxson Rank-Sum (W) pour la comparaison de deux groupes.Donc, ce que je voulais faire, c'était lister toutes les valeurs possibles de W (en utilisant toutes les permutations possibles de rangs) pour deux groupes avec des tailles d'échantillon données, puis en tirer toutes les valeurs possibles de MF.Ce que je voulais vraiment montrer, c'est que les critères que nous utilisons pour démontrer l'efficacité de la MF équivalaient à une valeur critique pour la distribution de W sous l'hypothèse nulle que la distribution pour les deux groupes est la même.  

 

La façon dont j'ai résolu mon problème était de supposer une distribution sous-jacente pour chaque groupe et de faire une étude de simulation pour obtenir une distribution de MF selon ces hypothèses.(De plus, pour des échantillons plus grands, W est asymptotiquement normal sous H0 : (pas de différence dans les populations), c'est donc aussi une autre façon de résoudre une partie du problème).L'utilisation de la simulation m'a cependant permis d'examiner également la puissance sous différentes hypothèses alternatives, ce qui a rendu mon analyse plus complète.

  

Re : Aide JSL : Comment créer toutes les permutations d'un vecteur ou d'une liste

2ème moitié de votre question, comment pas stocker toute la liste ?

 

Excellente question ; Je pense que la seule réponse proposée par JMP est de faire en sorte que votre code soit appelé à partir de l'endroit où la solution de JIM effectue un print() ou ma solution effectue un write(). Si JMP proposait un générateur ou des co-routines @XanGregg , vous pourriez avoir une solution plus flexible dans laquelle votre code pourrait demander au générateur la séquence suivante à partir du (ou des) point(s) où vous en avez besoin. Les répertorier dans un tableau à l’avance pourrait être le meilleur choix si vous en avez besoin.

 

Êtes-vous libre de partager plus de détails sur le projet ? Le temps nécessaire pour en regarder les 14 ! ou 15 ! les permutations sont probablement prohibitives. Si vous espérez trouver une réponse suffisamment bonne avant d'examiner toutes les permutations, utiliser des permutations aléatoires, peut-être avec un algorithme de recuit, pourrait être un meilleur choix.

Re : Aide JSL : Comment créer toutes les permutations d'un vecteur ou d'une liste

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

 

merci de m'avoir fait revisiter la version wikipedia ! La dernière fois, j'ai juste trouvé une variante différente, plus facile à convertir.

Re : Aide JSL : Comment créer toutes les permutations d'un vecteur ou d'une liste

J'ai converti la forme non récursive du code en JMP.Voyez si cela aide

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