permute i et t [i]

Question

En supposant que j'ai un tableau d'int T, Je cherche un algorithme sur place qui permute i et T [i]

J'ai: [3 2 0 1] (a)

Je veux: [2 3 1 0] (b)

par exemple. dans (b) T [0] = 2 car, dans (a), T [2] était égal à 0.

Je m'attendais à trouver un algorithme simple O (n) time, O (1) space, mais je ne le trouve pas. Des idées?

Remarque:

• Il y a un tableau sigle (a) avant que (b) soit après.

• Les valeurs du tableau appartiennent à [0, N [, pas de doublon.

Answer 1

Pour obtenir l'inversion de la permutation, il vous suffit de parcourir les cycles de la permutation

int i, j, next, prev;
for(int i=0; i<N; i++) {
  if(T[i]>=N) continue;
  j=T[i];
  prev=i;
  while(j < N) {
    next=T[j];
    T[j]=prev+N;
    prev=j;
    j=next;
  }
}
for(int i=0; i<N; i++)
  T[i]-=N;

J'utilise des nombres supérieurs à N pour marquer que cela fait partie d'un cycle déjà traité.

Answer 2

Vous pouvez choisir un ordre lexicographique pour obtenir toutes les permutations possibles. Suivez le lien ci-dessous pour obtenir une liste des algorithmes de permutation

Permutations

Answer 3

Il semble que vous recherchiez l'inverse dans le groupe de permutation d'un tableau . Votre exemple de tableau est {0 ? 3, 1 ? 2, 2 ? 0, 3 ? 1} et vous souhaitez {3 ? 0, 2 ? 1, 0 ? 2, 1 ? 3}. Réarrangé, il s’agit de {0 ? 2, 1 ? 3, 2 ? 1, 3 ? 0} ou [2 3 1 0]. Donc, pour trouver l'inverse, il vous suffit de parcourir le tableau d'origine et d'inverser la cartographie des indices. Cela devrait fonctionner (vous pouvez utiliser n’importe quel tableau si vous connaissez la longueur):

int t[] = { 3, 2, 0, 1};
int tinv[4];
for (int i = 0; i < 4; i++)
    tinv[t[i]] = i;

Aussi longtemps que t (de longueur n) est une permutation de [0 .. n-1], tinv ne doit pas être indéfini pour aucune valeur. La solution de jpalecek est un peu plus compliquée, donc je ne suis pas sûr que celle-ci soit suffisamment complète pour vous.

Answer 4

C’est ma tentative de résoudre ce problème sur place sans mémoire supplémentaire. C'est un algorithme O (n).

L’algorithme de jpalecek est assez intelligent mais sa lecture n’est pas intuitive, du moins pas pour moi. Je l'ai essayé et ça marche mais je n'ai pas eu le temps de comprendre pourquoi et les commentaires seraient géniaux.

L’algorithme de Gracenotes est excellent tant que le tableau n’est pas trop grand. Si les données sont volumineuses, il peut être nécessaire de créer le tableau de manière dynamique.

L’idée de base de mon algorithme est de mettre à jour le tableau en suivant la chaîne de paires d’index et de valeur. Par exemple, l'index 0 correspond à la valeur 3. En utilisant la valeur 3 comme index, vous trouverez la paire suivante, qui est l'index 3 dans le tableau et la valeur 1. Essentiellement, j'enregistre la paire index et valeur suivante et met à jour l'index et la valeur de paire précédents. jusqu'à ce que j'ai terminé la chaîne.

Si vous pouvez le rendre plus efficace, élégant ou meilleur dans l'ensemble, je serais intéressé.

J'ai compilé et testé le code ci-dessous, mais je n'ai utilisé aucune autre entrée de test. J'ai laissé dans la sortie de débogage pour ceux qui souhaitent l'essayer et mieux comprendre comment cela fonctionne.

// Array print routine.
void printArray (const char * str_p,int a[], int n)
{
   printf ("%s\n", str_p);
   for (int i = 0; i < n; i++)
   {
      printf ("%i ", i);
   }
   printf ("\n");
   for (int i = 0; i < n; i++)
   {
      printf ("%i ", a[i]);
   }
   printf ("\n\n");
}

// The main code.
void PermuteTheDamnArray()
{
   printArray ("Initial Array", a,n);

   int i = 0;     // Simply a counter.
   int p_ix = 0;  // Previous Index.
   int p_val = a[0]; // Previous Value.
   int n_ix = a[0];  // Next index.
   int n_val = a[n_ix]; // Next Value.
   for (i = 0; i < n; i++)
   {
      // Replace. 
      printf ("Swapping orig (%i,%i) with (%i,%i)\n", n_ix, n_val,p_val, p_ix);
      a[p_val] = p_ix;

      printArray ("Array after swap", a,n);

      // The next index and value pair becomes the new previous index and value pair.
      p_ix = n_ix;
      p_val = n_val;
      printf ("The previous pair is now: (%i,%i)\n", p_ix, p_val);

      // Get the next index and value pair.
      n_ix = n_val;
      n_val = a[n_val];
      printf ("The next pair is now: (%i,%i)\n", n_ix, n_val);

   }

   printArray ("Final Array", a,n);
}



Output:

Swapping orig (3,1) with (3,0)
Array after swap
0 1 2 3 
3 2 0 0 

The previous pair is now: (3,1)
The next pair is now: (1,2)
Swapping orig (1,2) with (1,3)
Array after swap
0 1 2 3 
3 3 0 0 

The previous pair is now: (1,2)
The next pair is now: (2,0)
Swapping orig (2,0) with (2,1)
Array after swap
0 1 2 3 
3 3 1 0 

The previous pair is now: (2,0)
The next pair is now: (0,3)
Swapping orig (0,3) with (0,2)
Array after swap
0 1 2 3 
2 3 1 0 

The previous pair is now: (0,3)
The next pair is now: (3,0)
Final Array
0 1 2 3 
2 3 1 0