permuto i y T [i]

Question

Suponiendo que tengo una matriz de int T, Estoy buscando un algoritmo in situ que permute i y T [i]

Tengo: [3 2 0 1] (a)

Quiero: [2 3 1 0] (b)

por ejemplo. en (b) T [0] = 2 porque, en (a) T [2] fue igual a 0.

Esperaba encontrar un tiempo O (n) simple, algoritmo de espacio O (1), pero no puedo encontrarlo. ¿Alguna idea?

Nota:

• Hay una matriz sigle (a) antes de (b) después.

• Los valores de la matriz pertenecen a [0, N [, sin duplicado.

Answer 1

Para obtener la inversión de la permutación, solo tienes que recorrer los ciclos de la permutación

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;

Uso números mayores que N para marcar esto es parte de un ciclo que ya fue procesado.

Answer 2

Puede obtener un orden lexicográfico para obtener todas las permutaciones posibles. Siga el enlace a continuación para obtener una lista de algoritmos de permutación

Permutaciones

Answer 3

Parece que estás buscando lo inverso en el grupo de permutación de una matriz . La matriz de ejemplo es {0 ? 3, 1 ? 2, 2 ? 0, 3 ? 1}, y desea {3 ? 0, 2 ? 1, 0 ? 2, 1 ? 3}. Reorganizado, eso es {0 ? 2, 1 ? 3, 2 ? 1, 3 ? 0}, o [2 3 1 0]. Por lo tanto, para encontrar lo inverso, solo debe recorrer la matriz original y revertir la asignación de índices. Esto debería funcionar (puedes usar cualquier matriz si conoces la longitud):

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

Mientras t (con longitud n) sea una permutación de [0 .. n-1], tinv no debe estar indefinido para ningún valor. La solución de jpalecek es algo más complicada, por lo que no estoy seguro de que esta sea lo suficientemente completa para ti.

Answer 4

Este es mi intento de resolver este problema en el lugar sin memoria adicional. Es un algoritmo O (n).

El algoritmo de jpalecek es bastante inteligente pero no intuitivo de leer, al menos no para mí. Lo probé y funciona, pero no he tenido tiempo de entender por qué y los comentarios serían excelentes.

El algoritmo de Gracenotes es excelente siempre que la matriz no sea demasiado grande. Si los datos son grandes, uno puede tener que crear la matriz dinámicamente.

La idea básica en mi algoritmo es actualizar la matriz siguiendo la cadena de pares de índice y valor. Por ejemplo, el índice 0 se asigna al valor 3. Al usar el valor 3 como el índice, encontrará el siguiente par, que es el índice 3 en la matriz y el valor 1. Esencialmente, guardo el siguiente índice y par de valores y actualizo el índice anterior y el valor del par Hasta que termine la cadena.

Si puede hacerlo más eficiente, elegante o mejor en general, me interesaría.

He compilado y probado el siguiente código, pero no he usado ninguna otra entrada de prueba. He dejado en la salida de depuración para aquellos que desean probarlo y entender mejor cómo funciona.

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