Pergunta
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.
Solução
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.
Outras dicas
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
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ê.
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