Comment permuter un tableau dans un ordre donné avec O (1) espace auxiliaire?

Question

Comment implémenter la fonction OrderElements suivante?

char chars[] = {'a', 'b', 'c', 'd', 'e'}; 
int want_order[] = {2, 4, 3, 0, 1}; 
int length = 5; 
OrderElements(chars, want_order, length); 

// chars now contains: c, e, d, a, b 

Il est facile lorsque vous pouvez utiliser un espace supplémentaire linéaire, mais peut-il être fait avec seulement un espace supplémentaire constant, à savoir, le tri directement les éléments chars en place?

P.S .: Ce n'était pas une question d'examen; J'ai vraiment besoin de cette fonction.

CLARIFICATION: Il semble y avoir un malentendu sur l'ordre final désiré des éléments. Le tableau résultant dans l'exemple doit comporter les éléments suivants, en se référant au tableau chars d'origine:

{chars[2], chars[4], chars[3], chars[0], chars[1]} 

qui est

{'c', 'e', 'd', 'a', 'b'}. 

Answer 1

à proprement parler, cependant, O(lg length) la mémoire est nécessaire pour représenter l'index de la liste; Je vais ignorer ceci pour cette discussion, cependant, puisque l'utilisation d'un i 64 bits est probablement assez grande pour tout ce que nous pouvons réellement réorganiser.

for (int i = 0; i < length; i++) { 
    int t = want_order[i]; 
    while (t < i) { 
    // t has been moved already; we need to find out where the value that started there 
    // went. Since we must've put it at want_order[t] before, resume looking there 
    t = want_order[t]; 
    // once t >= i, we know we've not touched that slot more than once, and so our 
    // value is there 
    } 
    swap(chars[i], chars[t]); 
} 

Une explication intuitive: Pour chaque élément du tableau, nous avons mis la valeur cible en elle, le stockage de notre ancienne valeur dans la fente qui contenait notre valeur cible. Nous devons prendre soin de traiter le cas où notre valeur d'objectif a été déplacée; ceci est traité en notant qu'un slot donné est seulement échangé jusqu'à deux fois; une fois quand la valeur y est volée par une autre valeur (ce qui n'aurait pas pu arriver, puisque cette itération va faire ça) ou quand la valeur est déplacée pour insérer la valeur finale (ce qui n'arrive qu'aux indices inférieurs).

Une illustration de la façon dont cela ressemble sur vos données échantillon:

i | want_order | chars  | t 
0 | 2 4 3 0 1 | a b c d e | 2 (swap) 
1 | 2 4 3 0 1 | c b a d e | 4 (swap) 
2 | 2 4 3 0 1 | c e d a b | 3 (swap) 
3 | 2 4 3 0 1 | c e d a b | 0 (follow) 
3 | 2 4 3 0 1 | c e d a b | 3 (swap - no-op) 
4 | 2 4 3 0 1 | c e d a b | 1 (follow) 
4 | 2 4 3 0 1 | c e d a b | 4 (swap - no-op) 

Cet algorithme utilise uniquement O(lg n) mémoire (pour les indices), mais je n'ai pas essayé d'analyser pleinement son temps de fonctionnement. Il est évident que c'est au pire O(n^2), mais je pense que ça ira mieux que ça en pratique. Cependant, il n'y a pas de limite réelle sur la longueur des chaînes qu'il pourrait avoir à suivre, donc en principe il peut finir par utiliser O(n^2) temps avec l'entrée du pire cas.

Answer 2

Impossible.

Vous avez besoin d'au moins O (log (list size)) pour connaître l'index de l'élément trié.

Answer 3

Trier Opération avec mémoire O (1) est BubbleSort, mais il a une O performance (n²)

http://en.wikipedia.org/wiki/Bubble_sort

Answer 4

Cela fera le travail dans O(n²). A chaque itération de la boucle externe, l'élément actuellement recherché est échangé vers sa position correcte (première boucle interne), puis l'ordre voulu des éléments restants est ajusté pour refléter la nouvelle situation (deuxième boucle interne).

for (int i = 0; i < length; i++) 
{ 
    for (int j = wantedOrder[i]; j > i; j--) 
    { 
     Swap(chars, j, j - 1); 
    } 

    for (int j = i + 1; j < length; j++) 
    { 
     if (wantedOrder[j] < wantedOrder[i]) 
     { 
      wantedOrder[j]++; 
     } 
    } 
} 

Cela nécessite bien entendu la destruction du tableau d'ordres de recherche. Si cela n'est pas autorisé, je n'ai aucune idée de la façon de résoudre le problème (du moins pour le moment).

Answer 5

Cela peut être fait Si vous êtes autorisé à changer le tableau want_order. L'algorithme est plutôt simple car la permutation peut être décomposée en cycles. Lorsque vous itérez un cycle, marquez chacun d'eux. Et la complexité temporelle est O (N). Pseudo-code:

char chars[]  = {'a', 'b', 'c', 'd', 'e'}; 
int want_order[] = {2, 4, 3, 0, 1}; 
int length  = 5; 

OrderElements(chars, want_order, length) { 
    int i, j, k; 

    for(i = 0; i < length; ++i) { 
    if (want_order[i] == -1) continue; 

    j = startPos = want_order[i]; 
    c = chars[i]; 
    do { 
     swap(c, chars[j]); 
     k = want_order[j]; 
     want_order[j] = -1; 
     j = k 
    } while(j != startPos); 
    } 
} 

Answer 6

Le message ci-dessus contient une erreur (il écrase par inadvertance un index). Voici une version corrigée:

char chars[]  = {'a', 'b', 'c', 'd', 'e'}; 
int want_order[] = {2, 4, 3, 0, 1}; 
int length  = 5; 

OrderElements(chars, want_order, length) { 
    int i, j, k; 

    for(i = 0; i < length; ++i) { 
    if (want_order[i] == -1) continue; 

    j = startPos = want_order[i]; 
    c = chars[i]; 
    do { 
     swap(c, chars[j]); 
     k = want_order[j]; 
     want_order[j] = -1; 
     j = k 
    } while(j != startPos); 
    } 
}