O (nlogn) Algoritma - Menemukan tiga yang spasi secara merata dalam string biner

Saya memiliki pertanyaan ini pada tes Algoritma kemarin, dan saya tidak tahu jawabannya. Itu membuatku benar-benar gila, karena nilainya sekitar 40 poin. Saya pikir sebagian besar kelas tidak menyelesaikannya dengan benar, karena saya belum menemukan solusi dalam 24 jam terakhir.

Diberikan string biner sembarang dengan panjang n, temukan tiga yang berjarak secara merata dalam string jika ada. Tulis algoritma yang memecahkan ini dalam waktu O (n * log (n)).

Jadi string seperti ini memiliki tiga yang "merata": 11100000, 0100100100

sunting: Ini adalah nomor acak, jadi itu harus bisa berfungsi untuk nomor apa pun. Contoh yang saya berikan adalah untuk menggambarkan properti "berjarak sama". Jadi 1001011 adalah angka yang valid. Dengan 1, 4, dan 7 menjadi yang berjarak sama.

Akhirnya! Menindaklanjuti petunjuk dalam jawaban sdcvvc , kami memilikinya: algoritma O (n log n) untuk masalahnya! Sederhana juga, setelah Anda memahaminya. Mereka yang menebak FFT benar.

Masalahnya: kita diberi string biner dengan Spanjang n , dan kami ingin menemukan tiga 1 spasi secara merata di dalamnya. Misalnya, Smungkin 110110010, di mana n = 9. Ini telah merata spasi 1s di posisi 2, 5, dan 8.

1. Pindai Skiri ke kanan, dan buat daftar Lposisi 1. Untuk yang di S=110110010atas, kita memiliki daftar L = [1, 2, 4, 5, 8]. Langkah ini adalah O (n). Masalahnya adalah sekarang untuk menemukan deret aritmetika panjang 3 di L, yaitu untuk menemukan yang berbeda a, b, c di Lsehingga ba = cb , atau ekuivalen a + c = 2b . Untuk contoh di atas, kami ingin menemukan progresi (2, 5, 8).

2. Membuat polinomial p dengan istilah x ^k untuk setiap k di L. Untuk contoh di atas, kita membuat polinomial p (x) = (x + x ² + x ⁴ + x ⁵ + x ⁸ ) . Langkah ini adalah O (n).

3. Temukan polinomial q= p ² , menggunakan Fast Fourier Transform . Untuk contoh di atas, kita mendapatkan polinomial q (x) = x ¹⁶ + 2x ¹³ + 2x ¹² + 3x ¹⁰ + 4x ⁹ + x ⁸ + 2x ⁷ + 4x ⁶ + 2x ⁵ + x ⁴ + 2x ³ + x ² . Langkah ini adalah O (n log n).

4. Abaikan semua istilah kecuali yang terkait dengan x ^2k untuk beberapa k in L. Untuk contoh di atas, kita mendapatkan istilah x ¹⁶ , 3x ¹⁰ , x ⁸ , x ⁴ , x ² . Langkah ini O (n), jika Anda memilih untuk melakukannya sama sekali.

Berikut titik penting: koefisien setiap x ^2b untuk b di Ladalah tepat jumlah pasangan (a, c) dalam Lsehingga a + c = 2b . [CLRS, Kel. 30.1-7] Satu pasangan seperti itu adalah (b, b) selalu (jadi koefisiennya paling sedikit 1), tetapi jika ada pasangan lain (a, c) , maka koefisiennya setidaknya 3, dari (a, c ) dan (c, a) . Untuk contoh di atas, kita memiliki koefisien x ¹⁰ menjadi 3 justru karena AP (2,5,8). (Koefisien ini x ^2bakan selalu menjadi angka ganjil, karena alasan di atas. Dan semua koefisien lain dalam q akan selalu genap.)

Jadi, algoritmanya adalah untuk melihat koefisien dari istilah-istilah ini x ^2b , dan melihat apakah ada di antara mereka yang lebih besar dari 1. Jika tidak ada, maka tidak ada spasi 1s yang merata. Jika ada adalah sebuah b di Lmana koefisien x ^2b lebih besar dari 1, maka kita tahu bahwa ada beberapa pasangan (a, c) - selain (b, b) - untuk yang a + c = 2b . Untuk menemukan pasangan yang sebenarnya, kita cukup mencoba masing - masing a dalam L( c yang sesuai adalah 2b-a ) dan melihat apakah ada 1 pada posisi 2b-a in S. Langkah ini adalah O (n).

Itu saja, semuanya.

Orang mungkin bertanya: apakah kita perlu menggunakan FFT? Banyak jawaban, seperti beta , flybywire , dan rsp , menyarankan bahwa pendekatan yang memeriksa setiap pasangan 1s dan melihat apakah ada 1 pada posisi "ketiga", mungkin bekerja di O (n log n), berdasarkan intuisi bahwa jika ada terlalu banyak 1, kita akan menemukan triple dengan mudah, dan jika ada terlalu sedikit 1, memeriksa semua pasangan membutuhkan sedikit waktu. Sayangnya, sementara intuisi ini benar dan pendekatan sederhana adalah lebih baik dari O (n ² ), tidak secara signifikan lebih baik. Seperti dalam jawaban sdcvvc , kita dapat mengambil "set Cantor-like" dari string dengan panjang n = 3 ^k, dengan 1s pada posisi yang representasi ternernya hanya memiliki 0s dan 2s (no 1s) di dalamnya. String semacam itu memiliki 2 ^k = n ^{(log 2) / (log 3)} ≈ n ^0,63 di dalamnya dan tidak ada spasi 1s secara merata, jadi memeriksa semua pasangan adalah urutan kuadrat dari jumlah 1s di dalamnya: itu 4 ^k ≈ n ^1.26 yang sayangnya secara asimptot jauh lebih besar dari (n log n). Faktanya, kasus terburuk bahkan lebih buruk: Leo Moser pada tahun 1953 membangun (secara efektif) string seperti itu yang memiliki n ^{1-c / √ (log n)} 1s di dalamnya tetapi tidak ada spasi 1s secara merata, yang berarti bahwa pada string seperti itu, sederhana pendekatan akan mengambil Θ (n ^{2-2c / √ (log n)} )- hanya kecil sedikit lebih baik dari Θ (n ² ) , mengejutkan!

Tentang jumlah maksimum 1s dalam string dengan panjang n tanpa 3 yang berjarak secara merata (yang kita lihat di atas setidaknya n ^0,63 dari konstruksi yang mudah digunakan seperti Cantor, dan setidaknya n ^{1-c / √ (log n)} dengan Konstruksi Moser) - ini adalah OEIS A003002 . Dapat juga dihitung langsung dari OEIS A065825 sebagai k sedemikian sehingga A065825 (k) ≤ n <A065825 (k + 1). Saya menulis sebuah program untuk menemukan ini, dan ternyata algoritma serakah tidak memberikan string terpanjang seperti itu. Misalnya, untuk n = 9, kita bisa mendapatkan 5 1s (110100011) tetapi serakah hanya memberikan 4 (110110000), untuk n= 26, kita bisa mendapatkan 11 1s (110010100010000000000000000000010101.010) tetapi yang serakah hanya memberi 8 (110110000110110000000000000000000000), dan untuk n = 74 kita bisa mendapatkan 221s. Mereka setuju di beberapa tempat sampai 50 (misalnya semua 38 hingga 50), meskipun. Seperti yang dikatakan referensi OEIS, tampaknya Jaroslaw Wroblewski tertarik dengan pertanyaan ini, dan ia mengelola sebuah situs web di perangkat non-rata-rata ini . Jumlah pastinya hanya diketahui hingga 194.

Masalah Anda disebut AVERAGE dalam makalah ini (1999):

Masalahnya adalah 3SUM-keras jika ada pengurangan sub-kuadrat dari masalah 3SUM: Diberikan himpunan A dari n bilangan bulat, apakah ada elemen a, b, c di A sedemikian sehingga a + b + c = 0? Tidak diketahui apakah RATA-RATA adalah 3SUM-keras. Namun, ada pengurangan waktu linear sederhana dari AVERAGE ke 3SUM, yang uraiannya kami hilangkan.

Wikipedia :

Ketika bilangan bulat berada dalam kisaran [−u ... u], 3SUM dapat diselesaikan dalam waktu O (n + u lg u) dengan menyatakan S sebagai vektor bit dan melakukan konvolusi menggunakan FFT.

Ini cukup untuk menyelesaikan masalah Anda :).

Yang sangat penting adalah bahwa O (n log n) adalah kompleksitas dalam hal jumlah nol dan satu, bukan jumlah yang (yang dapat diberikan sebagai array, seperti [1,5,9,15]). Memeriksa apakah suatu himpunan memiliki perkembangan aritmatika, ketentuan angka 1, sulit, dan menurut makalah itu pada tahun 1999 tidak ada algoritma yang lebih cepat daripada O (n ² ) yang diketahui, dan diduga bahwa itu tidak ada. Semua orang yang tidak memperhitungkan ini berusaha memecahkan masalah terbuka.

Info menarik lainnya, kebanyakan tidak menarik:

Batas bawah:

Batas bawah yang mudah adalah set Cantor-like (angka 1..3 ^ n-1 tidak mengandung 1 dalam ekspansi terner mereka) - densitasnya adalah n ^ (log_3 2) (sekitar 0,631). Jadi setiap pengecekan jika set tidak terlalu besar, dan kemudian memeriksa semua pasangan tidak cukup untuk mendapatkan O (n log n). Anda harus menyelidiki urutan lebih pintar. Batas bawah yang lebih baik dikutip di sini - ini n ^{1-c / (log (n)) ^ (1/2)} . Ini berarti set Cantor tidak optimal.

Batas atas - algoritme lama saya:

Diketahui bahwa untuk n besar, subset dari {1,2, ..., n} tidak mengandung progresi aritmatika memiliki paling banyak elemen n / (log n) ^ (1/20). Makalah Pada tiga kali lipat dalam perkembangan aritmatika membuktikan lebih: set tidak dapat mengandung lebih dari n * 2 ²⁸ * (log log n / log n) ^1/2 elemen. Jadi Anda bisa memeriksa apakah ikatan itu tercapai dan jika tidak, periksa pasangan secara naif. Ini adalah algoritma O (n ² * log log n / log n), lebih cepat dari O (n ² ). Sayangnya "Di triples ..." ada di Springer - tetapi halaman pertama tersedia, dan eksposisi Ben Green tersedia di sini , halaman 28, teorema 24.

