algorithme en place pour imbriquer un tableau

Question

On vous donne un tableau de $ 2n éléments de $

$$ a_1, a_2, \ dots, a_n, b_1, B_2, \ dots b_n $$

La tâche consiste à entrelacer le tableau, en utilisant un algorithme en place de telle sorte que les regards du tableau résultant comme

$$ b_1, a_1, B_2, a_2, \ dots, b_n, a_n $$

Si l'exigence en place était pas là, on pourrait facilement créer un nouveau tableau et copier des éléments donnant un $ \ mathcal {O} (n) $ algorithme de temps.

Avec l'exigence en place, une fracture et de l'algorithme Conquer cogne l'algorithme à $ \ theta (n \ log n) $.

La question est:

  

Y at-il un $ \ mathcal {O} (n) $ algorithme de temps, ce qui est en place?

. (Remarque: vous pouvez assumer le coût uniforme modèle RAM WORD, donc en place se traduit par $ \ mathcal {O} (1) $ restriction de l'espace)

Answer 1

Voici la réponse qui élabore sur l'algorithme du papier lié par Joe: http://arxiv.org /abs/0805.1598

Tout d'abord, considérons une $ \ theta (n \ log n) $ algorithme qui utilise diviser pour mieux régner.

1) Diviser pour régner

On nous donne

$$ a_1, a_2, \ dots, b_1, B_2, \ dots b_n $$

à utiliser diviser pour mieux régner, pour une $ m = \ Theta (n) $ , nous essayons d'obtenir le tableau

$$ [a_1, a_2, \ dots, a_m, b_1, B_2, \ dots, b_m], [a_ {m + 1}, \ dots, a_n, b_ { m + 1}, \ dots b_n] $$

et récursion.

Notez que la partie $$ b_1, B_2, \ dots b_m, a_ {m + 1}, \ dots a_n $$ est un décalage cyclique de

$$ a_ {m + 1}, \ dots a_n, b_1, \ dots b_m $$

par $ m $ endroits.

Ceci est un classique et peut être fait en place par trois reprises et $ \ mathcal {O} (n) $ temps.

Ainsi, la diviser et conquérir vous donne une $ \ theta (n \ log n) $ algorithme, avec une récursion similaire à $ 1 $ )

$$ j \ mapsto 2j \ mod 2n + 1 $$

Si nous savions en quelque sorte exactement ce que les cycles étaient, en utilisant un espace supplémentaire constant, on peut réaliser la permutation en choisissant un élément $ A $ , déterminer où cet élément va (en utilisant la formule ci-dessus), placer l'élément dans l'emplacement cible dans l'espace temporaire, mettre l'élément $ A $ dans cet emplacement cible et continuer le long du cycle. Une fois que nous avons fini avec un cycle que nous passons sur un élément du cycle suivant et de suivre ce cycle et ainsi de suite.

Cela nous donnerait une $ \ mathcal {O} (n) $ algorithme de temps, mais il suppose que nous "en quelque sorte savait ce que les cycles exacts étaient" et en essayant de faire la comptabilité dans le $ \ mathcal {O} (1) $ limitation de l'espace est ce qui rend difficile ce problème.

est où le papier utilise la théorie des nombres.

On peut montrer que, dans le cas où $ 2n + 1 = 3 ^ k $ , les éléments à des positions $ 1 $ , 3 $, 3 ^ 2, \ dots, 3 ^ {k-1} $ sont dans différents cycles et chaque cycle contient un élément à la position $ trois ^ m, m \ ge 0 $ .

Cette méthode utilise le fait que $ 2 $ est un générateur de $ (\ mathbb {Z} / 3 ^ k) ^ * $ .

Ainsi, lorsque $ 2n + 1 = 3 ^ k $ , le suivi de l'approche du cycle nous donne une $ \ mathcal {O} (n) $ algorithme de temps, comme pour chaque cycle, nous savons exactement où commencer: les pouvoirs de $ $ 3 (y compris $ 1 $ ) (celles-ci peuvent être calculés dans $ \ mathcal {O} (1) $ espace).

3) l'algorithme final

Maintenant, nous combinons les deux ci-dessus: Divide and Conquer + Cycles Permutation

.

Nous faisons diviser pour mieux régner, mais chercher $ m $ pour que 2 M $ + 1 $ est une puissance de $ $ 3 et $ m = \ Theta (n) $ .

instEad sur récursion sur les deux "moitiés", nous RECURSE sur un seul et faire $ \ theta (n) $ travail supplémentaire.

