Algoritma in-place untuk interleaving array

Anda diberi array elemen$2n$

Tugasnya adalah untuk interleave array, menggunakan algoritma di tempat sedemikian rupa sehingga array yang dihasilkan terlihat seperti

Jika persyaratan di tempat tidak ada, kami dapat dengan mudah membuat array baru dan menyalin elemen yang memberikan algoritma waktu .$\mathcal{O}(n)$

Dengan persyaratan di tempat, algoritma divide and conquer meningkatkan algoritma menjadi .$\theta(n \log n)$

Jadi pertanyaannya adalah:

Apakah ada algoritma waktu , yang juga ada di tempat?$\mathcal{O}(n)$

(Catatan: Anda dapat mengasumsikan model RAM WORD RAM yang seragam, jadi in-place diterjemahkan menjadi batasan ruang).$\mathcal{O}(1)$

Inilah jawaban yang menguraikan algoritma dari makalah yang dihubungkan oleh Joe: http://arxiv.org/abs/0805.1598

Pertama mari kita perhatikan algoritma yang menggunakan divide dan conquer.$\Theta(n \log n)$

1) Membagi dan Taklukkan

Kita diberikan

Sekarang untuk menggunakan membagi dan menaklukkan, untuk beberapa , kami mencoba untuk mendapatkan array$m = \Theta(n)$

dan berulang.

Perhatikan bahwa bagian adalah perubahan siklik dari

oleh tempat.$m$

Ini klasik dan dapat dilakukan di tempat dengan tiga pembalikan dan dalam waktu .$\mathcal{O}(n)$

Dengan demikian membagi dan menaklukkan memberi Anda algoritma , dengan rekursi yang mirip dengan .$\Theta(n \log n)$$T(n) = 2T(n/2) + \Theta(n)$

2) Siklus Permutasi

Sekarang, pendekatan lain untuk masalah ini adalah mempertimbangkan permutasi sebagai satu set siklus terpisah.

Permutasi diberikan oleh (dengan asumsi mulai dari )$1$

Jika kita entah bagaimana tahu persis siklusnya, dengan menggunakan ruang ekstra konstan, kita dapat mewujudkan permutasi dengan memilih elemen , menentukan ke mana elemen itu pergi (menggunakan rumus di atas), meletakkan elemen di lokasi target ke dalam ruang sementara, menempatkan elemen ke lokasi target itu dan melanjutkan sepanjang siklus. Setelah kita selesai dengan satu siklus kita pindah ke elemen siklus berikutnya dan ikuti siklus itu dan seterusnya.$A$$A$

Ini akan memberi kita algoritme waktu , tetapi mengasumsikan bahwa kita "entah bagaimana tahu siklus pastinya" dan mencoba melakukan pembukuan dalam batasan ruang Inilah yang membuat masalah ini sulit.$\mathcal{O}(n)$$\mathcal{O}(1)$

Di sinilah makalah ini menggunakan teori bilangan.

Dapat ditunjukkan bahwa, dalam kasus ketika , elemen-elemen pada posisi , berada dalam siklus yang berbeda dan setiap siklus mengandung elemen pada posisi .$2n + 1 = 3^k$$1$$3, 3^2, \dots, 3^{k-1}$$3^m, m \ge 0$

Ini menggunakan fakta bahwa adalah penghasil .$2$$(\mathbb{Z}/3^k)^*$

Jadi ketika , ikuti pendekatan siklus memberi kita algoritma waktu , seperti untuk setiap siklus, kita tahu persis di mana untuk memulai: kekuatan (termasuk ) (yang dapat dihitung dalam spasi).$2n+1 = 3^k$$\mathcal{O}(n)$$3$$1$$\mathcal{O}(1)$

3) Algoritma Terakhir

Sekarang kita menggabungkan dua di atas: Membagi dan Menaklukkan + Siklus Permutasi.

Kami membagi dan menaklukkan, tetapi pilih sehingga adalah kekuatan dan .$m$$2m+1$$3$$m = \Theta(n)$

Jadi alih-alih pada pengulangan pada kedua "bagian", kita hanya mengulang pada satu dan melakukan kerja ekstra.$\Theta(n)$

Ini memberi kita pengulangan (untuk beberapa ) dan dengan demikian memberi kita waktu , algoritma ruang!$T(n) = T(cn) + \Theta(n)$$0 \lt c \lt 1$$\mathcal{O}(n)$$\mathcal{O}(1)$