Ngomong-ngomong, makalahnya berasal dari tahun 1999 - tahun yang sama dengan yang pertama saya sebutkan, jadi mungkin itu sebabnya yang pertama tidak menyebutkan hasil itu.

Ini bukan solusi, tetapi garis pemikiran yang serupa dengan apa yang dipikirkan Olexiy

Saya bermain-main dengan membuat urutan dengan jumlah maksimum, dan semuanya cukup menarik, saya mendapatkan hingga 125 digit dan di sini adalah 3 angka pertama yang ditemukan dengan mencoba memasukkan bit '1' sebanyak mungkin:

• 11011000011011000000000000001101100001101100000000000000000000000000000000000000000000011011000011011000000000000000011011000011011
• 1011010001011010000000000001010110100010110100000000000000000000000000000000000000000000010110100010110100000000000010101101000101010
• 100110010100110010000000000100110010100110010000000000000000000000000000000000000000100100000010010000000000000000000010011001010011001

Perhatikan mereka semua fraktal (tidak terlalu mengejutkan mengingat kendala). Mungkin ada sesuatu dalam berpikir mundur, mungkin jika string bukan fraktal dengan karakteristik, maka harus memiliki pola yang berulang?

Berkat beta untuk istilah yang lebih baik untuk menggambarkan angka-angka ini.

Pembaruan: Sayangnya sepertinya pola rusak ketika memulai dengan string awal yang cukup besar, seperti: 10000000000001:

100000000000011
10000000000001101
100000000000011011
10000000000001101100001
100000000000011011000011
10000000000001101100001101
100000000000011011000011010000000001
100000000000011011000011010000000001001
1000000000000110110000110100000000010011
1000000000000110110000110100000000010011001
10000000000001101100001101000000000100110010000000001
10000000000001101100001101000000000100110010000000001000001
1000000000000110110000110100000000010011001000000000100000100000000000001
10000000000001101100001101000000000100110010000000001000001000000000000011
1000000000000110110000110100000000010011001000000000100000100000000000001101
100000000000011011000011010000000001001100100000000010000010000000000000110100001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001
1000000000000110110000110100000000010011001000000000100000100000000000001101000010010000010000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001
1000000000000110110000110100000000010011001000000000100000100000000000001101000010010000010000001100010000000010000000000000000000000000000000000000000100000010000000000000011
1000000000000110110000110100000000010011001000000000100000100000000000001101000010010000010000001100010000000010000000000000000000000000000000000000000100000010000000000000011000000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001001000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001001000100100000100000000000001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001001000001000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001001000100100000100000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001001000001000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000011
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001001000001000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000011000001
1000000000000110110000110100000000010011001000000000100000100000000000001101000010010000010000001100010000000010000000000000000000000000000000000000000100000010000000000000011000000001100100000000100100000000000010000000010000100000100100010010000010000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000110000010000000000000000000001
1000000000000110110000110100000000010011001000000000100000100000000000001101000010010000010000001100010000000010000000000000000000000000000000000000000100000010000000000000011000000001100100000000100100000000000010000000010000100000100100010010000010000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000110000010000000000000000000001001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001001000100100000100000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000001100000100000000000000000000010010000000000000000000000000000000000001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001001000001000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000011000001000000000000000000000100100000000000000000000000000000000000011
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001001000001000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000011000001000000000000000000000100100000000000000000000000000000000000011001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001001000100100000100000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000001100000100000000000000000000010010000000000000000000000000000000000001100100000000000000000000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001001000100100000100000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000001100000100000000000000000000010010000000000000000000000000000000000001100100000000000000000000001001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001001000100100000100000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000001100000100000000000000000000010010000000000000000000000000000000000001100100000000000000000000001001000001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001001000001000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000011000001000000000000000000000100100000000000000000000000000000000000011001000000000000000000000010010000010000001
1000000000000110110000110100000000010011001000000000100000100000000000001101000010010000010000001100010000000010000000000000000000000000000000000000000100000010000000000000011000000001100100000000100100000000000010000000010000100000100100010010000010000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000110000010000000000000000000001001000000000000000000000000000000000000110010000000000000000000000100100000100000011
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001001000100100000100000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000001100000100000000000000000000010010000000000000000000000000000000000001100100000000000000000000001001000001000000110000000000001

Saya menduga bahwa pendekatan sederhana yang terlihat seperti O (n ^ 2) sebenarnya akan menghasilkan sesuatu yang lebih baik, seperti O (n ln (n)). Urutan yang membutuhkan waktu paling lama untuk diuji (untuk setiap n yang diberikan) adalah yang tidak mengandung trio, dan yang memberikan batasan ketat pada jumlah 1 yang dapat berada dalam urutan.

Saya telah mengajukan beberapa argumen yang melambaikan tangan, tetapi saya belum dapat menemukan bukti yang rapi. Saya akan mengambil bacokan dalam kegelapan: jawabannya adalah ide yang sangat pintar bahwa profesor telah tahu begitu lama sehingga tampak jelas, tetapi itu terlalu sulit bagi para siswa. (Entah itu atau Anda tidur melalui ceramah yang membahasnya.)

Revisi: 2009-10-17 23:00

Saya sudah menjalankan ini pada sejumlah besar (seperti, string 20 juta) dan saya sekarang percaya algoritma ini bukan O (n logn). Meskipun demikian, ini adalah implementasi yang cukup keren dan berisi sejumlah optimasi yang membuatnya berjalan sangat cepat. Ini mengevaluasi semua pengaturan string biner 24 atau lebih sedikit digit dalam waktu kurang dari 25 detik.

Saya telah memperbarui kode untuk memasukkan 0 <= L < M < U <= X-1pengamatan dari hari ini sebelumnya.

Asli

Ini, dalam konsepnya, mirip dengan pertanyaan lain yang saya jawab . Kode itu juga melihat tiga nilai dalam satu seri dan menentukan apakah triplet memenuhi suatu syarat. Berikut adalah kode C # yang diadaptasi dari itu:

using System;
using System.Collections.Generic;

namespace StackOverflow1560523
{
    class Program
    {
        public struct Pair<T>
        {
            public T Low, High;
        }
        static bool FindCandidate(int candidate, 
            List<int> arr, 
            List<int> pool, 
            Pair<int> pair, 
            ref int iterations)
        {
            int lower = pair.Low, upper = pair.High;
            while ((lower >= 0) && (upper < pool.Count))
            {
                int lowRange = candidate - arr[pool[lower]];
                int highRange = arr[pool[upper]] - candidate;
                iterations++;
                if (lowRange < highRange)
                    lower -= 1;
                else if (lowRange > highRange)
                    upper += 1;
                else
                    return true;
            }
            return false;
        }
        static List<int> BuildOnesArray(string s)
        {
            List<int> arr = new List<int>();
            for (int i = 0; i < s.Length; i++)
                if (s[i] == '1')
                    arr.Add(i);
            return arr;
        }
        static void BuildIndexes(List<int> arr, 
            ref List<int> even, ref List<int> odd, 
            ref List<Pair<int>> evenIndex, ref List<Pair<int>> oddIndex)
        {
            for (int i = 0; i < arr.Count; i++)
            {
                bool isEven = (arr[i] & 1) == 0;
                if (isEven)
                {
                    evenIndex.Add(new Pair<int> {Low=even.Count-1, High=even.Count+1});
                    oddIndex.Add(new Pair<int> {Low=odd.Count-1, High=odd.Count});
                    even.Add(i);
                }
                else
                {
                    oddIndex.Add(new Pair<int> {Low=odd.Count-1, High=odd.Count+1});
                    evenIndex.Add(new Pair<int> {Low=even.Count-1, High=even.Count});
                    odd.Add(i);
                }
            }
        }

        static int FindSpacedOnes(string s)
        {
            // List of indexes of 1s in the string
            List<int> arr = BuildOnesArray(s);
            //if (s.Length < 3)
            //    return 0;

            //  List of indexes to odd indexes in arr
            List<int> odd = new List<int>(), even = new List<int>();

            //  evenIndex has indexes into arr to bracket even numbers
            //  oddIndex has indexes into arr to bracket odd numbers
            List<Pair<int>> evenIndex = new List<Pair<int>>(), 
                oddIndex = new List<Pair<int>>(); 
            BuildIndexes(arr, 
                ref even, ref odd, 
                ref evenIndex, ref oddIndex);

            int iterations = 0;
            for (int i = 1; i < arr.Count-1; i++)
            {
                int target = arr[i];
                bool found = FindCandidate(target, arr, odd, oddIndex[i], ref iterations) || 
                    FindCandidate(target, arr, even, evenIndex[i], ref iterations);
                if (found)
                    return iterations;
            }
            return iterations;
        }
        static IEnumerable<string> PowerSet(int n)
        {
            for (long i = (1L << (n-1)); i < (1L << n); i++)
            {
                yield return Convert.ToString(i, 2).PadLeft(n, '0');
            }
        }
        static void Main(string[] args)
        {
            for (int i = 5; i < 64; i++)
            {
                int c = 0;
                string hardest_string = "";
                foreach (string s in PowerSet(i))
                {
                    int cost = find_spaced_ones(s);
                    if (cost > c)
                    {
                        hardest_string = s;
                        c = cost;
                        Console.Write("{0} {1} {2}\r", i, c, hardest_string);
                    }
                }
                Console.WriteLine("{0} {1} {2}", i, c, hardest_string);
            }
        }
    }
}

Perbedaan utama adalah:

1. Pencarian solusi yang lengkap
   Kode ini menghasilkan kumpulan data untuk menemukan input tersulit untuk dipecahkan untuk algoritma ini.
2. Semua solusi versus yang paling sulit dipecahkan
   Kode untuk pertanyaan sebelumnya menghasilkan semua solusi menggunakan generator python. Kode ini hanya menampilkan yang paling sulit untuk setiap panjang pola.
3. Algoritma pemberian skor
   Kode ini memeriksa jarak dari elemen tengah ke sisi kiri dan kanannya. Kode python menguji apakah jumlah di atas atau di bawah 0.
