Algorytm na miejscu do przeplatania tablicy

Otrzymujesz tablicę elementów$2n$

Zadanie polega na przeplataniu tablicy przy użyciu algorytmu lokalnego, takiego jak tablica wynikowa

Gdyby nie istniał wymóg lokalny, moglibyśmy łatwo utworzyć nową tablicę i skopiować elementy, dając algorytm czasowy .$\mathcal{O}(n)$

Z wymaganiem na miejscu algorytm dzielenia i zdobywania powoduje, że algorytm jest .$\theta(n \log n)$

Pytanie brzmi:

Czy istnieje algorytm czasowy , który również istnieje?$\mathcal{O}(n)$

(Uwaga: możesz założyć model WORD RAM o jednolitym koszcie, więc w miejscu przekłada się na ograniczenie przestrzeni).$\mathcal{O}(1)$

Oto odpowiedź opracowana w oparciu o algorytm z artykułu, do którego link dołączył Joe: http://arxiv.org/abs/0805.1598

Najpierw zastanówmy się nad algorytmem , który wykorzystuje dziel i zwyciężaj.$\Theta(n \log n)$

1) Dziel i rządź

Dano nam

Teraz, aby użyć dzielenia i podbijania, dla niektórych , staramy się uzyskać tablicę$m = \Theta(n)$

i powtórzyć.

Zauważ, że część to cykliczne przesunięcie

przez miejsc.$m$

Jest to klasyk i można tego dokonać na miejscu poprzez trzy cofnięcia w czasie .$\mathcal{O}(n)$

Zatem dziel i rządź daje ci algorytm z rekurencją podobną do .$\Theta(n \log n)$$T(n) = 2T(n/2) + \Theta(n)$

2) Cykle permutacji

Teraz innym podejściem do problemu jest rozważenie permutacji jako zestawu rozłącznych cykli.

Permutacja jest podawana przez (przy założeniu, że od )$1$

Gdybyśmy w jakiś sposób wiedzieli dokładnie, czym są cykle, wykorzystując stałą dodatkową przestrzeń, moglibyśmy zrealizować permutację, wybierając element , określić, dokąd ten element idzie (używając powyższej formuły), umieścić element w docelowej lokalizacji w przestrzeni tymczasowej, umieścić element do tej docelowej lokalizacji i kontynuuj cykl. Gdy skończymy z jednym cyklem, przechodzimy do elementu następnego cyklu i podążamy za nim i tak dalej.$A$$A$

To dałoby nam algorytm czasowy , ale zakłada, że ​​„jakoś wiedzieliśmy, jakie dokładnie są cykle” i staramy się wykonywać tę księgowość w ramach ograniczenia przestrzeni to sprawia, że ​​ten problem jest trudny.$\mathcal{O}(n)$$\mathcal{O}(1)$

W tym miejscu papier wykorzystuje teorię liczb.

Można wykazać, że w przypadku, gdy , elementy w pozycjach , są w różnych cyklach i każdy cykl zawiera element w pozycji .$2n + 1 = 3^k$$1$$3, 3^2, \dots, 3^{k-1}$$3^m, m \ge 0$

Wykorzystuje to fakt, że jest generatorem .$2$$(\mathbb{Z}/3^k)^*$

Tak więc, gdy , podążanie za cyklem daje nam algorytm czasowy , ponieważ dla każdego cyklu wiemy dokładnie, od czego zacząć: potęgi (w tym ) (te można obliczyć w spacji ).$2n+1 = 3^k$$\mathcal{O}(n)$$3$$1$$\mathcal{O}(1)$

3) Ostateczny algorytm

Teraz łączymy dwa powyższe: Divide and Conquer + Permutation Cycles.

Wykonujemy dzielenie i podbijać, ale wybrać tak, jest potęgą i .$m$$2m+1$$3$$m = \Theta(n)$

Dlatego zamiast rekurencji na obu „połówkach”, powtarzamy tylko na jednej i wykonujemy dodatkową pracę.$\Theta(n)$

To daje nam powtarzalność (dla niektórych ), a tym samym daje nam czas , algorytm kosmiczny!$T(n) = T(cn) + \Theta(n)$$0 \lt c \lt 1$$\mathcal{O}(n)$$\mathcal{O}(1)$

Jestem prawie pewien, że znalazłem algorytm, który nie opiera się na teorii liczb lub teorii cyklu. Pamiętaj, że jest kilka szczegółów do uzgodnienia (być może jutro), ale jestem pewien, że się uda. Macham ręką, bo mam spać, nie dlatego, że próbuję ukryć problemy :)

