apexsquirt

[FR] perm.h -- manipuler des permutations !

Sep 19th, 2020 (edited)
1,131
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Permutation {
  2.    
  3.     public:
  4.     Permutation id(int m);
  5.     void apres(Permutation s);
  6.     void montrer ();
  7.     Permutation array2perm(int arr[], int m);
  8.     void inverse(Permutation & perm);
  9.     Permutation tau (int arr[], int m);
  10.     int signature();
  11.     void mappedFrom(int arr[]);
  12.     // oui je sais c'est écrit en anglais bla bla bla c'est pas grave on l'utilise quasi pas
  13.  
  14.     private:
  15.     int de[50];
  16.     int n;
  17.    
  18. };
  19. Permutation Permutation::id(int m) {
  20.     n = m;
  21.     de[0] = 0;
  22.     for (int i = 1; i <= n; i++)
  23.         de[i] = i;
  24. }
  25. void Permutation::montrer() {
  26.     printf("(%i",de[1]);
  27.     for (int i = 2; i <= n; i++)
  28.         printf(" %i",de[i]);
  29.     printf(")");
  30. }
  31. void Permutation::apres(Permutation s) {
  32.     n = s.n;
  33.     int deRet[n];
  34.     for (int i = 1; i <= n; i++)
  35.         deRet[i] = de[s.de[i]];
  36.     for (int i = 1; i <= n; i++)
  37.         de[i] = deRet[i];
  38. }
  39. Permutation operator * (Permutation a, Permutation b) {
  40.     a.apres(b);
  41.     return a;
  42. }
  43. Permutation Permutation::array2perm(int arr[], int m) {
  44.     n = m;
  45.     for (int i = 1; i <= n; i++)
  46.         de[i] = arr[i-1];
  47. }
  48. void Permutation::mappedFrom(int arr[]) {
  49.     for (int i = 1; i <= n; i++) {
  50.         arr[de[i]] = i;
  51.     }
  52. }
  53. Permutation Permutation::tau (int arr[], int m) {
  54.     Permutation ret;
  55.     ret.id(m);
  56.     for (int i = 1; i <= m; i++) {
  57.         if (arr[0] == i) ret.de[i] = arr[1];
  58.         else if (arr[1] == i) ret.de[i] = arr[0];
  59.         else ret.de[i] = i;
  60.     }
  61.     return ret;
  62. }
  63. void Permutation::inverse(Permutation & perm) {
  64.    
  65.     perm.n = n;
  66.     for (int i = 1; i <= n; i++)
  67.         perm.de[i] = de[i];
  68.    
  69.     int taus[n+1][2];
  70.    
  71.     Permutation identity;
  72.     int array[n+1];
  73.     Permutation inverse;
  74.    
  75.     identity.id(n);
  76.     inverse.id(n);
  77.    
  78.     Permutation tau;
  79.    
  80.     perm.mappedFrom(array);
  81.     for (int i = 1; i <= n; i++) {
  82.         taus[i][0] = i;
  83.         taus[i][1] = identity.de[array[i]];
  84.         tau = tau.tau(taus[i],n);
  85.         identity = tau * identity;
  86.         inverse = inverse * tau;
  87.     }
  88.    
  89.     perm = inverse;
  90.    
  91. }
  92. int Permutation::signature() {
  93.    
  94.     int epsilon = 1;
  95.    
  96.     Permutation perm;
  97.     perm.n = n;
  98.     for (int i = 1; i <= n; i++)
  99.         perm.de[i] = de[i];
  100.    
  101.     int taus[n+1][2];
  102.    
  103.     Permutation identity;
  104.     int array[n+1];
  105.     Permutation inverse;
  106.    
  107.     identity.id(n);
  108.     inverse.id(n);
  109.    
  110.     Permutation tau;
  111.    
  112.     perm.mappedFrom(array);
  113.     for (int i = 1; i <= n; i++) {
  114.         taus[i][0] = i;
  115.         taus[i][1] = identity.de[array[i]];
  116.         tau = tau.tau(taus[i],n);
  117.         if (i != identity.de[array[i]])
  118.             epsilon *= -1;
  119.         identity = tau * identity;
  120.     }
  121.    
  122.     return epsilon;
  123.    
  124. }
RAW Paste Data