Cela nous donne la récurrence $ T (n) = T (cn) + \ Theta (n) $ (pour une $ 0 \ lt c \ lt $ 1 ) et nous donne ainsi une $ \ mathcal {O} (n) $ temps, $ \ mathcal {O} (1) $ algorithme de l'espace!

Answer 2

Je suis assez sûr que je l'ai trouvé un algorithme qui ne repose pas sur la théorie des nombres ou la théorie du cycle. Notez qu'il ya quelques détails à régler (peut-être demain), mais je suis tout à fait confiant qu'ils élaboreront. Je handwave que je suis censé dormir, pas parce que je suis en train de problèmes cacher:)

Soit A soyez le premier tableau, B le second, |A| = |B| = N et supposons N=2^k pour certains k, pour simplifier. Que A[i..j] soit la sous-tableau de A avec des indices i jusqu'à j inclusivement. Les tableaux sont 0-basés. Laisser revenir la position RightmostBitPos(i) (0-based) du bit le plus à droite qui est « 1 » de i, partant de la droite. L'algorithme fonctionne comme suit.

GetIndex(i) {
    int rightPos = RightmostBitPos(i) + 1;
    return i >> rightPos;
}

Interleave(A, B, N) {
    if (n == 1) {
        swap(a[0], b[0]);
    }
    else {
        for (i = 0; i < N; i++)
            swap(A[i], B[GetIndex(i+1)]);

        for (i = 1; i <= N/2; i*=2)
            Interleave(B[0..i/2-1], B[i/2..i-1], i/2);

        Interleave(B[0..N/2], B[N/2+1..N], n/2);
    }
}

Prenons un tableau de 16 numéros, et nous allons commencer juste les entrelacer des swaps, et voir ce qui se passe:

1 2 3 4 5 6 7 8    | 9 10 11 12 13 14 15 16
9 2 3 4 5 6 7 8    | 1 10 11 12 13 14 15 16
9 1 3 4 5 6 7 8    | 2 10 11 12 13 14 15 16
9 1 10 4 5 6 7 8   | 2 3 11 12 13 14 15 16
9 1 10 2 5 6 7 8   | 4 3 11 12 13 14 15 16
9 1 10 2 11 6 7 8  | 4 3 5 12 13 14 15 16
9 1 10 2 11 3 7 8  | 4 6 5 12 13 14 15 16
9 1 10 2 11 3 12 8 | 4 6 5 7 13 14 15 16
9 1 10 2 11 3 12 4 | 8 6 5 7 13 14 15 16

D'un intérêt particulier est la première partie du second réseau:

|
| 1
| 2
| 2 3
| 4 3
| 4 3 5
| 4 6 5
| 4 6 5 7
| 8 6 5 7

Le modèle doit être clair: nous ajoutons alternativement un numéro à la fin et remplaçons le nombre le plus bas par un grand nombre. Notez que nous ajoutons toujours un nombre qui est un plus élevé que le nombre le plus élevé que nous avons déjà. Si nous étions en quelque sorte en mesure de déterminer exactement quel numéro est le plus bas à un moment donné, nous pouvons le faire facilement.

Maintenant, nous allons pour les plus grands exemples pour voir si nous pouvons voir un modèle. Notez que nous ne avons pas besoin de fixer la taille du tableau pour construire l'exemple ci-dessus. À un certain moment, nous obtenons cette configuration (la deuxième ligne de 16 soustraient de chaque numéro):

16 24 20 28 18 22 26 30 17 19 21 23 25 27 29 31
0   8  4 12  2  6 10 14  1  3  5  7  9 11 13 15

Maintenant, ce qui montre clairement un motif: "1 3 5 7 9 11 13 15" sont tous deux à part, "2 6 10 14" 4 sont tous en dehors et "4 12" sont 8 à part. On peut donc concevoir un algorithme qui nous dit ce que le prochain numéro le plus petit sera: le mécanisme est à peu près exactement comment les nombres binaires fonctionnent. Vous avez un peu pour la dernière moitié du tableau, un peu pour le deuxième trimestre, et ainsi de suite.

Si nous sommes donc assez d'espace a permis de stocker ces bits (nous avons besoin $ \ log n bits de poids $, mais notre modèle de calcul le permet - un pointeur dans le tableau a également besoin $ \ log n bits de $), nous pouvons comprendre dont le nombre d'échange de O $ (1) $ temps amorti.