Saya cukup yakin saya telah menemukan suatu algoritma yang tidak bergantung pada teori bilangan atau teori siklus. Perhatikan bahwa ada beberapa detail untuk dikerjakan (mungkin besok), tetapi saya cukup yakin mereka akan berhasil. Saya menggerakkan tangan karena saya seharusnya tidur, bukan karena saya berusaha menyembunyikan masalah :)

Biarkan Amenjadi array pertama, Byang kedua, |A| = |B| = Ndan anggap N=2^kuntuk beberapa orang k, untuk kesederhanaan. Biarkan A[i..j]menjadi subarray Adengan indeks isampai j, inklusif. Array berbasis 0. Mari RightmostBitPos(i)kembalikan posisi (berbasis-0) dari bit paling kanan yaitu '1' i, dihitung dari kanan. Algoritma bekerja sebagai berikut.

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

Mari kita ambil larik 16 angka, dan mari kita mulai menyisipkannya menggunakan swap, dan lihat apa yang terjadi:

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

Yang menarik adalah bagian pertama dari array kedua:

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

Polanya harus jelas: kita secara bergantian menambahkan angka ke ujung dan mengganti angka terendah dengan angka tinggi. Perhatikan bahwa kami selalu menambahkan angka yang lebih tinggi dari angka tertinggi yang sudah kami miliki. Jika kami entah bagaimana bisa mengetahui angka mana yang paling rendah pada waktu tertentu, kami dapat melakukannya dengan mudah.

Sekarang, kita mencari contoh yang lebih besar untuk melihat apakah kita dapat melihat suatu pola. Perhatikan bahwa kita tidak perlu memperbaiki ukuran array untuk membangun contoh di atas. Pada titik tertentu, kami mendapatkan konfigurasi ini (baris kedua mengurangi 16 dari setiap angka):

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

Sekarang ini dengan jelas menunjukkan sebuah pola: "1 3 5 7 9 11 13 15" semuanya 2 terpisah, "2 6 10 14" semuanya 4 terpisah dan "4 12" adalah 8 terpisah. Karena itu kita dapat menyusun algoritma yang memberi tahu kita berapa angka terkecil berikutnya: mekanismenya persis seperti cara kerja angka biner. Anda memiliki sedikit untuk paruh terakhir array, sedikit untuk kuartal kedua, dan seterusnya.

Jika kita oleh karena itu diberi ruang yang cukup untuk menyimpan bit-bit ini (kita membutuhkan bits, tetapi model komputasi kita memungkinkan ini - sebuah pointer ke array juga membutuhkan bits), kita dapat mencari tahu nomor mana yang akan ditukar dengan waktu diamortisasi.$\log n$$\log n$$O(1)$

Oleh karena itu kita bisa mendapatkan paruh pertama array ke dalam keadaan interleaved dalam waktu dan swap. Namun, kita harus memperbaiki paruh kedua dari array kita, yang tampaknya kacau ("8 6 5 7 13 14 15 16").$O(n)$$O(n)$

Sekarang, jika kita dapat 'mengurutkan' bagian pertama dari bagian kedua ini, kita akan berakhir dengan "5 6 7 8 13 14 15 16", dan secara interleaving setengah bagian ini akan melakukan trik: kita interleave array di time ( panggilan rekursif yang masing-masing membagi dua ukuran input). Perhatikan bahwa kita tidak perlu tumpukan karena panggilan ini bersifat rekursif ekor, jadi penggunaan ruang kita tetap .$O(n)$$O(\log n)$$O(1)$

Sekarang, pertanyaannya adalah: apakah ada beberapa pola di bagian yang perlu kita sortir? Mencoba 32 angka memberi kita "16 12 10 14 9 11 13 15" untuk memperbaikinya. Perhatikan bahwa kita memiliki pola yang sama persis di sini! "9 11 13 15", "10 14" dan "12" dikelompokkan bersama dengan cara yang sama seperti yang kita lihat sebelumnya.

Sekarang, triknya adalah secara interleave secara interleave sub bagian ini. Kami interleave "16" dan "12" ke "12 16". Kami menyisipkan "12 16" dan "10 14" ke "10 12 14 16". Kami interleave "10 12 14 16" dan "9 11 13 15" ke "9 10 11 12 13 14 15 16". Ini semacam bagian pertama.

Sama seperti di atas, total biaya operasi ini adalah . Menambahkan semua ini, kami masih berhasil mendapatkan total waktu berjalan .$O(n)$$O(n)$

