In-Place-Algorithmus zur Verschachtelung eines Arrays

Question

Sie erhalten eine Reihe von $ 2n $ Elements

$$ a_1, a_2, dots, a_n, b_1, b_2, dots b_n $$

Die Aufgabe besteht darin, das Array mit einem In-Place-Algorithmus zu verschärfen, so dass das resultierende Array aussieht wie

$$ b_1, a_1, b_2, a_2, dots, b_n, a_n $$

Wenn die Anforderung an der Stelle nicht vorhanden wäre, könnten wir problemlos ein neues Array und Kopieren von Elementen erstellen, die einen $ mathcal {o} (n) $ Time-Algorithmus geben.

Mit der Ein- und Platz-Anforderung stoßen ein Klassif- und Erobereralgorithmus den Algorithmus auf $ theta (n log n) $.

Die Frage ist also:

Gibt es einen $ mathcal {o} (n) $ Time-Algorithmus, der auch an Ort ist?

(Hinweis: Sie können das einheitliche Kostwort-RAM-Modell annehmen, sodass In-Place $ mathcal {o} (1) $ Space Restriction übersetzt).

Answer 1

Hier ist die Antwort, die den Algorithmus aus dem von Joe verknüpften Papier ausübt: http://arxiv.org/abs/0805.1598

Lassen Sie uns zunächst a betrachten $ Theta (n log n) $ Algorithmus, der Kluft und Eroberung verwendet.

1) Teilen und erobern

Wir werden gegeben

$$ a_1, a_2, dots, b_1, b_2, dots b_n $$

Nun zur Verwendung von Kluft und Eroberung für einige $ m = theta (n) $, Wir versuchen, das Array zu bekommen

$$ [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] $$

und wiederholen.

Beachten Sie, dass der Teil $$ B_1, B_2, Punkte B_M, A_ {m+1}, dots a_n $$ ist eine zyklische Verschiebung von

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

durch $ m $ setzt.

Dies ist ein Klassiker und kann durch drei Umkehrungen und in ein Ort erfolgen $ mathcal {o} (n) $ Zeit.

So gibt die Kluft und Eroberung Ihnen a $ Theta (n log n) $ Algorithmus mit einer ähnlichen Rekursion wie $ T (n) = 2T (n/2) + theta (n) $.

2) Permutationszyklen

Ein weiterer Ansatz für das Problem ist die Betrachtung der Permutation als eine Reihe von Disjoint -Zyklen.

Die Permutation wird gegeben (unter der Annahme, beginnend bei $1$)

$$ J MAPSTO 2J MOD 2N+1 $$

Wenn wir irgendwie genau wussten, was die Zyklen waren, konnten wir die Permutation nutzen, indem wir ein Element auswählen $ A $, Bestimmen Sie, wohin dieses Element führt (unter Verwendung der obigen Formel), das Element in den Zielort in den temporären Raum setzen, das Element einlegen $ A $ in diesen Zielort und weiter entlang des Zyklus. Sobald wir mit einem Zyklus fertig sind, gehen wir zu einem Element des nächsten Zyklus und folgen diesem Zyklus und so weiter.

Dies würde uns eine geben $ mathcal {o} (n) $ Zeitalgorithmus, aber es wird davon ausgegangen $ mathcal {o} (1) $ Die Raumbeschränkung macht dieses Problem schwierig.

Hier verwendet das Papier die Zahlentheorie.

Es kann gezeigt werden, dass in dem Fall wann $ 2n + 1 = 3^k $, die Elemente an Positionen $1$, $ 3, 3^2, Punkte, 3^{k-1} $ sind in verschiedenen Zyklen und jeder Zyklus enthält ein Element an der Position $ 3^m, m ge 0 $.

Dies verwendet die Tatsache, dass $2$ ist ein Generator von $ ( mathbb {z}/3^k)^*$.

Also wann $ 2n+1 = 3^k $, der Follow the Cycle -Ansatz gibt uns eine $ mathcal {o} (n) $ Zeitalgorithmus wie für jeden Zyklus wissen wir genau, wo wir beginnen sollen: Kräfte von $3$ (einschließlich $1$) (Diese können in berechnet werden $ mathcal {o} (1) $ Platz).

3) Endalgorithmus

Jetzt kombinieren wir die oben genannten zwei: Division und Eroberer + Permutationszyklen.

Wir teilen uns eine Kluft und erobern, aber wählen Sie $ m $ so dass $ 2m+1 $ ist eine Kraft von $3$ und $ m = theta (n) $.

Auf beide "Hälften" wird stattdessen nur eins wiederholt und tun $ Theta (n) $ Extra Arbeit.

Dies gibt uns das Wiederauftreten $ T (n) = t (cn) + theta (n) $ (für einige $ 0 lt c lt 1 $) und gibt uns so eine $ mathcal {o} (n) $ Zeit, $ mathcal {o} (1) $ Weltraumalgorithmus!