On peut donc obtenir la première moitié du tableau dans son état entrelacée dans O $ (n) $ temps et $ O (n) $ swaps. Cependant, nous devons fixer la deuxième moitié de notre tableau, qui semble tout foiré ( « 8 6 5 7 13 14 15 16 »).

Maintenant, si l'on peut « sorte » la première moitié de cette deuxième partie, nous nous retrouvons avec « 5 6 7 8 13 14 15 16 », et entrelacer récursive cette moitié fera l'affaire: nous entrelacer le tableau en $ O (n) $ temps ($ O (\ log n) $ appels récursifs chacun réduire de moitié la taille d'entrée). Notez que nous ne avons pas besoin d'une pile que ces appels sont récursives la queue, donc notre utilisation de l'espace reste O $ (1) $.

Maintenant, la question est: est-il un modèle dans la partie que nous devons trier? Essayer 32 chiffres nous donne "16 12 10 14 9 11 13 15" pour réparer. Notez que nous avons ici le même schéma exact! "9 11 13 15", "10 14" et "12" sont regroupés de la même façon, nous avons vu précédemment.

Maintenant, l'astuce consiste à récursive entrelacer ces sous-parties. Nous entrelacer "16" et "12" à "12 16". Nous entrelacer "12 16" et "10 14" à "10 12 14 16". Nous Interleave "10 12 14 16" et "9 11 13 15" à "9 10 11 12 13 14 15 16". Ce trie la première partie.

Tout comme ci-dessus, le coût total de cette opération est O $ (n) $. Ajout de tous ces haut, nous parvenons toujours à obtenir un temps de fonctionnement total de $ O (n) $.

Exemple Un:

Interleave the first half:
1 2 3 4 5 6 7 8    | 9 10 11 12 13 14 15 16
9 2 3 4 5 6 7 8    | 1 10 11 12 13 14 15 16
9 1 3 4 5 6 7 8    | 2 10 11 12 13 14 15 16
9 1 10 4 5 6 7 8   | 2 3 11 12 13 14 15 16
9 1 10 2 5 6 7 8   | 4 3 11 12 13 14 15 16
9 1 10 2 11 6 7 8  | 4 3 5 12 13 14 15 16
9 1 10 2 11 3 7 8  | 4 6 5 12 13 14 15 16
9 1 10 2 11 3 12 8 | 4 6 5 7 13 14 15 16
9 1 10 2 11 3 12 4 | 8 6 5 7 13 14 15 16
Sort out the first part of the second array (recursion not explicit):
8 6 5 7 13 14 15 16
6 8 5 7 13 14 15 16
5 8 6 7 13 14 15 16
5 6 8 7 13 14 15 16
5 6 7 8 13 14 15 16
Interleave again:
5 6 7 8   | 13 14 15 16
13 6 7 8  | 5 14 15 16
13 5 7 8  | 6 14 15 16
13 5 14 8 | 6 7 15 16
13 5 14 6 | 8 7 15 16
Sort out the first part of the second array:
8 7 15 16
7 8 15 16
Interleave again:
7 8 | 15 16
15 8 | 7 16
15 7 | 8 16
Interleave again:
8 16
16 8
Merge all the above:
9 1 10 2 11 3 12 4 | 13 5 14 6 | 15 7 | 16 8

Answer 3

Voici une en place non récurrent dans l'algorithme de temps linéaire pour entrelacer deux moitiés d'un tableau sans stockage supplémentaire.

L'idée générale est simple: Promenade à travers la première moitié du tableau de gauche à droite, en échangeant les valeurs correctes en place. Comme vous avancez, les encore à utiliser des valeurs de gauche se permutés dans l'espace laissé vacant par les bonnes valeurs. La seule astuce est de déterminer comment les retirer à nouveau.

Nous commençons par un tableau de taille N divisé en 2 moitiés presque égales.
  [ left_items | right_items ]
Comme nous, il devient transformons
[ placed_items | remaining_left_items| swapped_left_items | remaining_right_items]

L'espace d'échange augmente avec le schéma suivant: A) la croissance de l'espace en retirant l'élément adjacent droit et la permutation dans un nouvel élément de la gauche; B) échanger élément le plus ancien avec un nouvel élément de la gauche. Si les éléments sont numérotés de gauche 1..N, cette apparence de motif comme

step swapspace index changed
1    A: 1         0
2    B: 2         0
3    A: 2 3       1
4    B: 4 3       0     
5    A: 4 3 5     2
6    B: 4 6 5     1
7    A: 4 6 5 7   3
...

