permute i et T [i]

Question

En supposant que je suis un tableau d'entiers T, Je cherche un en place algorithme qui permute i et T [i]

je: [3 2 0 1 ] (a)

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

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

Je m'attendais à trouver un algorithme de temps O (n) simple, O (1), mais Je ne peux pas le trouver. Des idées ?

Note:

• Il y a un tableau de Sigle (a) est avant (b) est 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 marcher dans 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 les nombres supérieurs à N pour marquer cela fait partie d'un cycle qui a déjà été traité .

Answer 2

Vous pouvez opter pour l'ordre lexicographique pour obtenir toutes les permutations possibles. Suivez le lien ci-dessous pour une liste d'algorithmes de permutation

Permutations

Answer 3

Il semble que vous cherchez l'inverse dans le permutation group d'un tableau. Votre tableau d'exemple est {0 → 3, 1 → 2, 2 → 0, 3 → 1}, et vous voulez {3 → 0, 2 → 1, 0 → 2, 1 → 3}. Réarrangé, c'est {0 → 2, 1 → 3, 2 → 1, 3 → 0} ou [2 3 1 0]. Donc, pour trouver l'inverse, il suffit de parcourir le tableau original et inverser le mappage des indices. Cela devrait fonctionner (vous pouvez utiliser un 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; 

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

Answer 4

Ceci 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 pas intuitif à lire, 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 super.

L'algorithme de Gracenotes est génial tant que le tableau n'est pas trop grand. Si les données sont volumineuses, il se peut que vous deviez créer le tableau dynamiquement.

L'idée de base dans mon algorithme est de mettre à jour le tableau en suivant la chaîne de paires d'index et de valeurs. Par exemple index 0 correspond à 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, je sauvegarde la paire index et valeur suivante et met à jour l'indice précédent 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