Answer 2

Ich bin mir ziemlich sicher, dass ich einen Algorithmus gefunden habe, der sich nicht auf die Zahlentheorie oder die Zyklus -Theorie beruht. Beachten Sie, dass es einige Details zum Ausarbeiten gibt (möglicherweise morgen), aber ich bin ziemlich zuversichtlich, dass sie trainieren werden. Ich handwelle, wie ich schlafen soll, nicht weil ich versuche, Probleme zu verbergen :)

Lassen A Sei das erste Array, B der Zweite, |A| = |B| = N und annehmen N=2^k für einige k, zur Einfachheit. Lassen A[i..j] die Subtarray von sein A mit Indizes i durch zu j, inklusive. Arrays sind 0 basiert. Lassen RightmostBitPos(i) Geben Sie die (0-basierte) Position des rechts rechtlichen Bits zurück, das '1' von ist i, von rechts zählen. Der Algorithmus funktioniert wie folgt.

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);
    }
}

Nehmen wir eine Reihe von 16 Zahlen und beginnen wir einfach mit Swaps zu verschieben und sehen, was passiert:

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

Von besonderem Interesse ist der erste Teil des zweiten Arrays:

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

Das Muster sollte klar sein: Wir fügen abwechselnd eine Zahl zum Ende hinzu und ersetzen die niedrigste Zahl durch eine hohe Zahl. Beachten Sie, dass wir immer eine Zahl hinzufügen, die eine höher ist als die höchste Zahl, die wir bereits haben. Wenn wir irgendwie genau herausfinden konnten, welche Zahl zu einem bestimmten Zeitpunkt am niedrigsten ist, können wir das leicht tun.

Jetzt entscheiden wir uns für größere Beispiele, um zu sehen, ob wir ein Muster sehen können. Beachten Sie, dass wir die Größe des Arrays nicht reparieren müssen, um das obige Beispiel zu konstruieren. Irgendwann erhalten wir diese Konfiguration (die zweite Zeile subtrahiert 16 von jeder Zahl):

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

Dies zeigt eindeutig ein Muster: "1 3 5 7 9 11 13 15" sind alle 2 voneinander entfernt, "2 6 10 14" sind alle 4 voneinander entfernt und "4 12" sind 8 voneinander entfernt. Wir können daher einen Algorithmus entwickeln, der uns sagt, wie die nächst kleinste Zahl sein wird: Der Mechanismus ist so ziemlich genau, wie binäre Zahlen funktionieren. Sie haben die letzte Hälfte des Arrays ein wenig, ein bisschen für das zweite Quartal und so weiter.

Wenn wir daher genügend Platz für die Speicherung dieser Bits erlaubt haben (wir benötigen $ log n $ bit, aber unser Computermodell erlaubt dies - ein Zeiger auf das Array benötigt auch $ log n $ Bits), können wir herausfinden, welche Nummer zu der Nummer ist tauschen Sie $ o (1) $ time ab.

Wir können daher die erste Hälfte des Arrays in seinen verschachtelten Zustand in $ O (n) $ Time und $ O (n) $ SWAPs bringen. Wir müssen jedoch die zweite Hälfte unseres Arrays reparieren, was alles durcheinander erscheint ("8 6 5 7 13 14 15 16").

Wenn wir nun die erste Hälfte dieses zweiten Teils "sortieren" können, haben wir "5 6 7 8 13 14 15 16" und wird rekursiv verschoben, wenn diese Hälfte den Trick machen: Wir verschieben das Array in $ o (n) ) $ time ($ o ( log n) $ rekursive Anrufe, von denen jeweils die Eingangsgröße halbiert). Beachten Sie, dass wir keinen Stapel benötigen, da diese Anrufe schwanzrekursiv sind, sodass unsere Raumnutzung $ O (1) $ bleibt.

Die Frage ist nun: Gibt es ein Muster in dem Teil, das wir sortieren müssen? Versuchen Sie 32 Zahlen "16 12 10 14 9 11 13 15", um sich zu reparieren. Beachten Sie, dass wir hier genau das gleiche Muster haben! "9 11 13 15", "10 14" und "12" sind auf die gleiche Weise zusammengefasst, die wir zuvor gesehen haben.

Der Trick besteht nun darin, diese Unterabschnitte rekursiv zu verschärfen. Wir schicken "16" und "12" bis "12 16". Wir schicken "12 16" und "10 14" bis "10 12 14 16". Wir schicken "10 12 14 16" und "9 11 13 15" bis "9 10 11 12 13 14 15 16". Dies sorgt den ersten Teil.

Genau wie oben betragen die Gesamtkosten für diesen Vorgang $ O (n) $. Wenn wir all dies hinzufügen, können wir immer noch eine Gesamtlaufzeit von $ O (n) $ erhalten.

Ein Beispiel:

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