Niech Abędzie pierwszą tablicą, Bdrugą, |A| = |B| = Ni N=2^kdla niektórych załóżmy kdla uproszczenia. Niech A[i..j]będzie podrzędną Az indeksami iaż do jwłącznie. Tablice są oparte na 0. Niech RightmostBitPos(i)zwróci pozycję (w oparciu o 0) najbardziej wysuniętego w prawo bitu, czyli „1” i, licząc od prawej. Algorytm działa w następujący sposób.

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

Weźmy tablicę 16 liczb i zacznijmy przeplatać je za pomocą swapów i zobaczmy, co się stanie:

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

Szczególnie interesująca jest pierwsza część drugiej tablicy:

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

Wzór powinien być wyraźny: naprzemiennie dodajemy liczbę na końcu i zastępujemy najniższą liczbę wysoką liczbą. Pamiętaj, że zawsze dodajemy liczbę, która jest o jeden wyższa od najwyższej liczby, którą już mamy. Gdybyśmy byli w stanie dowiedzieć się, która liczba jest najniższa w danym momencie, możemy to zrobić z łatwością.

Teraz szukamy większych przykładów, aby zobaczyć, czy możemy zobaczyć wzór. Zauważ, że nie musimy poprawiać rozmiaru tablicy, aby zbudować powyższy przykład. W pewnym momencie otrzymujemy tę konfigurację (druga linia odejmuje 16 od każdej liczby):

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

Teraz wyraźnie pokazuje to wzór: „1 3 5 7 9 11 13 15” są 2 osobno, „2 6 10 14” są 4 osobno, a „4 12” są 8 osobno. Możemy zatem opracować algorytm, który mówi nam, jaka będzie następna najmniejsza liczba: mechanizm jest dokładnie taki, jak działają liczby binarne. Masz trochę za ostatnią połowę tablicy, trochę za drugi kwartał i tak dalej.