4. Konvergensi pada seorang kandidat
   Kode saat ini bekerja dari tengah menuju tepi untuk menemukan seorang kandidat. Kode dalam masalah sebelumnya bekerja dari tepi ke tengah. Perubahan terakhir ini memberikan peningkatan kinerja yang besar.
5. Penggunaan genap genap dan ganjil
   Berdasarkan pengamatan pada akhir artikel ini, kode mencari pasangan genap angka genap untuk menemukan L dan U, menjaga M tetap. Ini mengurangi jumlah pencarian dengan informasi pra-komputasi. Dengan demikian, kode ini menggunakan dua tingkat tipuan dalam loop utama FindCandidate dan membutuhkan dua panggilan ke FindCandidate untuk setiap elemen tengah: sekali untuk angka genap dan sekali untuk yang aneh.

Gagasan umum adalah bekerja pada indeks, bukan representasi data mentah. Menghitung larik di mana 1 muncul memungkinkan algoritma untuk berjalan dalam waktu yang proporsional dengan jumlah 1 dalam data daripada dalam waktu yang proporsional dengan panjang data. Ini adalah transformasi standar: buat struktur data yang memungkinkan operasi lebih cepat sambil menjaga masalah tetap sama.

Hasilnya kedaluwarsa: dihapus.

Sunting: 2009-10-16 18:48

Pada data yx, yang diberi kepercayaan pada respons lain sebagai perwakilan dari data sulit untuk dihitung, saya mendapatkan hasil ini ... Saya menghapus ini. Mereka ketinggalan zaman.

Saya akan menunjukkan bahwa data ini bukan yang paling sulit untuk algoritma saya, jadi saya pikir asumsi bahwa fraktal yx adalah yang paling sulit untuk dipecahkan adalah salah. Kasus terburuk untuk algoritma tertentu, saya harapkan, akan tergantung pada algoritma itu sendiri dan kemungkinan tidak akan konsisten di berbagai algoritma.

Sunting: 2009-10-17 13:30

Pengamatan lebih lanjut tentang ini.

Pertama, konversikan string 0 dan 1 menjadi array indeks untuk setiap posisi 1. Katakan panjang array itu adalah X. Lalu tujuannya adalah menemukan

0 <= L < M < U <= X-1

seperti yang

A[M] - A[L] = A[U] - A[M]

atau

2*A[M] = A[L] + A[U]

Karena A [L] dan A [U] jumlah ke bilangan genap, mereka tidak bisa (genap, ganjil) atau (ganjil, genap). Pencarian untuk pertandingan dapat ditingkatkan dengan memecah A [] menjadi kelompok yang genap dan genap dan mencari pasangan pada kelompok [M] di kelompok calon yang genap dan genap.

Namun, ini lebih merupakan optimasi kinerja daripada peningkatan algoritmik, saya pikir. Jumlah perbandingan harus turun, tetapi urutan algoritme harus sama.

Sunting 2009-10-18 00:45

Namun optimasi lain terjadi pada saya, dengan cara yang sama seperti memisahkan kandidat menjadi genap dan ganjil. Karena ketiga indeks harus ditambahkan ke kelipatan 3 (a, a + x, a + 2x - mod 3 adalah 0, terlepas dari a dan x), Anda dapat memisahkan L, M, dan U ke dalam nilai mod 3 mereka. :

M  L  U
0  0  0
   1  2
   2  1
1  0  2
   1  1
   2  0
2  0  1
   1  0
   2  2

Bahkan, Anda bisa menggabungkan ini dengan pengamatan even / odd dan memisahkannya ke dalam nilai mod 6 mereka:

M  L  U
0  0  0
   1  5
   2  4
   3  3
   4  2
   5  1

dan seterusnya. Ini akan memberikan optimasi kinerja lebih lanjut tetapi bukan peningkatan algoritmik.

Belum dapat menemukan solusi :(, tetapi punya beberapa ide.

Bagaimana jika kita mulai dari masalah terbalik: membuat urutan dengan jumlah maksimum 1s dan TANPA trio yang berjarak sama rata. Jika Anda dapat membuktikan jumlah maksimum 1s adalah o (n), maka Anda dapat meningkatkan perkiraan Anda dengan mengulangi hanya melalui daftar 1s saja.

Ini dapat membantu ....

Masalah ini berkurang menjadi sebagai berikut:

Diberikan urutan bilangan bulat positif, temukan urutan yang berdekatan dipartisi ke dalam awalan dan akhiran sedemikian sehingga jumlah awalan berikutnya sama dengan jumlah akhiran akhiran berikutnya.

Sebagai contoh, diberi urutan [ 3, 5, 1, 3, 6, 5, 2, 2, 3, 5, 6, 4 ], kita akan menemukan urutan [ 3, 6, 5, 2, 2]dengan awalan [ 3, 6 ]dengan jumlah awalan 9dan akhiran [ 5, 2, 2 ]dengan jumlah akhiran dari9 .

Pengurangannya adalah sebagai berikut:

Diberi urutan nol dan satu, dan mulai dari yang paling kiri, terus bergerak ke kanan. Setiap kali yang lain ditemui, catat jumlah gerakan sejak yang sebelumnya ditemui dan tambahkan nomor itu ke urutan yang dihasilkan.

Misalnya, diberi urutan [ 0, 1, 1, 0, 0, 1, 0, 0, 0, 1 0 ], kita akan menemukan pengurangan [ 1, 3, 4]. Dari reduksi ini, kami menghitung urutan yang berdekatan [ 1, 3, 4], awalan [ 1, 3]dengan jumlah 4, dan akhiran [ 4 ]dengan jumlah4 .

Pengurangan ini dapat dihitung dalam O(n) .

Sayangnya, saya tidak yakin ke mana harus pergi dari sini.

Untuk jenis masalah sederhana (yaitu Anda mencari tiga "1" dengan hanya (yaitu nol atau lebih) "0" di antara itu), Ini cukup sederhana: Anda bisa membagi urutan di setiap "1" dan mencari dua urutan yang berdekatan setelah panjang yang sama (tentu saja urutan kedua bukan yang terakhir). Jelas, ini bisa dilakukan dalam O (n) waktu.

Untuk versi yang lebih kompleks (yaitu Anda mencari indeks i dan celah g > 0 sedemikian rupa s[i]==s[i+g]==s[i+2*g]=="1"), saya tidak yakin, jika ada solusi O (n log n) , karena mungkin ada O (n²) kembar tiga yang memiliki properti ini (pikirkan string semua yang ada, ada sekitar n² / 2 kembar tiga seperti itu). Tentu saja, Anda hanya mencari satu di antaranya, tetapi saat ini saya tidak tahu, bagaimana cara menemukannya ...

Pertanyaan yang menyenangkan, tetapi begitu Anda menyadari bahwa pola aktual antara dua '1 tidak masalah, algoritme menjadi:

• memindai mencari '1'
• mulai dari pemindaian posisi berikutnya untuk '1' lainnya (ke akhir array dikurangi jarak dari '1' saat ini atau yang ketiga '1' akan di luar batas)
• jika pada posisi ke-2 '1' ditambah jarak ke 1 pertama 'ketiga' 1 'ditemukan, kita memiliki spasi yang sama.

Dalam kode, JTest fashion, (Perhatikan kode ini tidak ditulis untuk menjadi paling efisien dan saya menambahkan beberapa println untuk melihat apa yang terjadi.)

import java.util.Random;

import junit.framework.TestCase;

public class AlgorithmTest extends TestCase {

 /**
  * Constructor for GetNumberTest.
  *
  * @param name The test's name.
  */
 public AlgorithmTest(String name) {
  super(name);
 }

 /**
  * @see TestCase#setUp()
  */
 protected void setUp() throws Exception {
  super.setUp();
 }

 /**
  * @see TestCase#tearDown()
  */
 protected void tearDown() throws Exception {
  super.tearDown();
 }

 /**
  * Tests the algorithm.
  */
 public void testEvenlySpacedOnes() {

  assertFalse(isEvenlySpaced(1));
  assertFalse(isEvenlySpaced(0x058003));
  assertTrue(isEvenlySpaced(0x07001));
  assertTrue(isEvenlySpaced(0x01007));
  assertTrue(isEvenlySpaced(0x101010));

  // some fun tests
  Random random = new Random();

  isEvenlySpaced(random.nextLong());
  isEvenlySpaced(random.nextLong());
  isEvenlySpaced(random.nextLong());
 }

 /**
  * @param testBits
  */
 private boolean isEvenlySpaced(long testBits) {
  String testString = Long.toBinaryString(testBits);
  char[] ones = testString.toCharArray();
  final char ONE = '1';

  for (int n = 0; n < ones.length - 1; n++) {

   if (ONE == ones[n]) {
    for (int m = n + 1; m < ones.length - m + n; m++) {

     if (ONE == ones[m] && ONE == ones[m + m - n]) {
      System.out.println(" IS evenly spaced: " + testBits + '=' + testString);
      System.out.println("               at: " + n + ", " + m + ", " + (m + m - n));
      return true;
     }
    }
   }
  }

  System.out.println("NOT evenly spaced: " + testBits + '=' + testString);
  return false;
 }
}

Saya memikirkan pendekatan membagi dan menaklukkan yang mungkin berhasil.

Pertama, dalam preprocessing Anda harus memasukkan semua angka kurang dari setengah ukuran input Anda ( n / 3) ke dalam daftar.

Diberikan string: 0000010101000100 (perhatikan bahwa contoh khusus ini valid)

Masukkan semua bilangan prima (dan 1) dari 1 hingga (16/2) ke dalam daftar: {1, 2, 3, 4, 5, 6, 7}

Kemudian bagi menjadi dua:

100000101 01000100

Terus lakukan ini sampai Anda mendapatkan string ukuran 1. Untuk semua string ukuran-satu dengan 1 di dalamnya, tambahkan indeks string ke daftar kemungkinan; jika tidak, kembalikan -1 untuk kegagalan.

Anda juga harus mengembalikan daftar jarak spasi yang masih mungkin, terkait dengan setiap indeks awal. (Mulailah dengan daftar yang Anda buat di atas dan hapus angka saat Anda pergi) Di sini, daftar kosong berarti Anda hanya berurusan dengan satu 1 dan sehingga spasi apa pun mungkin pada saat ini; kalau tidak, daftar mencakup jarak yang harus dikesampingkan.

Jadi lanjutkan dengan contoh di atas:

1000 0101 0100 0100

10 00 01 01 01 00 01 00

1 0 0 0 0 1 0 1 0 1 0 0 0 1 0 0

Pada langkah menggabungkan pertama, kami memiliki delapan set dua sekarang. Pada yang pertama, kita memiliki kemungkinan satu set, tetapi kita belajar bahwa spasi dengan 1 tidak mungkin karena nol lainnya ada di sana. Jadi kita mengembalikan 0 (untuk indeks) dan {2,3,4,5,7} untuk fakta bahwa spasi dengan 1 tidak mungkin. Yang kedua, kita tidak punya apa-apa dan jadi -1. Yang ketiga kami memiliki kecocokan tanpa spasi dihilangkan dalam indeks 5, jadi kembalikan 5, {1,2,3,4,5,7}. Pada pasangan keempat kita kembalikan 7, {1,2,3,4,5,7}. Di urutan kelima, kembalikan 9, {1,2,3,4,5,7}. Di keenam, kembali -1. Di ketujuh, kembalikan 13, {1,2,3,4,5,7}. Di kedelapan, kembalikan -1.

Menggabungkan lagi menjadi empat set empat, kami memiliki:

1000: Return (0, {4,5,6,7}) 0101: Return (5, {2,3,4,5,6,7}), (7, {1,2,3,4,5,6 , 7}) 0100: Kembali (9, {3,4,5,6,7}) 0100 : Kembali (13, {3,4,5,6,7})

Menggabungkan ke dalam set delapan:

10000101: Return (0, {5,7}), (5, {2,3,4,5,6,7}), (7, {1,2,3,4,5,6,7}) 01000100 : Return (9, {4,7}), (13, {3,4,5,6,7})

Menggabungkan ke dalam satu set enam belas:

10000101 01000100

Seiring kemajuan kami, kami terus memeriksa semua kemungkinan sejauh ini. Hingga langkah ini kami telah meninggalkan hal-hal yang melampaui akhir dari string, tetapi sekarang kami dapat memeriksa semua kemungkinan.

Pada dasarnya, kami memeriksa 1 pertama dengan jarak 5 dan 7, dan menemukan bahwa mereka tidak berbaris ke 1. (Perhatikan bahwa setiap cek adalah KONSTAN, bukan waktu linier) Kemudian kita periksa yang kedua (indeks 5) dengan jarak 2, 3, 4, 5, 6, dan 7-- atau kita mau, tetapi kita bisa berhenti pada 2 karena yang benar-benar cocok.

Fiuh! Itu algoritma yang agak panjang.

Saya tidak tahu 100% apakah itu O (n log n) karena langkah terakhir, tetapi semua yang ada pasti O (n log n) sejauh yang saya tahu. Saya akan kembali ke sini nanti dan mencoba untuk memperbaiki langkah terakhir.

EDIT: Mengubah jawaban saya untuk mencerminkan komentar Welbog. Maaf atas kesalahannya. Saya akan menulis beberapa pseudocode nanti, ketika saya mendapat lebih banyak waktu untuk menguraikan apa yang saya tulis lagi. ;-)