Hier finden Sie einen nicht rekursiven In-Place im linearen Zeitalgorithmus, um zwei Hälften eines Arrays ohne zusätzlichen Speicher zu verschärfen.

Die allgemeine Idee ist einfach: Gehen Sie durch die erste Hälfte des Arrays von links nach rechts und tauschen Sie die richtigen Werte ein. Wenn Sie voranschreiten, werden die noch nicht verwendeten linken Werte in den von den richtigen Werten geräumten Raum ausgetauscht. Der einzige Trick besteht darin, herauszufinden, wie man sie wieder herausholt.

Wir beginnen mit einer Reihe von Größe N, die in 2 fast gleiche Hälften geteilt wird.
[ left_items | right_items ]
Während wir es verarbeiten, wird es
[ placed_items | remaining_left_items| swapped_left_items | remaining_right_items]

Der Swap -Raum wächst mit dem folgenden Muster: a) Wachsen Sie den Raum, indem Sie den angrenzenden rechten Gegenstand entfernen und einen neuen Gegenstand von links austauschen. B) Tauschen Sie den ältesten Artikel mit einem neuen Gegenstand von links aus. Wenn die linken Elemente nummeriert sind 1..N, sieht dieses Muster aus

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
...

Die Reihenfolge, die sich der Index geändert hat, ist genau Oeis A025480, die mit einem einfachen Prozess berechnet werden können. Auf diese Weise kann der Swap -Standort nur die Anzahl der bisher hinzugefügten Elemente angegeben werden, was auch der Index des aktuellen Elements ist.

Das sind alle Informationen, die wir benötigen, um die 1. Hälfte der Sequenz in der linearen Zeit zu bevölkern.

Wenn wir in den Mittelpunkt kommen, hat das Array drei Teile:[ placed_items | swapped_left_items | remaining_right_items]Wenn wir die ausgetauschten Gegenstände entschlüsseln können, haben wir das Problem auf die Hälfte der Größe reduziert und können uns wiederholen.

Um den Swap -Raum zu entschlüsseln, verwenden wir die folgende Eigenschaft: eine Sequenz, die von erstellt wurde von N Wechselnde Append und Swap_oldest -Operationen werden enthalten N/2 Gegenstände, in denen ihr Alter gegeben wird von A025480(N/2)..A025480(N-1). (Integer Division, kleinere Werte sind älter).

Wenn die linke Hälfte beispielsweise die Werte 1..19 enthielt, würde der Tauschraum enthalten [16, 12, 10, 14, 18, 11, 13, 15, 17, 19]. A025480 (9..18) ist [2, 5, 1, 6, 3, 7, 0, 8, 4, 9], das ist genau die Liste der Indizes der Elemente vom ältesten zum neuesten.

So können wir unseren Tauschraum entschlüsseln, indem wir durchschreiten und austauschen S[i] mit S[ A(N/2 + i)]. Dies ist auch eine lineare Zeit.

Die verbleibende Komplikation ist, dass Sie irgendwann eine Position erreichen, in der der richtige Wert in einem niedrigeren Index sein sollte, aber bereits ausgetauscht wurde. Es ist leicht, den neuen Standort zu finden: Führen Sie einfach die Indexberechnung durch, um festzustellen, wohin das Element ausgetauscht wurde. Es kann erforderlich sein, der Kette ein paar Schritte zu befolgen, bis Sie einen ungewöhnten Standort finden.

Zu diesem Zeitpunkt haben wir die Hälfte des Arrays verschmolzen und die Reihenfolge der unmützten Teile in der anderen Hälfte mit genau beibehalten N/2 + N/4 Swaps. Wir können den Rest des Arrays für insgesamt insgesamt fortsetzen N + N/4 + N/8 + .... Swaps, was streng geringer ist als 3N/2.

Wie berechnet man A025480:
Dies ist in Oeis als definiert als a(2n) = n, a(2n+1) = a(n). Eine alternative Formulierung ista(n) = isEven(n)? n/2 : a((n-1)/2). Dies führt zu einem einfachen Algorithmus unter Verwendung bitialer Operationen:

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

Dies ist eine amortisierte O (1) -Operation über alle möglichen Werte für N. (1/2 benötigen 1 Schicht, 1/4 benötigen 2, 1/8 3, ...). Es gibt eine noch schnellere Methode, bei der eine kleine Nachschlagtabelle verwendet wird, um die Position des am wenigsten signifikanten Nullbits zu finden.

Angesichts dessen ist hier eine Implementierung in 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;
  }
}

Dies sollte ein ziemlich cache-freundlicher Algorithmus sein, da 2 der 3 Datenorte nacheinander zugegriffen werden und die Menge der verarbeiteten Daten streng abnimmt. Diese Methode kann von einem abgebaut werden Outschellen zu einer In-Shuffle durch Negation der is_even Testen Sie zu Beginn der Schleife.