Jeśli więc mamy wystarczającą ilość miejsca do przechowywania tych bitów (potrzebujemy bitów, ale nasz model obliczeniowy na to pozwala - wskaźnik do tablicy również potrzebuje bitów), możemy dowiedzieć się, którą liczbę zamienić w zamortyzowany czas.log n O ( 1 $\log n$$\log n$$O(1)$

Możemy zatem wprowadzić pierwszą połowę tablicy do jej stanu przeplotu w czasie i . Musimy jednak naprawić drugą połowę naszej tablicy, która wydaje się całkowicie pomieszana („8 6 5 7 13 14 15 16”).O ( n $O(n)$$O(n)$

Teraz, jeśli możemy „posortować” pierwszą połowę tej drugiej części, otrzymamy „5 6 7 8 13 14 15 16” i rekurencyjne przeplatanie tej połowy załatwi sprawę: przeplatamy tablicę w time ( wywołania rekurencyjne, z których każde zmniejsza o połowę wielkość wejściową). Zauważ, że nie potrzebujemy stosu, ponieważ te wywołania są rekurencyjne, więc nasze użycie przestrzeni pozostaje .O ( log n ) O ( 1 $O(n)$$O(\log n)$$O(1)$

Teraz pytanie brzmi: czy jest jakiś wzór w części, którą musimy posortować? Próbowanie 32 liczb daje nam „16 12 10 14 9 11 13 15” do naprawienia. Pamiętaj, że mamy tutaj dokładnie ten sam wzór! „9 11 13 15”, „10 14” i „12” są zgrupowane w taki sam sposób, jak widzieliśmy wcześniej.

Teraz sztuczka polega na rekurencyjnym przeplataniu tych części. Przeplatamy „16” i „12” na „12 16”. Przeplatamy „12 16” i „10 14” na „10 12 14 16”. Przeplatamy „10 12 14 16” i „9 11 13 15” na „9 10 11 12 13 14 15 16”. To sortuje pierwszą część.

Podobnie jak powyżej, całkowity koszt tej operacji wynosi . Podsumowując, nadal udaje nam się uzyskać całkowity czas działania .O ( n $O(n)$$O(n)$

Przykład:

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

Oto nierekurencyjny w miejscu algorytm liniowego czasu do przeplatania dwóch połówek tablicy bez dodatkowej pamięci.

Ogólna idea jest prosta: przejdź przez pierwszą połowę tablicy od lewej do prawej, zamieniając prawidłowe wartości na swoje miejsce. W miarę postępów lewe wartości, które mają być używane, są zamieniane w miejsce zwolnione przez właściwe wartości. Jedyną sztuczką jest wymyślenie, jak je wyciągnąć ponownie.

Zaczynamy od tablicy o rozmiarze N podzielonej na 2 prawie równe połowy.
[ left_items | right_items ]
Gdy go przetwarzamy, staje się
[ placed_items | remaining_left_items| swapped_left_items | remaining_right_items]

Przestrzeń wymiany rośnie według następującego wzoru: A) powiększ przestrzeń, usuwając sąsiedni prawy przedmiot i zamieniając nowy przedmiot z lewej; B) zamień najstarszy element na nowy z lewej strony. Jeśli lewe elementy są ponumerowane 1..N, ten wzór wygląda

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

Sekwencja zmian indeksu to dokładnie OEIS A025480 , którą można obliczyć za pomocą prostego procesu. Dzięki temu można znaleźć lokalizację wymiany, biorąc pod uwagę tylko liczbę dodanych do tej pory elementów, która jest również indeksem aktualnie umieszczanego elementu.

To wszystkie informacje, których potrzebujemy, aby wypełnić pierwszą połowę sekwencji w czasie liniowym.

Kiedy dojdziemy do punktu środkowego, tablica będzie się [ placed_items | swapped_left_items | remaining_right_items] składać z trzech części: Jeśli możemy rozszyfrować zamienione elementy, zmniejszyliśmy problem do połowy rozmiaru i możemy powtórzyć.

Aby rozszyfrować przestrzeń wymiany, używamy następującej właściwości: Sekwencja zbudowana przez Nnaprzemienne operacje append i swap_oldest będą zawierać N/2elementy, według których podano ich wiek A025480(N/2)..A025480(N-1). (Dzielenie liczb całkowitych, mniejsze wartości są starsze).

Na przykład, jeśli lewa połowa pierwotnie zawierała wartości 1..19, wówczas przestrzeń wymiany będzie zawierać [16, 12, 10, 14, 18, 11, 13, 15, 17, 19]. A025480 (9..18) to [2, 5, 1, 6, 3, 7, 0, 8, 4, 9]dokładnie lista indeksów pozycji od najstarszego do najnowszego.

Możemy więc rozszyfrować naszą przestrzeń wymiany, przechodząc przez nią i zamieniając S[i]się nią S[ A(N/2 + i)]. To także czas liniowy.

Pozostała komplikacja polega na tym, że ostatecznie osiągniesz pozycję, w której poprawna wartość powinna mieć niższy indeks, ale została już zamieniona. Znalezienie nowej lokalizacji jest łatwe: wystarczy ponownie wykonać obliczenia indeksu, aby dowiedzieć się, gdzie wymieniono element. Konieczne może być wykonanie kilku kroków, aż znajdziesz niezamienioną lokalizację.

W tym momencie połączyliśmy połowę macierzy i utrzymaliśmy porządek nie połączonych części w drugiej połowie, dokładnie N/2 + N/4zamieniając. Możemy kontynuować przez resztę tablicy, aby uzyskać sumę N + N/4 + N/8 + ....swapów, która jest ściśle mniejsza niż 3N/2.

Jak obliczyć A025480:
Jest to zdefiniowane w OEIS jako a(2n) = n, a(2n+1) = a(n).Alternatywne sformułowanie a(n) = isEven(n)? n/2 : a((n-1)/2). Prowadzi to do prostego algorytmu wykorzystującego operacje bitowe:

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

Jest to amortyzowana operacja O (1) dla wszystkich możliwych wartości dla N. (1/2 potrzebuje 1 zmiany, 1/4 potrzebuje 2, 1/8 potrzebuje 3, ...) . Istnieje jeszcze szybsza metoda, która wykorzystuje małą tabelę wyszukiwania, aby znaleźć pozycję najmniej znaczącego bitu zerowego.

Biorąc to pod uwagę, oto implementacja w 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;
  }
}

Powinien to być algorytm dość przyjazny dla pamięci podręcznej, ponieważ dostęp do 2 z 3 lokalizacji danych jest uzyskiwany sekwencyjnie, a ilość przetwarzanych danych ściśle się zmniejsza. Metodę tę można zmienić z wymieszania na wymieszanie na wymieszanie, negując is_eventest na początku pętli.