Sebuah contoh:

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

Berikut ini adalah non-rekursif di tempat dalam algoritma waktu linier untuk interleave dua bagian array tanpa penyimpanan tambahan.

Gagasan umumnya sederhana: Berjalanlah melalui paruh pertama array dari kiri ke kanan, menukar nilai yang benar ke tempatnya. Saat Anda maju, nilai-nilai kiri yang belum digunakan ditukar ke ruang kosong oleh nilai-nilai yang tepat. Satu-satunya trik adalah mencari tahu cara menariknya kembali.

Kita mulai dengan array ukuran N dibagi menjadi 2 bagian yang hampir sama.
[ left_items | right_items ]
Saat kami memprosesnya, itu menjadi
[ placed_items | remaining_left_items| swapped_left_items | remaining_right_items]

Ruang swap tumbuh dengan pola berikut: A) menumbuhkan ruang dengan menghapus item kanan yang berdekatan dan menukar item baru dari kiri; B) menukar item terlama dengan item baru dari kiri. Jika item kiri diberi nomor 1..N, pola ini terlihat seperti

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

Urutan yang indeksnya diubah adalah OEIS A025480 , yang dapat dihitung dengan proses sederhana. Ini memungkinkan lokasi swap ditemukan hanya dengan jumlah item yang ditambahkan sejauh ini, yang juga merupakan indeks dari item saat ini yang ditempatkan.

Itu semua info yang kami butuhkan untuk mengisi paruh pertama urutan dalam waktu linier.

Ketika kita sampai ke titik tengah, array akan memiliki tiga bagian: [ placed_items | swapped_left_items | remaining_right_items] Jika kita dapat menguraikan item yang ditukar, kita telah mengurangi masalah menjadi setengah ukuran, dan dapat mengulangi.

Untuk mengurai ruang swap, kami menggunakan properti berikut: Urutan yang dibangun oleh Noperasi append dan swap_oldest bergantian akan berisi N/2item yang umurnya ditentukan oleh A025480(N/2)..A025480(N-1). (Divisi integer, nilai yang lebih kecil lebih tua).

Sebagai contoh, jika setengah kiri awalnya memegang nilai-nilai 1..19, maka ruang swap akan berisi [16, 12, 10, 14, 18, 11, 13, 15, 17, 19]. A025480 (9..18) adalah [2, 5, 1, 6, 3, 7, 0, 8, 4, 9], yang persis daftar indeks item dari terlama ke terbaru.

Jadi kita dapat mengacak ruang swap kita dengan memajukannya dan bertukar S[i]dengan S[ A(N/2 + i)]. Ini juga waktu linier.

Komplikasi yang tersisa adalah bahwa pada akhirnya Anda akan mencapai posisi di mana nilai yang benar harus berada pada indeks yang lebih rendah, tetapi itu sudah ditukar. Sangat mudah untuk menemukan lokasi baru: lakukan saja perhitungan indeks lagi untuk menemukan di mana item itu ditukar. Mungkin perlu mengikuti rantai beberapa langkah sampai Anda menemukan lokasi yang tidak ditukar.

Pada titik ini, kami telah menggabungkan setengah larik, dan mempertahankan urutan bagian yang tidak digeser di bagian lainnya, dengan N/2 + N/4swap yang tepat . Kita dapat melanjutkan melalui sisa array untuk total N + N/4 + N/8 + ....swap yang benar-benar kurang dari 3N/2.

Cara menghitung A025480:
Ini didefinisikan dalam OEIS sebagai a(2n) = n, a(2n+1) = a(n).formulasi alternatif a(n) = isEven(n)? n/2 : a((n-1)/2). Ini mengarah ke algoritma sederhana menggunakan operasi bitwise:

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

Ini adalah operasi O (1) yang diamortisasi atas semua nilai yang mungkin untuk N. (1/2 membutuhkan 1 shift, 1/4 membutuhkan 2, 1/8 membutuhkan 3, ...) . Ada metode yang lebih cepat yang menggunakan tabel pencarian kecil untuk menemukan posisi bit nol paling signifikan.

Karena itu, inilah implementasi di 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;
  }
}

Ini harus menjadi algoritma yang ramah cache, karena 2 dari 3 lokasi data diakses secara berurutan dan jumlah data yang sedang diproses menurun secara ketat. Metode ini dapat diubah dari out-shuffle ke in-shuffle dengan meniadakan is_eventes pada awal loop.