permutar i e t [i]

Question

Supondo que eu tenho uma série de T int, Eu estou procurando um algoritmo no local que permutar i e T [i]

I tem: [3 2 0 1] (a)

Eu quero: [2 3 1 0] (b)

por exemplo. em (b) T [0] = 2 uma vez que, em (a) t [2] foi igual a 0.

Eu estava à espera de encontrar um O simples (n) tempo, O (1) algoritmo de espaço, mas não posso encontrá-lo. Alguma idéia?

Nota:

• Há uma matriz sigle (a) é antes de (b) é depois.

• valores na matriz pertencem a [0, N [, nenhuma duplicata.

Answer 1

Para obter a inversão da permutação, você só tem que andar os ciclos da permutação

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;

I usar números maiores do que N para marcar esta é parte de um ciclo que já foi processada.

Answer 2

Você pode ir para ordenação lexicográfica para obter todas as permutações possíveis. Siga o link abaixo para uma lista de permutação algoritmos

Permutations

Answer 3

Parece que você está procurando o inverso no permutação grupo de uma matriz . Seu exemplo de matriz é {0 ? 3, 1 ? 2, 2 ? 0, 3 ? 1}, e você quer {3 ? 0, 2 ? 1, 0 ? 2, 1 ? 3}. Rearranjado, que é {0 ? 2, 1 ? 3, 2 ? 1, 3 ? 0}, ou [2 3 1 0]. Assim, para encontrar o inverso, você só precisa percorrer a matriz original e inverter o mapeamento dos índices. Isso deve funcionar (você pode usar qualquer variedade se você sabe o comprimento):

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

Enquanto t (com comprimento n) é uma permutação de [0 .. n-1], TINV não deve ser indefinido para quaisquer valores. A solução da jpalecek é um pouco mais complicado, então eu não tenho certeza se este é o suficiente abrangente para você.

Answer 4

Esta é minha tentativa para resolver este problema no local sem memória extra. É um O (n) algoritmo.

O algoritmo por jpalecek é bastante inteligente, mas não intuitiva para ler, pelo menos não para mim. Eu tentei sair e ele funciona, mas eu não tive o tempo para entender por que e comentários seria ótimo.

O algoritmo por Gracenotes é ótimo, desde que a matriz não é muito grande. Se os dados é grande, um pode ter que criar a matriz dinamicamente.

A idéia básica no meu algoritmo é atualizar a matriz, seguindo a cadeia de pares de índice e valor. Por exemplo índice de 0 mapas a valor de 3. Ao usar valor 3 como o índice encontra-se o próximo par que é índice 3 na matriz e valor 1. Essencialmente eu salvar o próximo índice e valor par e atualizar o valor do índice e par anterior até que eu sou feito da cadeia.

Se você pode torná-lo mais eficiente, elegante ou melhor no geral, eu estaria interessado.

Eu compilei e testado o código abaixo mas não usou qualquer outra entrada de teste. Deixei na saída de depuração para aqueles que desejam experimentá-lo e entender melhor como ele 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