La séquence dont l'indice changé est exactement OEIS A025480 , qui peut être calculé avec un processus simple. Cela permet à ce qui est également placé l'index de l'élément courant de l'emplacement de swap à trouver donné que le nombre d'éléments ajoutés à ce jour,.

C'est toutes les informations dont nous avons besoin pour remplir la 1ère moitié de la séquence dans le temps linéaire.

Quand nous arrivons à mi-parcours, le tableau aura trois parties: [ placed_items | swapped_left_items | remaining_right_items] Si nous pouvons déchiffrer les éléments échangés, nous avons réduit le problème à la moitié de la taille, et peut répéter.

Pour déchiffrer l'espace d'échange, nous utilisons la propriété suivante: Une séquence construite par N append alternatif et les opérations swap_oldest contiendra des éléments de N/2 où les âges sont donnés par A025480(N/2)..A025480(N-1). (division entière, des valeurs plus petites sont plus).

Par exemple, si la moitié gauche tenait à l'origine des valeurs 1..19, l'espace d'échange contiendrait [16, 12, 10, 14, 18, 11, 13, 15, 17, 19]. A025480 (9..18) est [2, 5, 1, 6, 3, 7, 0, 8, 4, 9], ce qui est exactement la liste des index des articles du plus ancien au plus récent.

Nous pouvons donc notre espace unscramble d'échange en avançant à travers elle et échange S[i] avec S[ A(N/2 + i)]. Ceci est également le temps linéaire.

La complication restante est que finalement vous arriverez à une position où la valeur correcte doit être à un indice inférieur, mais il a déjà été permutées. Il est facile de trouver le nouvel emplacement: il suffit de faire à nouveau le calcul de l'indice pour découvrir où l'élément a été échangé à. Il peut être nécessaire de suivre la chaîne quelques étapes jusqu'à ce que vous trouviez un emplacement unswapped.

À ce stade, nous avons fusionné la moitié du tableau, et maintenu l'ordre des parties non fusionnées dans l'autre moitié, avec des swaps exactement N/2 + N/4. Nous pouvons continuer à travers le reste du tableau pour un total de swaps de N + N/4 + N/8 + .... qui est strictement inférieur à 3N/2.

Comment calculer A025480:   Ceci est défini comme dans OEIS a(2n) = n, a(2n+1) = a(n). Une autre formulation isa(n) = isEven(n)? n/2 : a((n-1)/2). Cela conduit à un algorithme simple en utilisant des opérations de manipulation de bits:

index_t a025480(index_t n){
    while (n&1) n=n>>1;
    return n>>1;  
}

Ceci est une opération O (1) amorti sur toutes les valeurs possibles pour N. (1/2 besoin de 1 quart de travail, 1/4 besoin de 2, 1/8 ont besoin de 3, ...) . Il existe une méthode encore plus rapide qui utilise une petite table de recherche pour trouver la position du bit de zéro significatif.

Étant donné que, voici une implémentation en C:

static inline index_t larger_half(index_t sz) {return sz - (sz / 2); }
static inline bool is_even(index_t i) { return ((i & 1) ^ 1); }

index_t unshuffle_item(index_t j, index_t sz)
{
  index_t i = j;
  do {
    i = a025480(sz / 2 + i);
  }
  while (i < j);
  return i;
}

void interleave(value_t a[], index_t n_items)
{
  index_t i = 0;
  index_t midpt = larger_half(n_items);
  while (i < n_items - 1) {

    //for out-shuffle, the left item is at an even index
    if (is_even(i)) { i++; }
    index_t base = i;

    //emplace left half.
    for (; i < midpt; i++) {
      index_t j = a025480(i - base);
      SWAP(a + i, a + midpt + j);
    }

    //unscramble swapped items
    index_t swap_ct  = larger_half(i - base);
    for (index_t j = 0; j + 1 < swap_ct ; j++) {
      index_t k = unshuffle_item(j, i - base);
      if (j != k) {
        SWAP(a + midpt + j, a + midpt + k);
      }
    }
    midpt += swap_ct;
  }
}

Cela devrait être un algorithme assez convivial cache, puisque 2 des 3 emplacements de données sont accessibles de façon séquentielle et en cours de traitement la quantité de données est strictement décroissante. Cette méthode peut être activée à partir d'un hors lecture aléatoire à un remaniement en annulant par le test de is_even au début de la boucle.