Saya akan memberikan tebakan kasar saya di sini, dan biarkan mereka yang lebih baik dengan kompleksitas menghitung untuk membantu saya tentang bagaimana harga algoritma saya dalam O-notasi bijaksana

1. diberikan string biner 0000010101000100 (sebagai contoh)
2. krop kepala dan ekor nol -> 00000 101010001 00
3. kami mendapatkan 101010001 dari perhitungan sebelumnya
4. periksa apakah bit tengah 'satu', jika benar, ditemukan valid tiga spasi 'satu' (hanya jika jumlah bit ganjil diberi nomor)
5. korelatif, jika jumlah potongan yang dipotong tetap genap dinomori, kepala dan ekor 'satu' tidak dapat menjadi bagian dari 'satu' yang ditempatkan secara merata,
6. kita menggunakan 1010100001 sebagai contoh (dengan 'nol' ekstra untuk menjadi tanaman genap), dalam hal ini kita perlu memotong lagi, kemudian menjadi -> 10101 00001
7. kami mendapatkan 10101 dari perhitungan sebelumnya, dan periksa bit tengah, dan kami menemukan bit yang berjarak sama lagi

Saya tidak tahu bagaimana cara menghitung kompleksitas untuk ini, adakah yang bisa membantu?

edit: tambahkan beberapa kode untuk menggambarkan ide saya

edit2: mencoba mengkompilasi kode saya dan menemukan beberapa kesalahan besar, diperbaiki

char *binaryStr = "0000010101000100";

int main() {
   int head, tail, pos;
   head = 0;
   tail = strlen(binaryStr)-1;
   if( (pos = find3even(head, tail)) >=0 )
      printf("found it at position %d\n", pos);
   return 0;
}

int find3even(int head, int tail) {
   int pos = 0;
   if(head >= tail) return -1;
   while(binaryStr[head] == '0') 
      if(head<tail) head++;
   while(binaryStr[tail] == '0') 
      if(head<tail) tail--;
   if(head >= tail) return -1;
   if( (tail-head)%2 == 0 && //true if odd numbered
       (binaryStr[head + (tail-head)/2] == '1') ) { 
         return head;
   }else {
      if( (pos = find3even(head, tail-1)) >=0 )
         return pos;
      if( (pos = find3even(head+1, tail)) >=0 )
         return pos;
   }
   return -1;
}

Saya datang dengan sesuatu seperti ini:

def IsSymetric(number):
    number = number.strip('0')

    if len(number) < 3:
        return False
    if len(number) % 2 == 0:
        return IsSymetric(number[1:]) or IsSymetric(number[0:len(number)-2])
    else:
        if number[len(number)//2] == '1':
            return True
        return IsSymetric(number[:(len(number)//2)]) or IsSymetric(number[len(number)//2+1:])
    return False

Ini terinspirasi oleh andycjw.

1. Potong nol.
2. Jika itupun menguji dua substring 0 - (len-2) (lewati karakter terakhir) dan dari 1 - (len-1) (lewati karakter pertama)
3. Jika tidak, bahkan jika char tengah adalah salah satu dari kita sukses. Lain membagi string di tengah tanpa elemen tengah dan periksa kedua bagian.

Mengenai kerumitan ini mungkin O (nlogn) seperti pada setiap rekursi kita membaginya dengan dua.

Semoga ini bisa membantu.

Oke, saya akan coba lagi masalah ini. Saya pikir saya bisa membuktikan algoritma O (n log (n)) yang mirip dengan yang sudah dibahas dengan menggunakan pohon biner seimbang untuk menyimpan jarak antara 1's. Pendekatan ini terinspirasi oleh pengamatan Hakim tentang mengurangi masalah menjadi daftar jarak antara 1 itu.

Bisakah kita memindai string input untuk membangun pohon biner seimbang di sekitar posisi 1 sehingga setiap node menyimpan posisi 1 dan setiap tepi diberi label dengan jarak ke 1 yang berdekatan untuk setiap simpul anak. Sebagai contoh:

10010001 gives the following tree

      3
     / \
  2 /   \ 3
   /     \
  0       7

Ini dapat dilakukan dalam O (n log (n)) karena, untuk string berukuran n, setiap penyisipan mengambil O (log (n)) dalam kasus terburuk.

Maka masalahnya adalah untuk mencari pohon untuk menemukan apakah, pada simpul mana pun, ada jalur dari simpul itu melalui anak kiri yang memiliki jarak yang sama dengan jalur melalui anak kanan. Ini dapat dilakukan secara rekursif pada setiap subtree. Saat menggabungkan dua subtree dalam pencarian, kita harus membandingkan jarak dari jalur di subtree kiri dengan jarak dari jalur di kanan. Karena jumlah jalur dalam subtree akan sebanding dengan log (n), dan jumlah node adalah n, saya percaya ini dapat dilakukan dalam waktu O (n log (n)) waktu.

Apakah saya melewatkan sesuatu?

Ini sepertinya masalah yang menyenangkan jadi saya memutuskan untuk mencoba.

Saya membuat asumsi bahwa 111000001 akan menemukan 3 yang pertama dan menjadi sukses. Pada dasarnya jumlah nol yang mengikuti angka 1 adalah hal yang penting, karena 0111000 sama dengan 111000 menurut definisi Anda. Setelah Anda menemukan dua kasus 1, 1 berikutnya ditemukan menyelesaikan trilogi.

Ini dia dengan Python:

def find_three(bstring):
    print bstring
    dict = {}
    lastone = -1
    zerocount = 0
    for i in range(len(bstring)):
        if bstring[i] == '1':
            print i, ': 1'
            if lastone != -1:
                if(zerocount in dict):
                    dict[zerocount].append(lastone)
                    if len(dict[zerocount]) == 2:
                        dict[zerocount].append(i)
                        return True, dict
                else:
                    dict[zerocount] = [lastone]
            lastone = i
            zerocount = 0
        else:
            zerocount = zerocount + 1
    #this is really just book keeping, as we have failed at this point
    if lastone != -1:
        if(zerocount in dict):
            dict[zerocount].append(lastone)
        else:
            dict[zerocount] = [lastone]
    return False, dict

Ini adalah percobaan pertama, jadi saya yakin ini bisa ditulis dengan cara yang lebih bersih. Harap sebutkan kasus di mana metode ini gagal di bawah.

Saya berasumsi alasan ini nlog (n) disebabkan oleh hal berikut:

• Untuk menemukan 1 yang merupakan awal triplet, Anda perlu memeriksa (n-2) karakter. Jika Anda belum menemukannya pada saat itu, Anda tidak akan (karakter n-1 dan n tidak dapat memulai triplet) (O (n))
• Untuk menemukan 1 kedua yang merupakan bagian dari triplet (dimulai oleh yang pertama), Anda perlu memeriksa m / 2 (m = nx, di mana x adalah offset dari 1 pertama) karakter. Ini karena, jika Anda belum menemukan 1 kedua saat Anda setengah dari yang pertama hingga akhir, Anda tidak akan ... karena yang ketiga harus persis sama dengan yang melewati yang kedua. (O (log (n)))
• Itu O (1) untuk menemukan 1 terakhir karena Anda tahu indeks itu harus pada saat Anda menemukan yang pertama dan kedua.

Jadi, Anda memiliki n, log (n), dan 1 ... O (nlogn)

Sunting: Ups, salahku. Otak saya telah menetapkan bahwa n / 2 adalah logn ... yang jelas tidak (menggandakan nomor pada item masih menggandakan jumlah iterasi pada loop dalam). Ini masih di n ^ 2, tidak menyelesaikan masalah. Yah, setidaknya saya harus menulis beberapa kode :)

Implementasi di Tcl

proc get-triplet {input} {
    for {set first 0} {$first < [string length $input]-2} {incr first} {
        if {[string index $input $first] != 1} {
            continue
        }
        set start [expr {$first + 1}]
        set end [expr {1+ $first + (([string length $input] - $first) /2)}]
        for {set second $start} {$second < $end} {incr second} {
            if {[string index $input $second] != 1} {
                continue
            }
            set last [expr {($second - $first) + $second}]
            if {[string index $input $last] == 1} {
                return [list $first $second $last]
            }
        }
    }
    return {}
}

get-triplet 10101      ;# 0 2 4
get-triplet 10111      ;# 0 2 4
get-triplet 11100000   ;# 0 1 2
get-triplet 0100100100 ;# 1 4 7

Saya pikir saya telah menemukan cara untuk menyelesaikan masalah, tetapi saya tidak dapat membuat bukti formal. Solusi yang saya buat ditulis dalam Java, dan menggunakan penghitung 'n' untuk menghitung berapa banyak daftar / array yang diaksesnya. Jadi n harus kurang dari atau sama dengan stringLength * log (stringLength) jika sudah benar. Saya mencobanya untuk angka 0 hingga 2 ^ 22, dan berhasil.

Dimulai dengan mengulangi string input dan membuat daftar semua indeks yang menyimpan satu. Ini hanya O (n).

Kemudian dari daftar indeks itu memilih INDEX pertama, dan INDEX kedua yang lebih besar dari yang pertama. Kedua indeks ini harus memiliki satu, karena mereka berada dalam daftar indeks. Dari sanaIndex ketiga dapat dihitung. Jika inputString [thirdIndex] adalah 1 maka terhenti.

public static int testString(String input){
//n is the number of array/list accesses in the algorithm
int n=0;

//Put the indices of all the ones into a list, O(n)
ArrayList<Integer> ones = new ArrayList<Integer>();
for(int i=0;i<input.length();i++){
    if(input.charAt(i)=='1'){
        ones.add(i);
    }
}

//If less than three ones in list, just stop
if(ones.size()<3){
    return n;
}

int firstIndex, secondIndex, thirdIndex;
for(int x=0;x<ones.size()-2;x++){
    n++;
    firstIndex = ones.get(x);

    for(int y=x+1; y<ones.size()-1; y++){
        n++;
        secondIndex = ones.get(y);
        thirdIndex = secondIndex*2 - firstIndex;

        if(thirdIndex >= input.length()){
            break;
        }

        n++;
        if(input.charAt(thirdIndex) == '1'){
            //This case is satisfied if it has found three evenly spaced ones
            //System.out.println("This one => " + input);
            return n;
        }
    }
}

return n;

}

catatan tambahan: penghitung n tidak bertambah ketika iterasi atas string input untuk membangun daftar indeks. Operasi ini O (n), jadi tidak akan berpengaruh pada kompleksitas algoritma.

Salah satu jalan masuk ke masalah adalah memikirkan faktor dan bergeser.

Dengan menggeser, Anda membandingkan string yang dan nol dengan versi bergeser itu sendiri. Anda kemudian mengambil yang cocok. Ambil contoh ini bergeser dua:

1010101010
  1010101010
------------
001010101000

1 yang dihasilkan (bitwise ANDed), harus mewakili semua 1 yang ditempatkan secara merata oleh dua. Contoh yang sama digeser oleh tiga:

1010101010
   1010101010
-------------
0000000000000

Dalam hal ini tidak ada 1 yang secara merata berjarak tiga terpisah.

Jadi, apa artinya ini? Nah, Anda hanya perlu menguji shift yang merupakan bilangan prima. Misalnya katakan Anda memiliki dua 1 yang enam terpisah. Anda hanya perlu menguji shift 'dua' dan shift 'tiga' (karena ini membagi enam). Sebagai contoh:

10000010 
  10000010 (Shift by two)
    10000010
      10000010 (We have a match)

10000010
   10000010 (Shift by three)
      10000010 (We have a match)

Jadi, satu-satunya shift yang perlu Anda periksa adalah 2,3,5,7,11,13, dll. Hingga yang paling dekat dengan akar kuadrat dari ukuran string angka.

Hampir dipecahkan?

Saya pikir saya lebih dekat ke solusi. Pada dasarnya:

1. Pindai string untuk 1. Untuk setiap 1 not itu tersisa setelah mengambil modulus dari posisinya. Modulus berkisar dari 1 hingga setengah ukuran string. Ini karena ukuran pemisahan terbesar yang mungkin adalah setengah string. Ini dilakukan dalam O (n ^ 2). TAPI. Hanya moduli prima yang perlu diperiksa sehingga O (n ^ 2 / log (n))
2. Urutkan daftar modulus / sisa agar modulus terbesar pertama, ini dapat dilakukan dalam waktu O (n * log (n)).
3. Carilah tiga moduli / sisanya berturut-turut yang sama.
4. Entah bagaimana mengambil posisi yang!

Saya pikir petunjuk terbesar untuk jawabannya, adalah bahwa algoritma pengurutan tercepat, adalah O (n * log (n)).

SALAH

Langkah 1 salah seperti yang ditunjukkan oleh seorang rekan. Jika kita memiliki 1 di posisi 2,12 dan 102. Kemudian mengambil modulus 10, mereka semua akan memiliki sisa yang sama, namun tidak sama-sama berjarak! Maaf.

Berikut adalah beberapa pemikiran yang, meskipun telah berusaha sebaik mungkin, tampaknya tidak akan membungkus diri mereka menjadi sebuah busur. Namun, mereka mungkin menjadi titik awal yang berguna untuk analisis seseorang.

Pertimbangkan solusi yang diusulkan sebagai berikut, yang merupakan pendekatan yang disarankan beberapa orang, termasuk saya dalam versi sebelumnya dari jawaban ini. :)

1. Potong nol di depan dan di belakang.
2. Pindai string mencari 1.
3. Ketika 1 ditemukan:
   1. Asumsikan bahwa itu adalah solusi tengah 1.
   2. Untuk setiap 1 sebelumnya, gunakan posisi yang disimpannya untuk menghitung posisi yang diantisipasi dari final 1.
   3. Jika posisi yang dihitung adalah setelah akhir string, itu tidak dapat menjadi bagian dari solusi, jadi jatuhkan posisi dari daftar kandidat.
   4. Periksa solusinya.
4. Jika solusinya tidak ditemukan, tambahkan 1 saat ini ke daftar kandidat.
5. Ulangi sampai tidak ada lagi 1 yang ditemukan.

Sekarang pertimbangkan string input string seperti berikut ini, yang tidak akan memiliki solusi:

101
101001
1010010001
101001000100001
101001000100001000001

Secara umum, ini adalah gabungan string k dari bentuk j 0 diikuti oleh 1 untuk j dari nol hingga k-1.

k=2  101
k=3  101001
k=4  1010010001
k=5  101001000100001
k=6  101001000100001000001

Perhatikan bahwa panjang substring adalah 1, 2, 3, dll. Jadi, ukuran masalah n memiliki substring panjang 1 hingga k sedemikian sehingga n = k (k + 1) / 2.

k=2  n= 3  101
k=3  n= 6  101001
k=4  n=10  1010010001
k=5  n=15  101001000100001
k=6  n=21  101001000100001000001

Perhatikan bahwa k juga melacak angka 1 yang harus kita pertimbangkan. Ingatlah bahwa setiap kali kita melihat angka 1, kita perlu mempertimbangkan semua angka 1 yang terlihat sejauh ini. Jadi ketika kita melihat 1 yang kedua, kita hanya mempertimbangkan yang pertama, ketika kita melihat yang ketiga, kita mempertimbangkan kembali yang pertama, ketika kita melihat yang keempat, kita perlu mempertimbangkan yang pertama, dan seterusnya. Pada akhir algoritma, kami telah mempertimbangkan k (k-1) / 2 pasang 1. Sebut itu hal.

k=2  n= 3  p= 1  101
k=3  n= 6  p= 3  101001
k=4  n=10  p= 6  1010010001
k=5  n=15  p=10  101001000100001
k=6  n=21  p=15  101001000100001000001

Hubungan antara n dan p adalah n = p + k.

Proses melalui string membutuhkan O (n) waktu. Setiap kali 1 ditemukan, perbandingan maksimum (k-1) dilakukan. Karena n = k (k + 1) / 2, n> k ** 2, jadi sqrt (n)> k. Ini memberi kita O (n sqrt (n)) atau O (n ** 3/2). Namun perlu dicatat bahwa itu mungkin bukan ikatan yang benar-benar ketat, karena jumlah perbandingan berubah dari 1 hingga maksimum k, itu bukan k sepanjang waktu. Tapi saya tidak yakin bagaimana menjelaskannya dalam matematika.

Masih bukan O (n log (n)). Juga, saya tidak dapat membuktikan input tersebut adalah kasus terburuk, meskipun saya curiga mereka adalah input. Saya pikir pengemasan yang lebih padat dari 1 ke depan menghasilkan pengemasan yang lebih jarang pada akhirnya.

Karena seseorang mungkin masih menganggapnya berguna, inilah kode saya untuk solusi itu di Perl:

#!/usr/bin/perl

# read input as first argument
my $s = $ARGV[0];

# validate the input
$s =~ /^[01]+$/ or die "invalid input string\n";

# strip leading and trailing 0's
$s =~ s/^0+//;
$s =~ s/0+$//;

# prime the position list with the first '1' at position 0
my @p = (0);

# start at position 1, which is the second character
my $i = 1;

print "the string is $s\n\n";

while ($i < length($s)) {
   if (substr($s, $i, 1) eq '1') {
      print "found '1' at position $i\n";
      my @t = ();
      # assuming this is the middle '1', go through the positions
      # of all the prior '1's and check whether there's another '1'
      # in the correct position after this '1' to make a solution
      while (scalar @p) {
         # $p is the position of the prior '1'
         my $p = shift @p;
         # $j is the corresponding position for the following '1'
         my $j = 2 * $i - $p;
         # if $j is off the end of the string then we don't need to
         # check $p anymore
         next if ($j >= length($s));
         print "checking positions $p, $i, $j\n";
         if (substr($s, $j, 1) eq '1') {
            print "\nsolution found at positions $p, $i, $j\n";
            exit 0;
         }
         # if $j isn't off the end of the string, keep $p for next time
         push @t, $p;
      }
      @p = @t;
      # add this '1' to the list of '1' positions
      push @p, $i;
   }
   $i++;
}

print "\nno solution found\n";

Saat memindai 1s, tambahkan posisinya ke Daftar. Saat menambahkan 1 detik dan berturut-turut, bandingkan mereka dengan setiap posisi dalam daftar sejauh ini. Spasi sama dengan currentOne (tengah) - priorOne (kiri). Bit sisi kanan adalah currentOne + spacing. Jika 1, akhirnya.

Daftar yang tumbuh terbalik dengan ruang di antara mereka. Sederhananya, jika Anda memiliki banyak 0s antara 1s (seperti dalam kasus terburuk), daftar 1s Anda yang dikenal akan tumbuh cukup lambat.

using System;
using System.Collections.Generic;

namespace spacedOnes
{
    class Program
    {
        static int[] _bits = new int[8] {128, 64, 32, 16, 8, 4, 2, 1};

        static void Main(string[] args)
        {
            var bytes = new byte[4];
            var r = new Random();
            r.NextBytes(bytes);
            foreach (var b in bytes) {
                Console.Write(getByteString(b));
            }
            Console.WriteLine();
            var bitCount = bytes.Length * 8;
            var done = false;
            var onePositions = new List<int>();
            for (var i = 0; i < bitCount; i++)
            {
                if (isOne(bytes, i)) {
                    if (onePositions.Count > 0) {
                        foreach (var knownOne in onePositions) {
                            var spacing = i - knownOne;
                            var k = i + spacing;
                            if (k < bitCount && isOne(bytes, k)) {
                                Console.WriteLine("^".PadLeft(knownOne + 1) + "^".PadLeft(spacing) + "^".PadLeft(spacing));
                                done = true;
                                break;
                            }
                        }
                    }
                    if (done) {
                        break;
                    }
                    onePositions.Add(i);
                }
            }
            Console.ReadKey();
        }

        static String getByteString(byte b) {
            var s = new char[8];
            for (var i=0; i<s.Length; i++) {
                s[i] = ((b & _bits[i]) > 0 ? '1' : '0');
            }
            return new String(s);
        }

        static bool isOne(byte[] bytes, int i)
        {
            var byteIndex = i / 8;
            var bitIndex = i % 8;
            return (bytes[byteIndex] & _bits[bitIndex]) > 0;
        }
    }
}

Saya pikir saya akan menambahkan satu komentar sebelum memposting solusi naif ke-22 untuk masalah ini. Untuk solusi naif, kita tidak perlu menunjukkan bahwa jumlah 1 dalam string paling banyak adalah O (log (n)), tetapi lebih banyak O (sqrt (n * log (n)).

Pemecah:

def solve(Str):
    indexes=[]
    #O(n) setup
    for i in range(len(Str)):
        if Str[i]=='1':
            indexes.append(i)

    #O((number of 1's)^2) processing
    for i in range(len(indexes)):
        for j in range(i+1, len(indexes)):
                            indexDiff = indexes[j] - indexes[i]
            k=indexes[j] + indexDiff
            if k<len(Str) and Str[k]=='1':
                return True
    return False

Ini pada dasarnya agak mirip dengan ide dan implementasi flybywire, meskipun melihat ke depan, bukan ke belakang.

Pembangun Tali Serakah:

#assumes final char hasn't been added, and would be a 1 
def lastCharMakesSolvable(Str):
    endIndex=len(Str)
    j=endIndex-1
    while j-(endIndex-j) >= 0:
        k=j-(endIndex-j)
        if k >= 0 and Str[k]=='1' and Str[j]=='1':
            return True
        j=j-1
    return False



def expandString(StartString=''):
    if lastCharMakesSolvable(StartString):
        return StartString + '0'
    return StartString + '1'

n=1
BaseStr=""
lastCount=0
while n<1000000:
    BaseStr=expandString(BaseStr)
    count=BaseStr.count('1')
    if count != lastCount:
        print(len(BaseStr), count)
    lastCount=count
    n=n+1

(Dalam pembelaan saya, saya masih dalam tahap pemahaman 'belajar python')

Juga, output yang berpotensi berguna dari bangunan serakah string, ada lompatan yang agak konsisten setelah memukul kekuatan 2 dalam jumlah 1 ... yang saya tidak mau menunggu untuk menyaksikan memukul 2096.

strlength   # of 1's
    1    1
    2    2
    4    3
    5    4
   10    5
   14    8
   28    9
   41    16
   82    17
  122    32
  244    33
  365    64
  730    65
 1094    128
 2188    129
 3281    256
 6562    257
 9842    512
19684    513
29525    1024

Saya akan mencoba menyajikan pendekatan matematika. Ini lebih merupakan awal daripada akhir, sehingga bantuan, komentar, atau bahkan kontradiksi - akan sangat dihargai. Namun, jika pendekatan ini terbukti - algoritme adalah pencarian langsung di string.

1. Dengan jumlah ruang kdan string yang tetap S, pencarian untuk k-spaced-triplet membutuhkan waktu O(n)- Kami hanya menguji untuk setiap 0<=i<=(n-2k)if S[i]==S[i+k]==S[i+2k]. Tes mengambil O(1)dan kami melakukannya di n-kmana kkonstanta, sehingga dibutuhkan O(n-k)=O(n).

2. Mari kita asumsikan ada Proporsi Terbalik antara jumlah 1's dan ruang maksimum yang perlu kita cari. Artinya, Jika ada banyak 1, harus ada triplet dan itu harus cukup padat; Jika hanya ada beberapa 1, Triplet (jika ada) bisa sangat jarang. Dengan kata lain, saya dapat membuktikan bahwa jika saya memiliki cukup 1, triplet seperti itu harus ada - dan semakin banyak yang 1saya miliki, triplet yang lebih padat harus ditemukan. Ini bisa dijelaskan dengan prinsip Pigeonhole - Harapan untuk menguraikan hal ini nanti.

3. Katakanlah ada batas atas kpada kemungkinan jumlah ruang yang harus saya cari. Sekarang, untuk setiap 1terletak di S[i]kita perlu memeriksa 1di S[i-1]dan S[i+1], S[i-2]dan S[i+2], ... S[i-k]dan S[i+k]. Ini berlaku O((k^2-k)/2)=O(k^2)untuk masing-masing 1in S-karena Formula Penjumlahan Seri Gauss . Perhatikan bahwa ini berbeda dari bagian 1 - Saya memiliki ksebagai batas atas untuk jumlah ruang, bukan sebagai ruang konstan.

Kita perlu membuktikan O(n*log(n)). Artinya, kita perlu menunjukkan yang k*(number of 1's)proporsional log(n).

Jika kita bisa melakukan itu, algoritma sepele - untuk setiap 1di Syang indeks i, hanya mencari 1's dari setiap sisi hingga jarak k. Jika dua ditemukan dalam jarak yang sama, kembali idan k. Sekali lagi, bagian yang sulit adalah menemukan kdan membuktikan kebenaran.

Saya akan sangat menghargai komentar Anda di sini - Saya telah berusaha menemukan hubungan antara kdan jumlah 1di papan tulis saya, sejauh ini tidak berhasil.

Anggapan:

Salah, berbicara tentang log (n) jumlah batas atas yang

EDIT:

Sekarang saya menemukan bahwa menggunakan nomor Cantor (jika benar), densitas pada set adalah (2/3) ^ Log_3 (n) (fungsi yang aneh) dan saya setuju, log (n) / n kepadatan adalah untuk kuat.

Jika ini adalah batas atas, ada algoritme yang memecahkan masalah ini dalam setidaknya O (n * (3/2) ^ (log (n) / log (3))) kompleksitas waktu dan O ((3/2) ^ ( log (n) / log (3))) kompleksitas ruang. (periksa jawaban Justice untuk algorhitm)

Ini masih jauh lebih baik daripada O (n ^ 2)

Fungsi ini ((3/2) ^ (log (n) / log (3))) sangat mirip dengan n * log (n) pada pandangan pertama.

Bagaimana saya mendapatkan formula ini?

Memutar nomor Cantors pada string.
Misalkan panjang string adalah 3 ^ p == n
Pada setiap langkah dalam menghasilkan string Cantor Anda menyimpan 2/3 dari jumlah yang ada sebelumnya. Terapkan ini p kali.

Itu berarti (n * ((2/3) ^ p)) -> (((3 ^ p)) * ((2/3) ^ p)) yang tersisa dan setelah penyederhanaan 2 ^ p. Ini berarti 2 ^ p dalam 3 ^ p string -> (3/2) ^ p. Pengganti p = log (n) / log (3) dan dapatkan
((3/2) ^ (log (n) / log (3)))

Bagaimana dengan solusi O (n) sederhana, dengan ruang O (n ^ 2)? (Menggunakan asumsi bahwa semua operator bitwise bekerja di O (1).)

Algoritma pada dasarnya bekerja dalam empat tahap:

Tahap 1: Untuk setiap bit di nomor asli Anda, cari tahu seberapa jauh jaraknya, tetapi pertimbangkan hanya satu arah. (Saya menganggap semua bit dalam arah bit yang paling tidak signifikan.)

Tahap 2: Membalik urutan bit dalam input;

Tahap 3: Jalankan kembali langkah 1 pada input yang terbalik.

Tahap 4: Bandingkan hasil dari Tahap 1 dan Tahap 3. Jika ada bit yang sama spasi di atas DAN di bawah ini, kita harus memiliki hit.

Ingatlah bahwa tidak ada langkah dalam algoritma di atas yang membutuhkan waktu lebih lama dari O (n). ^ _ ^

Sebagai manfaat tambahan, algoritma ini akan menemukan SEMUA yang sama spasi dari nomor SETIAP. Jadi misalnya jika Anda mendapatkan hasil "0x0005" maka ada yang sama spasi di KEDUA 1 dan 3 unit jauhnya

Saya tidak benar-benar mencoba mengoptimalkan kode di bawah ini, tetapi kode C # yang dapat dikompilasi sepertinya berfungsi.

using System;

namespace ThreeNumbers
{
    class Program
    {
        const int uint32Length = 32;

        static void Main(string[] args)
        {
            Console.Write("Please enter your integer: ");
            uint input = UInt32.Parse(Console.ReadLine());

            uint[] distancesLower = Distances(input);
            uint[] distancesHigher = Distances(Reverse(input));

            PrintHits(input, distancesLower, distancesHigher);
        }

        /// <summary>
        /// Returns an array showing how far the ones away from each bit in the input.  Only 
        /// considers ones at lower signifcant bits.  Index 0 represents the least significant bit 
        /// in the input.  Index 1 represents the second least significant bit in the input and so 
        /// on.  If a one is 3 away from the bit in question, then the third least significant bit 
        /// of the value will be sit.
        /// 
        /// As programed this algorithm needs: O(n) time, and O(n*log(n)) space.  
        /// (Where n is the number of bits in the input.)
        /// </summary>
        public static uint[] Distances(uint input)
        {
            uint[] distanceToOnes = new uint[uint32Length];
            uint result = 0;

            //Sets how far each bit is from other ones. Going in the direction of LSB to MSB
            for (uint bitIndex = 1, arrayIndex = 0; bitIndex != 0; bitIndex <<= 1, ++arrayIndex)
            {
                distanceToOnes[arrayIndex] = result;
                result <<= 1;

                if ((input & bitIndex) != 0)
                {
                    result |= 1;
                }
            }

            return distanceToOnes;
        }

        /// <summary>
        /// Reverses the bits in the input.
        /// 
        /// As programmed this algorithm needs O(n) time and O(n) space.  
        /// (Where n is the number of bits in the input.)
        /// </summary>
        /// <param name="input"></param>
        /// <returns></returns>
        public static uint Reverse(uint input)
        {
            uint reversedInput = 0;
            for (uint bitIndex = 1; bitIndex != 0; bitIndex <<= 1)
            {
                reversedInput <<= 1;
                reversedInput |= (uint)((input & bitIndex) != 0 ? 1 : 0);
            }

            return reversedInput;
        }

        /// <summary>
        /// Goes through each bit in the input, to check if there are any bits equally far away in 
        /// the distancesLower and distancesHigher
        /// </summary>
        public static void PrintHits(uint input, uint[] distancesLower, uint[] distancesHigher)
        {
            const int offset = uint32Length - 1;

            for (uint bitIndex = 1, arrayIndex = 0; bitIndex != 0; bitIndex <<= 1, ++arrayIndex)
            {
                //hits checks if any bits are equally spaced away from our current value
                bool isBitSet = (input & bitIndex) != 0;
                uint hits = distancesLower[arrayIndex] & distancesHigher[offset - arrayIndex];

                if (isBitSet && (hits != 0))
                {
                    Console.WriteLine(String.Format("The {0}-th LSB has hits 0x{1:x4} away", arrayIndex + 1, hits));
                }
            }
        }
    }
}

Seseorang mungkin akan berkomentar bahwa untuk jumlah yang cukup besar, operasi bitwise tidak dapat dilakukan dalam O (1). Anda benar. Namun, saya menduga bahwa setiap solusi yang menggunakan penjumlahan, pengurangan, penggandaan, atau pembagian (yang tidak dapat dilakukan dengan bergeser) juga akan memiliki masalah itu.

Di bawah ini solusinya. Mungkin ada beberapa kesalahan kecil di sana-sini, tetapi idenya bagus.

Sunting: Ini bukan n * log (n)

KODE PSEUDO:

foreach character in the string
  if the character equals 1 {         
     if length cache > 0 { //we can skip the first one
        foreach location in the cache { //last in first out kind of order
           if ((currentlocation + (currentlocation - location)) < length string)
              if (string[(currentlocation + (currentlocation - location))] equals 1)
                 return found evenly spaced string
           else
              break;
        }
     }
     remember the location of this character in a some sort of cache.
  }

return didn't find evenly spaced string

Kode C #:

public static Boolean FindThreeEvenlySpacedOnes(String str) {
    List<int> cache = new List<int>();

    for (var x = 0; x < str.Length; x++) {
        if (str[x] == '1') {
            if (cache.Count > 0) {
                for (var i = cache.Count - 1; i > 0; i--) {
                    if ((x + (x - cache[i])) >= str.Length)
                        break;

                    if (str[(x + (x - cache[i]))] == '1')
                        return true;                            
                }
            }
            cache.Add(x);                    
        }
    }

    return false;
}

Bagaimana itu bekerja:

iteration 1:
x
|
101101001
// the location of this 1 is stored in the cache

iteration 2:
 x
 | 
101101001

iteration 3:
a x b 
| | | 
101101001
//we retrieve location a out of the cache and then based on a 
//we calculate b and check if te string contains a 1 on location b

//and of course we store x in the cache because it's a 1

iteration 4:
  axb  
  |||  
101101001

a  x  b  
|  |  |  
101101001


iteration 5:
    x  
    |  
101101001

iteration 6:
   a x b 
   | | | 
101101001

  a  x  b 
  |  |  | 
101101001
//return found evenly spaced string

Jelas kita perlu setidaknya memeriksa tandan triplet pada waktu yang bersamaan, jadi kita perlu memampatkan cek itu entah bagaimana. Saya memiliki algoritma kandidat, tetapi menganalisis kompleksitas waktu berada di luar batas kemampuan * waktu saya.

Bangun sebuah pohon di mana setiap simpul memiliki tiga anak dan setiap simpul berisi jumlah total 1 pada daunnya. Bangun daftar tertaut di atas angka 1 juga. Tetapkan setiap node biaya yang diizinkan sebanding dengan kisaran yang dicakupnya. Selama waktu yang kami habiskan di setiap node sesuai anggaran, kami akan memiliki algoritma O (n lg n).

-

Mulai dari root. Jika kuadrat dari jumlah total 1 di bawahnya kurang dari biaya yang diizinkan, terapkan algoritma naif. Kalau tidak kambuh pada anak-anaknya.

Sekarang kami telah kembali sesuai anggaran, atau kami tahu bahwa tidak ada kembar tiga yang sah yang sepenuhnya terkandung dalam salah satu anak. Karena itu kita harus memeriksa triplet antar-simpul.

Sekarang segalanya menjadi sangat berantakan. Kami pada dasarnya ingin mengulang pada potensi set anak sambil membatasi jangkauan. Segera setelah rentang dibatasi sehingga algoritma naif akan berjalan di bawah anggaran, Anda melakukannya. Nikmati menerapkan ini, karena saya jamin itu akan membosankan. Ada selusin kasus.

-

Alasan saya berpikir bahwa algoritma akan bekerja adalah karena urutan tanpa kembar tiga yang valid tampaknya berganti-ganti antara tandan 1 dan banyak 0. Ini secara efektif membagi ruang pencarian terdekat, dan pohon mengemulasi pemisahan itu.

Waktu menjalankan algoritma tidak jelas sama sekali. Itu bergantung pada sifat non-sepele dari urutan. Jika 1 benar-benar jarang maka algoritma naif akan bekerja sesuai anggaran. Jika angka 1 padat, maka kecocokan harus segera ditemukan. Tetapi jika kerapatan 'tepat' (mis. Dekat ~ n ^ 0,63, yang dapat Anda capai dengan mengatur semua bit pada posisi tanpa angka '2' pada basis 3), saya tidak tahu apakah ini akan bekerja. Anda harus membuktikan bahwa efek pemisahan cukup kuat.

Tidak ada jawaban teoritis di sini, tetapi saya menulis program Java cepat untuk mengeksplorasi perilaku running-time sebagai fungsi dari k dan n, di mana n adalah total panjang bit dan k adalah jumlah 1. Saya dengan beberapa penjawab yang mengatakan bahwa algoritma "biasa" yang memeriksa semua pasangan posisi bit dan mencari bit ke-3, meskipun itu akan membutuhkan O (k ^ 2) dalam kasus terburuk, di kenyataan karena kasus terburuk membutuhkan bitstring yang jarang, adalah O (n ln n).

Pokoknya inilah programnya, di bawah ini. Ini adalah program gaya Monte-Carlo yang menjalankan sejumlah besar percobaan NTRIALS untuk n konstan, dan secara acak menghasilkan bitet untuk rentang nilai-k menggunakan proses Bernoulli dengan kepadatan yang dibatasi antara batas yang dapat ditentukan, dan mencatat waktu berjalan menemukan atau gagal menemukan triplet yang jaraknya sama, waktu diukur dalam langkah-langkah TIDAK dalam waktu CPU. Saya menjalankannya untuk n = 64, 256, 1024, 4096, 16384 * (masih berjalan), pertama uji coba dengan 500000 uji coba untuk melihat nilai k mana yang mengambil waktu berjalan paling lama, kemudian tes lain dengan uji 50.000.000 dengan uji menyempit- kepadatan fokus untuk melihat seperti apa nilai-nilai itu. Waktu berjalan terpanjang bisa terjadi dengan kepadatan sangat jarang (misalnya untuk n = 4096 puncak waktu berjalan berada dalam kisaran k = 16-64, dengan puncak lembut untuk runtime rata-rata pada 4212 langkah @ k = 31, runtime maksimum memuncak pada 5101 langkah @ k = 58). Sepertinya akan mengambil nilai N yang sangat besar untuk langkah kasus O (k ^ 2) terburuk untuk menjadi lebih besar daripada langkah O (n) di mana Anda memindai bitstring untuk menemukan indeks posisi 1.

package com.example.math;

import java.io.PrintStream;
import java.util.BitSet;
import java.util.Random;

public class EvenlySpacedOnesTest {
    static public class StatisticalSummary
    {
        private int n=0;
        private double min=Double.POSITIVE_INFINITY;
        private double max=Double.NEGATIVE_INFINITY;
        private double mean=0;
        private double S=0;

        public StatisticalSummary() {}
        public void add(double x) {
            min = Math.min(min, x);
            max = Math.max(max, x);
            ++n;
            double newMean = mean + (x-mean)/n;
            S += (x-newMean)*(x-mean);
            // this algorithm for mean,std dev based on Knuth TAOCP vol 2
            mean = newMean;
        }
        public double getMax() { return (n>0)?max:Double.NaN; }
        public double getMin() { return (n>0)?min:Double.NaN; }
        public int getCount() { return n; }
        public double getMean() { return (n>0)?mean:Double.NaN; }
        public double getStdDev() { return (n>0)?Math.sqrt(S/n):Double.NaN; } 
        // some may quibble and use n-1 for sample std dev vs population std dev    
        public static void printOut(PrintStream ps, StatisticalSummary[] statistics) {
            for (int i = 0; i < statistics.length; ++i)
            {
                StatisticalSummary summary = statistics[i];
                ps.printf("%d\t%d\t%.0f\t%.0f\t%.5f\t%.5f\n",
                        i,
                        summary.getCount(),
                        summary.getMin(),
                        summary.getMax(),
                        summary.getMean(),
                        summary.getStdDev());
            }
        }
    }

    public interface RandomBernoulliProcess // see http://en.wikipedia.org/wiki/Bernoulli_process
    {
        public void setProbability(double d);
        public boolean getNextBoolean();
    }

    static public class Bernoulli implements RandomBernoulliProcess
    {
        final private Random r = new Random();
        private double p = 0.5;
        public boolean getNextBoolean() { return r.nextDouble() < p; }
        public void setProbability(double d) { p = d; }
    }   
    static public class TestResult {
        final public int k;
        final public int nsteps;
        public TestResult(int k, int nsteps) { this.k=k; this.nsteps=nsteps; } 
    }

    ////////////
    final private int n;
    final private int ntrials;
    final private double pmin;
    final private double pmax;
    final private Random random = new Random();
    final private Bernoulli bernoulli = new Bernoulli();
    final private BitSet bits;
    public EvenlySpacedOnesTest(int n, int ntrials, double pmin, double pmax) {
        this.n=n; this.ntrials=ntrials; this.pmin=pmin; this.pmax=pmax;
        this.bits = new BitSet(n);
    }

    /*
     * generate random bit string
     */
    private int generateBits()
    {
        int k = 0; // # of 1's
        for (int i = 0; i < n; ++i)
        {
            boolean b = bernoulli.getNextBoolean();
            this.bits.set(i, b);
            if (b) ++k;
        }
        return k;
    }

    private int findEvenlySpacedOnes(int k, int[] pos) 
    {
        int[] bitPosition = new int[k];
        for (int i = 0, j = 0; i < n; ++i)
        {
            if (this.bits.get(i))
            {
                bitPosition[j++] = i;
            }
        }
        int nsteps = n; // first, it takes N operations to find the bit positions.
        boolean found = false;
        if (k >= 3) // don't bother doing anything if there are less than 3 ones. :(
        {       
            int lastBitSetPosition = bitPosition[k-1];
            for (int j1 = 0; !found && j1 < k; ++j1)
            {
                pos[0] = bitPosition[j1];
                for (int j2 = j1+1; !found && j2 < k; ++j2)
                {
                    pos[1] = bitPosition[j2];

                    ++nsteps;
                    pos[2] = 2*pos[1]-pos[0];
                    // calculate 3rd bit index that might be set;
                    // the other two indices point to bits that are set
                    if (pos[2] > lastBitSetPosition)
                        break;
                    // loop inner loop until we go out of bounds

                    found = this.bits.get(pos[2]);
                    // we're done if we find a third 1!
                }
            }
        }
        if (!found)
            pos[0]=-1;
        return nsteps;
    }

    /*
     * run an algorithm that finds evenly spaced ones and returns # of steps.
     */
    public TestResult run()
    {
        bernoulli.setProbability(pmin + (pmax-pmin)*random.nextDouble());
        // probability of bernoulli process is randomly distributed between pmin and pmax

        // generate bit string.
        int k = generateBits();
        int[] pos = new int[3];
        int nsteps = findEvenlySpacedOnes(k, pos);
        return new TestResult(k, nsteps); 
    }

    public static void main(String[] args)
    {
        int n;
        int ntrials;
        double pmin = 0, pmax = 1;
        try {
            n = Integer.parseInt(args[0]);
            ntrials = Integer.parseInt(args[1]);
            if (args.length >= 3)
                pmin = Double.parseDouble(args[2]);
            if (args.length >= 4)
                pmax = Double.parseDouble(args[3]);
        }
        catch (Exception e)
        {
            System.out.println("usage: EvenlySpacedOnesTest N NTRIALS [pmin [pmax]]");
            System.exit(0);
            return; // make the compiler happy
        }

        final StatisticalSummary[] statistics;
        statistics=new StatisticalSummary[n+1];
        for (int i = 0; i <= n; ++i)
        {
            statistics[i] = new StatisticalSummary();
        }

        EvenlySpacedOnesTest test = new EvenlySpacedOnesTest(n, ntrials, pmin, pmax);
        int printInterval=100000;
        int nextPrint = printInterval;
        for (int i = 0; i < ntrials; ++i)
        {
            TestResult result = test.run();
            statistics[result.k].add(result.nsteps);
            if (i == nextPrint)
            {
                System.err.println(i);
                nextPrint += printInterval;
            }
        }
        StatisticalSummary.printOut(System.out, statistics);
    }
}

# <algorithm>
def contains_evenly_spaced?(input)
  return false if input.size < 3
  one_indices = []
  input.each_with_index do |digit, index|
    next if digit == 0
    one_indices << index
  end
  return false if one_indices.size < 3
  previous_indexes = []
  one_indices.each do |index|
    if !previous_indexes.empty?
      previous_indexes.each do |previous_index|
        multiple = index - previous_index
        success_index = index + multiple
        return true if input[success_index] == 1
      end
    end
    previous_indexes << index
  end
  return false
end
# </algorithm>

def parse_input(input)
  input.chars.map { |c| c.to_i }
end

Saya mengalami masalah dengan skenario terburuk dengan jutaan digit. Fuzzing dari /dev/urandomdasarnya memberi Anda O (n), tapi saya tahu kasus terburuk lebih buruk dari itu. Aku tidak tahu seberapa parahnya. Untuk yang kecil n, itu sepele untuk menemukan input di sekitar 3*n*log(n), tetapi sangat sulit untuk membedakan mereka dari beberapa urutan pertumbuhan lain untuk masalah khusus ini.

Adakah yang bisa mengerjakan input kasus terburuk menghasilkan string dengan panjang lebih besar dari katakanlah, seratus ribu?

Adaptasi dari algoritma Rabin-Karp dapat dilakukan untuk Anda. Kompleksitasnya adalah 0 (n) sehingga dapat membantu Anda.

Lihatlah http://en.wikipedia.org/wiki/Rabin-Karp_string_search_algorithm

Mungkinkah ini solusi? Saya ', tidak yakin apakah itu O (nlogn) tetapi menurut saya itu lebih baik daripada O (n²) karena satu-satunya cara untuk tidak menemukan triple adalah distribusi bilangan prima.

Ada ruang untuk perbaikan, yang kedua ditemukan 1 bisa menjadi yang pertama berikutnya 1. Juga tidak ada pengecekan kesalahan.

#include <iostream>

#include <string>

int findIt(std::string toCheck) {
    for (int i=0; i<toCheck.length(); i++) {
        if (toCheck[i]=='1') {
            std::cout << i << ": " << toCheck[i];
            for (int j = i+1; j<toCheck.length(); j++) {
                if (toCheck[j]=='1' && toCheck[(i+2*(j-i))] == '1') {
                    std::cout << ", " << j << ":" << toCheck[j] << ", " << (i+2*(j-i)) << ":" << toCheck[(i+2*(j-i))] << "    found" << std::endl;
                    return 0;
                }
            }
        }
    }
    return -1;
}

int main (int agrc, char* args[]) {
    std::string toCheck("1001011");
    findIt(toCheck);
    std::cin.get();
    return 0;
}

Saya pikir algoritma ini memiliki kompleksitas O (n log n) (C ++, DevStudio 2k5). Sekarang, saya tidak tahu detail tentang bagaimana menganalisis suatu algoritma untuk menentukan kerumitannya, jadi saya telah menambahkan beberapa informasi pengumpulan metrik ke kode. Kode menghitung jumlah tes yang dilakukan pada urutan 1 dan 0 untuk setiap input yang diberikan (mudah-mudahan, saya belum membuat banyak algoritma). Kita dapat membandingkan jumlah tes aktual terhadap nilai O dan melihat apakah ada korelasi.

#include <iostream>
using namespace std;

bool HasEvenBits (string &sequence, int &num_compares)
{
  bool
    has_even_bits = false;

  num_compares = 0;

  for (unsigned i = 1 ; i <= (sequence.length () - 1) / 2 ; ++i)
  {
    for (unsigned j = 0 ; j < sequence.length () - 2 * i ; ++j)
    {
      ++num_compares;
      if (sequence [j] == '1' && sequence [j + i] == '1' && sequence [j + i * 2] == '1')
      {
        has_even_bits = true;
        // we could 'break' here, but I want to know the worst case scenario so keep going to the end
      }
    }
  }

  return has_even_bits;
}

int main ()
{
  int
    count;

  string
    input = "111";

  for (int i = 3 ; i < 32 ; ++i)
  {
    HasEvenBits (input, count);
    cout << i << ", " << count << endl;
    input += "0";
  }
}

Program ini menghasilkan jumlah pengujian untuk setiap panjang string hingga 32 karakter. Inilah hasilnya:

 n  Tests  n log (n)
=====================
 3     1     1.43
 4     2     2.41
 5     4     3.49
 6     6     4.67
 7     9     5.92
 8    12     7.22
 9    16     8.59
10    20    10.00
11    25    11.46
12    30    12.95
13    36    14.48
14    42    16.05
15    49    17.64
16    56    19.27
17    64    20.92
18    72    22.59
19    81    24.30
20    90    26.02
21   100    27.77
22   110    29.53
23   121    31.32
24   132    33.13
25   144    34.95
26   156    36.79
27   169    38.65
28   182    40.52
29   196    42.41
30   210    44.31
31   225    46.23

Saya telah menambahkan nilai 'n log n' juga. Plot ini menggunakan alat grafik pilihan Anda untuk melihat korelasi antara dua hasil. Apakah analisis ini mencakup semua nilai n? Saya tidak tahu