O (nlogn) Algorithm - Encuentra tres espacios iguales dentro de una cadena binaria

Ayer tuve esta pregunta en una prueba de Algoritmos, y no puedo encontrar la respuesta. Me está volviendo loco, porque valía unos 40 puntos. Supongo que la mayoría de la clase no lo resolvió correctamente, porque no he encontrado una solución en las últimas 24 horas.

Dada una cadena binaria arbitraria de longitud n, encuentre tres espaciados uniformemente dentro de la cadena si existen. Escriba un algoritmo que resuelva esto en tiempo O (n * log (n)).

Así que las cadenas como estas tienen tres que están "espaciadas uniformemente": 11100000, 0100100100

editar: es un número aleatorio, por lo que debería poder funcionar para cualquier número. Los ejemplos que di fueron para ilustrar la propiedad "uniformemente espaciada". Entonces 1001011 es un número válido. Con 1, 4 y 7 que son espaciados uniformemente.

¡Finalmente! Siguiendo los leads en la respuesta de sdcvvc , lo tenemos: ¡el algoritmo O (n log n) para el problema! También es simple, después de que lo entiendes. Los que adivinaron FFT tenían razón.

El problema: se nos da una cadena binaria Sde longitud n , y queremos encontrar tres 1s espaciados uniformemente en ella. Por ejemplo, Spuede ser 110110010, donde n = 9. Ha espaciado uniformemente 1s en las posiciones 2, 5 y 8.

1. Escanee de Sizquierda a derecha y haga una lista Lde posiciones de 1. Para lo S=110110010anterior, tenemos la lista L = [1, 2, 4, 5, 8]. Este paso es O (n). El problema ahora es encontrar una progresión aritmética de longitud 3 en L, es decir, encontrar distintas a, b, c en Ltal que ba = cb , o equivalentemente a + c = 2b . Para el ejemplo anterior, queremos encontrar la progresión (2, 5, 8).

2. Haz un polinomio p con términos x ^k para cada k in L. Para el ejemplo anterior, hacemos el polinomio p (x) = (x + x ² + x ⁴ + x ⁵ + x ⁸ ) . Este paso es O (n).

3. Encuentre el polinomio q= p ² , usando la Transformada rápida de Fourier . Para el ejemplo anterior, obtenemos el polinomio q (x) = x ¹⁶ + 2x ¹³ + 2x ¹² + 3x ¹⁰ + 4x ⁹ + x ⁸ + 2x ⁷ + 4x ⁶ + 2x ⁵ + x ⁴ + 2x ³ + x ² . Este paso es O (n log n).

4. Ignore todos los términos, excepto los correspondientes a x ^2k para algunos k en L. Para el ejemplo anterior, obtenemos los términos x ¹⁶ , 3x ¹⁰ , x ⁸ , x ⁴ , x ² . Este paso es O (n), si decide hacerlo.

Aquí está el punto crucial: el coeficiente de cualquier x ^2b para b en Les precisamente el número de pares (a, c) en Ltal que a + c = 2b . [CLRS, ej. 30.1-7] Uno de esos pares es (b, b) siempre (entonces el coeficiente es al menos 1), pero si existe algún otro par (a, c) , entonces el coeficiente es al menos 3, de (a, c ) y (c, a) . Para el ejemplo anterior, tenemos el coeficiente de x ¹⁰ para ser 3 precisamente por el AP (2,5,8). (Estos coeficientes x ^2bsiempre serán números impares, por las razones anteriores. Y todos los demás coeficientes en q siempre serán pares).

Entonces, el algoritmo es mirar los coeficientes de estos términos x ^2b , y ver si alguno de ellos es mayor que 1. Si no hay ninguno, entonces no hay 1s espaciados uniformemente. Si no es un b en Lpara el que el coeficiente de x ^2b es mayor que 1, entonces sabemos que hay algún par (a, c) - que no sea (b, b) - para el que a + c = 2b . Para encontrar el par real, simplemente intentamos cada a in L(la c correspondiente sería 2b-a ) y vemos si hay un 1 en la posición 2b-a in S. Este paso es O (n).

Eso es todo amigos.

Uno podría preguntarse: ¿necesitamos usar FFT? Muchas respuestas, como beta , flybywire y rsp , sugieren que el enfoque que verifica cada par de 1s y ve si hay un 1 en la "tercera" posición, podría funcionar en O (n log n), según la intuición que si hay demasiados 1s, encontraríamos un triple fácilmente, y si hay muy pocos 1s, verificar todos los pares lleva poco tiempo. Desafortunadamente, aunque esta intuición es correcta y el enfoque simple es mejor que O (n ² ), no es significativamente mejor. Como en la respuesta de sdcvvc , podemos tomar el "conjunto tipo Cantor" de cadenas de longitud n = 3 ^k, con 1s en las posiciones cuya representación ternaria tiene solo 0s y 2s (no 1s). Dicha cadena tiene 2 ^k = n ^{(log 2) / (log 3)} ≈ n ^0.63 unos en ella y no 1s espaciados uniformemente, por lo que verificar todos los pares sería del orden del cuadrado del número de 1s: eso es 4 ^k ≈ n ^1.26 que desafortunadamente es asintóticamente mucho más grande que (n log n). De hecho, el peor de los casos es aún peor: Leo Moser en 1953 construyó (efectivamente) tales cadenas que tienen n ^{1-c / √ (log n)} 1s en ellas pero no 1s espaciadas uniformemente, lo que significa que en tales cadenas, lo simple el enfoque tomaría Θ (n ^{2-2c / √ (log n)} )- Sólo una pequeña poco mejor que Θ (n ² ) , es sorprendente!

Aproximadamente el número máximo de 1s en una cadena de longitud n sin 3 espaciados uniformemente (lo que vimos arriba era al menos n ^0.63 de la construcción fácil de tipo Cantor, y al menos n ^{1-c / √ (log n)} con Construcción de Moser) - esto es OEIS A003002 . También se puede calcular directamente a partir de OEIS A065825 como el k tal que A065825 (k) ≤ n <A065825 (k + 1). Escribí un programa para encontrarlos, y resulta que el algoritmo codicioso no da la cadena más larga. Por ejemplo, para n = 9, podemos obtener 5 1s (110100011) pero el codicioso da solo 4 (110110000), para n= 26 podemos obtener 11 1s (11001010001000010110001101) pero el codicioso da sólo 8 (11011000011011000000000000), y para n = 74 podemos obtener 22 1s (11000010110001000001011010001000000000000000010001011010000010001101000011) pero el codicioso sólo da 16 (11011000011011000000000000011011000011011000000000000000000000000000000000). Sin embargo, están de acuerdo en bastantes lugares hasta 50 (por ejemplo, todos de 38 a 50). Como dicen las referencias de OEIS, parece que Jaroslaw Wroblewski está interesado en esta pregunta, y mantiene un sitio web sobre estos conjuntos que no promedian . Los números exactos se conocen solo hasta 194.

Su problema se llama PROMEDIO en este documento (1999):

Un problema es 3SUM-hard si hay una reducción sub-cuadrática del problema 3SUM: Dado un conjunto A de n enteros, ¿hay elementos a, b, c en A tales que a + b + c = 0? No se sabe si AVERAGE es 3SUM-hard. Sin embargo, hay una reducción simple de tiempo lineal de PROMEDIO a 3SUM, cuya descripción omitimos.

Wikipedia :

Cuando los enteros están en el rango [−u ... u], 3SUM puede resolverse en el tiempo O (n + u lg u) representando S como un vector de bits y realizando una convolución usando FFT.

Esto es suficiente para resolver tu problema :).

Lo que es muy importante es que O (n log n) es la complejidad en términos de número de ceros y unos, no el recuento de unos (que podría darse como una matriz, como [1,5,9,15]). Comprobar si un conjunto tiene una progresión aritmética, términos de número de 1, es difícil, y según ese documento a partir de 1999 no se conoce un algoritmo más rápido que O (n ² ), y se conjetura que no existe. Todos los que no tienen esto en cuenta están intentando resolver un problema abierto.

Otra información interesante, mayormente irreverente:

Límite inferior:

Un límite inferior fácil es un conjunto tipo Cantor (números 1..3 ^ n-1 que no contienen 1 en su expansión ternaria); su densidad es n ^ (log_3 2) (circa 0.631). Entonces, verificar si el conjunto no es demasiado grande y luego verificar todos los pares no es suficiente para obtener O (n log n). Tienes que investigar la secuencia más inteligente. Aquí se cita un límite inferior mejor : es n ^{1-c / (log (n)) ^ (1/2)} . Esto significa que el conjunto de Cantor no es óptimo.

Límite superior: mi antiguo algoritmo:

Se sabe que para n grande, un subconjunto de {1,2, ..., n} que no contiene progresión aritmética tiene a lo sumo n / (log n) ^ (1/20) elementos. El artículo Sobre triples en progresión aritmética demuestra más: el conjunto no puede contener más de n * 2 ²⁸ * (log log n / log n) ^1/2 elementos. Por lo tanto, puede verificar si se logra ese límite y, de lo contrario, verificar ingenuamente los pares. Este es el algoritmo O (n ² * log log n / log n), más rápido que O (n ² ). Desafortunadamente "On triples ..." está en Springer, pero la primera página está disponible, y la exposición de Ben Green está disponible aquí , página 28, teorema 24.

Por cierto, los documentos son de 1999, el mismo año que el primero que mencioné, así que probablemente es por eso que el primero no menciona ese resultado.

Esta no es una solución, sino una línea de pensamiento similar a lo que Olexiy estaba pensando.

Estaba jugando con la creación de secuencias con el número máximo de unos, y todos son bastante interesantes, obtuve hasta 125 dígitos y aquí están los primeros 3 números que encontré al intentar insertar tantos bits '1' como sea posible:

• 11011000011011000000000000001101100001101100000000000000000000000000000000000000000110110000110110000000000000011011000011011
• 10110100010110100000000000010110100010110100000000000000000000000000000000000000000101101000101101000000000000101101000101101
• 10011001010011001000000000010011001010011001000000000000000000000000000000000000010011001010011001000000000010011001010011001

Tenga en cuenta que todos son fractales (no es demasiado sorprendente dadas las restricciones). Puede haber algo en pensar hacia atrás, tal vez si la cadena no es un fractal con una característica, ¿entonces debe tener un patrón repetitivo?

Gracias a beta por el mejor término para describir estos números.

Actualización: Por desgracia, parece que el patrón se rompe al comenzar con una cadena inicial lo suficientemente grande, como: 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

Sospecho que un enfoque simple que se parece a O (n ^ 2) en realidad producirá algo mejor, como O (n ln (n)). Las secuencias que tardan más en probarse (para cualquier n dado) son las que no contienen tríos, y eso impone restricciones severas en el número de 1 que puede estar en la secuencia.

Se me ocurrieron algunos argumentos para agitar las manos, pero no he podido encontrar una prueba ordenada. Voy a apuñalar en la oscuridad: la respuesta es una idea muy inteligente que el profesor ha sabido durante tanto tiempo que parece obvio, pero es demasiado difícil para los estudiantes. (O eso o dormiste en la conferencia que lo cubrió).

Revisión: 2009-10-17 23:00

He ejecutado esto en grandes cantidades (como cadenas de 20 millones) y ahora creo que este algoritmo no es O (n logn). A pesar de eso, es una implementación lo suficientemente genial y contiene una serie de optimizaciones que hacen que funcione realmente rápido. Evalúa todos los arreglos de cadenas binarias de 24 dígitos o menos en menos de 25 segundos.

He actualizado el código para incluir la 0 <= L < M < U <= X-1observación de hoy.

Original

Esto es, en concepto, similar a otra pregunta que respondí . Ese código también analizó tres valores en una serie y determinó si un triplete cumplía una condición. Aquí hay un código C # adaptado de eso:

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

Las principales diferencias son:

1. Búsqueda exhaustiva de soluciones
   Este código genera un conjunto poderoso de datos para encontrar la entrada más difícil de resolver para este algoritmo.
2. Todas las soluciones versus las más difíciles de resolver
   El código de la pregunta anterior generó todas las soluciones utilizando un generador de Python. Este código solo muestra lo más difícil para cada longitud de patrón.
3. Algoritmo de puntuación
   Este código verifica la distancia desde el elemento medio hasta su borde izquierdo y derecho. El código de Python probó si una suma estaba por encima o por debajo de 0.
4. Convergencia en un candidato
   El código actual funciona desde el medio hacia el borde para encontrar un candidato. El código en el problema anterior funcionó desde los bordes hacia el medio. Este último cambio ofrece una gran mejora en el rendimiento.
5. Uso de grupos pares e impares En
   base a las observaciones al final de este artículo, el código busca pares de números pares de pares de números impares para encontrar L y U, manteniendo M fijo. Esto reduce el número de búsquedas mediante el cálculo previo de la información. En consecuencia, el código usa dos niveles de indirección en el bucle principal de FindCandidate y requiere dos llamadas a FindCandidate para cada elemento intermedio: una para números pares y otra para números impares.

La idea general es trabajar en índices, no en la representación en bruto de los datos. Calcular un conjunto donde aparecen los 1 permite que el algoritmo se ejecute en el tiempo proporcional al número de 1 en los datos en lugar de en el tiempo proporcional a la longitud de los datos. Esta es una transformación estándar: cree una estructura de datos que permita una operación más rápida mientras mantiene el problema equivalente.

Los resultados están desactualizados: eliminados.

Editar: 2009-10-16 18:48

En los datos de yx, a los que se les da cierta credibilidad en las otras respuestas como representativos de datos duros para calcular, obtengo estos resultados ... los eliminé. Están desactualizados.

Señalaría que estos datos no son los más difíciles para mi algoritmo, por lo que creo que la suposición de que los fractales de yx son los más difíciles de resolver es errónea. El peor de los casos para un algoritmo en particular, espero, dependerá del algoritmo en sí mismo y probablemente no será consistente en diferentes algoritmos.

Editar: 2009-10-17 13:30

Más observaciones sobre esto.

Primero, convierta la cadena de 0 y 1 en una matriz de índices para cada posición de los 1. Digamos que la longitud de esa matriz A es X. Entonces el objetivo es encontrar

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

tal que

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

o

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

Como A [L] y A [U] suman un número par, no pueden ser (par, impar) o (impar, par). La búsqueda de una coincidencia podría mejorarse dividiendo A [] en grupos pares e impares y buscando coincidencias en A [M] en los grupos de candidatos pares e impares.

Sin embargo, creo que es más una optimización del rendimiento que una mejora algorítmica. El número de comparaciones debería disminuir, pero el orden del algoritmo debería ser el mismo.

Editar 2009-10-18 00:45

Sin embargo, se me ocurre otra optimización, en la misma línea que separar a los candidatos en pares e impares. Como los tres índices tienen que agregarse a un múltiplo de 3 (a, a + x, a + 2x - mod 3 es 0, independientemente de a y x), puede separar L, M y U en sus valores de mod 3 :

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

De hecho, podría combinar esto con la observación par / impar y separarlos en sus valores mod 6:

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

y así. Esto proporcionaría una mayor optimización del rendimiento, pero no una aceleración algorítmica.

No pude encontrar la solución todavía :(, pero tengo algunas ideas.

¿Qué pasa si partimos de un problema inverso: construimos una secuencia con el número máximo de 1s y SIN tríos espaciados uniformemente? Si puede probar que el número máximo de 1s es o (n), puede mejorar su estimación iterando solo a través de la lista de 1s solamente.

Esto puede ayudar ...

Este problema se reduce a lo siguiente:

Dada una secuencia de enteros positivos, encuentre una subsecuencia contigua dividida en un prefijo y un sufijo de tal manera que la suma del prefijo de la subsecuencia sea igual a la suma del sufijo de la subsecuencia.

Por ejemplo, dada una secuencia de [ 3, 5, 1, 3, 6, 5, 2, 2, 3, 5, 6, 4 ], encontraríamos una subsecuencia de [ 3, 6, 5, 2, 2]con un prefijo de [ 3, 6 ]suma de prefijo de 9y un sufijo de [ 5, 2, 2 ]con suma de sufijo de 9.

La reducción es la siguiente:

Dada una secuencia de ceros y unos, y comenzando en el extremo izquierdo, continúe moviéndose hacia la derecha. Cada vez que se encuentre otro, registre el número de movimientos desde que se encontró el anterior y agregue ese número a la secuencia resultante.

Por ejemplo, dada una secuencia de [ 0, 1, 1, 0, 0, 1, 0, 0, 0, 1 0 ], encontraríamos la reducción de [ 1, 3, 4]. A partir de esta reducción, calculamos la subsecuencia contigua de [ 1, 3, 4], el prefijo de [ 1, 3]con suma de 4y el sufijo de [ 4 ]con suma de 4.

Esta reducción puede calcularse en O(n).

Desafortunadamente, no estoy seguro de a dónde ir desde aquí.

Para el tipo de problema simple (es decir, busca tres "1" con solo (es decir, cero o más) "0" entre ellos), es bastante simple: puede dividir la secuencia en cada "1" y buscar dos subsecuencias adyacentes que tengan la misma longitud (la segunda subsecuencia no es la última, por supuesto). Obviamente, esto se puede hacer en O (n) tiempo.

Para la versión más compleja (es decir, busca un índice i y una brecha g > 0 tal que s[i]==s[i+g]==s[i+2*g]=="1"), no estoy seguro, si existe una solución O (n log n) , ya que posiblemente haya trillizos O (n²) que tienen esta propiedad (piense en una cadena de todos, hay aproximadamente n² / 2 de estos tripletes). Por supuesto, solo está buscando uno de estos, pero actualmente no tengo idea de cómo encontrarlo ...

Una pregunta divertida, pero una vez que te das cuenta de que el patrón real entre dos '1' no importa, el algoritmo se convierte en:

• escanear buscar un '1'
• comenzando desde la siguiente exploración de posición para otro '1' (hasta el final de la matriz menos la distancia desde el primer '1' actual o de lo contrario el 3er '1' estaría fuera de límites)
• si en la posición del segundo '1' más la distancia al primer 1 'se encuentra un tercer' 1 ', tenemos espacios iguales.

En código, JTest fashion (tenga en cuenta que este código no está escrito para ser más eficiente y agregué algunos println para ver qué sucede).

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

Pensé en un enfoque de divide y vencerás que podría funcionar.

Primero, en el preprocesamiento debe insertar todos los números de menos de la mitad de su tamaño de entrada ( n / 3) en una lista.

Dada una cadena: 0000010101000100(tenga en cuenta que este ejemplo en particular es válido)

Inserte todos los primos (y 1) del 1 al (16/2) en una lista: {1, 2, 3, 4, 5, 6, 7}

Luego divídalo por la mitad:

100000101 01000100

Siga haciendo esto hasta llegar a cadenas de tamaño 1. Para todas las cadenas de tamaño uno con un 1 en ellas, agregue el índice de la cadena a la lista de posibilidades; de lo contrario, devuelve -1 por falla.

También deberá devolver una lista de distancias de separación aún posibles, asociadas con cada índice inicial. (Comience con la lista que hizo arriba y elimine los números a medida que avanza) Aquí, una lista vacía significa que solo está tratando con un 1 y, por lo tanto, cualquier espacio es posible en este punto; de lo contrario, la lista incluye espacios que deben descartarse.

Continuando con el ejemplo anterior:

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

En el primer paso combinado, tenemos ocho conjuntos de dos ahora. En el primero, tenemos la posibilidad de un conjunto, pero aprendemos que el espacio entre 1 es imposible debido a que el otro cero está allí. Entonces devolvemos 0 (para el índice) y {2,3,4,5,7} por el hecho de que el espaciado entre 1 es imposible. En el segundo, no tenemos nada y, por lo tanto, devuelve -1. En el tercero tenemos una coincidencia sin espacios eliminados en el índice 5, así que devuelve 5, {1,2,3,4,5,7}. En el cuarto par devolvemos 7, {1,2,3,4,5,7}. En el quinto, devuelve 9, {1,2,3,4,5,7}. En el sexto, devuelve -1. En el séptimo, devuelve 13, {1,2,3,4,5,7}. En el octavo, devuelve -1.

Combinando nuevamente en cuatro conjuntos de cuatro, tenemos:

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

Combinando en conjuntos de ocho:

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

Combinando en un conjunto de dieciséis:

10000101 01000100

A medida que avanzamos, seguimos comprobando todas las posibilidades hasta ahora. Hasta este paso, hemos dejado cosas que iban más allá del final de la cadena, pero ahora podemos verificar todas las posibilidades.

Básicamente, verificamos el primer 1 con espacios de 5 y 7, y encontramos que no se alinean con los 1. (Tenga en cuenta que cada verificación es CONSTANTE, no lineal). Luego verificamos la segunda (índice 5) con espacios de 2, 3, 4, 5, 6 y 7, o lo haríamos, pero podemos detenernos en 2 desde eso realmente coincide.

¡Uf! Ese es un algoritmo bastante largo.

No sé 100% si es O (n log n) debido al último paso, pero todo lo que hay hasta allí definitivamente es O (n log n) por lo que puedo decir. Volveré a esto más tarde e intentaré refinar el último paso.

EDITAR: Cambié mi respuesta para reflejar el comentario de Welbog. Lo siento por el error. Escribiré un pseudocódigo más tarde, también, cuando tenga un poco más de tiempo para descifrar lo que escribí nuevamente. ;-)

Daré mi conjetura aquí, y dejaré que aquellos que son mejores calculando la complejidad me ayuden a saber cómo funciona mi algoritmo en cuanto a la notación O

1. cadena binaria dada 0000010101000100 (como ejemplo)
2. cabeza de cultivo y cola de ceros -> 00000 101010001 00
3. obtenemos 101010001 del cálculo anterior
4. compruebe si el bit del medio es 'uno', si es verdadero, se encontraron válidos tres 'unos' espaciados uniformemente (solo si el número de bits es impar)
5. correlativamente, si el número de bits recortado restante está incluso numerado, la cabeza y la cola 'uno' no pueden ser parte de 'uno' espaciado uniformemente,
6. usamos 1010100001 como ejemplo (con un 'cero' adicional para convertirlo en un número par recortado), en este caso necesitamos recortar nuevamente, luego se convierte en -> 10101 00001
7. obtenemos 10101 del cálculo anterior, y verificamos el bit medio, y encontramos el bit uniformemente espaciado nuevamente

No tengo idea de cómo calcular la complejidad para esto, ¿alguien puede ayudarme?

editar: agregue un código para ilustrar mi idea

edit2: intenté compilar mi código y encontré algunos errores importantes, solucionado

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

Se me ocurrió algo como esto:

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

Esto está inspirado en andycjw.

1. Truncar los ceros.
2. Si es así, pruebe dos subcadenas 0 - (len-2) (omita el último carácter) y desde 1 - (len-1) (omita el primer carácter)
3. Si no es así, si el personaje del medio es uno, entonces tenemos éxito. De lo contrario, divida la cuerda en el midle sin el elemento midle y verifique ambas partes.

En cuanto a la complejidad, esto podría ser O (nlogn) ya que en cada recursión estamos dividiendo por dos.

Espero eso ayude.

Ok, voy a dar otra puñalada al problema. Creo que puedo probar un algoritmo O (n log (n)) que es similar a los ya discutidos mediante el uso de un árbol binario equilibrado para almacenar distancias entre 1. Este enfoque se inspiró en la observación de Justice sobre reducir el problema a una lista de distancias entre los 1's.

¿Podríamos escanear la cadena de entrada para construir un árbol binario equilibrado alrededor de la posición de 1 de manera que cada nodo almacene la posición del 1 y cada borde esté etiquetado con la distancia al 1 adyacente para cada nodo secundario. Por ejemplo:

10010001 gives the following tree

      3
     / \
  2 /   \ 3
   /     \
  0       7

Esto se puede hacer en O (n log (n)) ya que, para una cadena de tamaño n, cada inserción toma O (log (n)) en el peor de los casos.

Entonces, el problema es buscar en el árbol para descubrir si, en cualquier nodo, hay una ruta desde ese nodo a través del elemento secundario izquierdo que tiene la misma distancia que un camino a través del elemento secundario derecho. Esto puede hacerse recursivamente en cada subárbol. Al fusionar dos subárboles en la búsqueda, debemos comparar las distancias de los caminos en el subárbol izquierdo con las distancias de los caminos en el derecho. Dado que el número de rutas en un subárbol será proporcional a log (n), y el número de nodos es n, creo que esto se puede hacer en el tiempo O (n log (n)).

¿Yo me perdí algo?

Esto parecía un problema divertido, así que decidí probarlo.

Estoy asumiendo que 111000001 encontraría los primeros 3 y tendría éxito. Esencialmente, el número de ceros después del 1 es lo importante, ya que 0111000 es el mismo que 111000 según su definición. Una vez que encuentre dos casos de 1, el siguiente 1 encontrado completa la trilogía.

Aquí está en 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

Este es un primer intento, así que estoy seguro de que podría escribirse de manera más limpia. Enumere los casos en los que este método falla a continuación.

Supongo que la razón por la que esto es nlog (n) se debe a lo siguiente:

• Para encontrar el 1 que es el comienzo del triplete, debe verificar los caracteres (n-2). Si no lo ha encontrado en ese momento, no lo hará (caracteres n-1 yn no pueden iniciar un triplete) (O (n))
• Para encontrar el segundo 1 que es la parte del triplete (iniciado por el primero), debe verificar m / 2 (m = nx, donde x es el desplazamiento de los primeros 1) caracteres. Esto se debe a que, si no ha encontrado el segundo 1 en el momento en que está a la mitad del primero hasta el final, no lo hará ... ya que el tercer 1 debe estar exactamente a la misma distancia que el segundo. (O (log (n)))
• Es O (1) para encontrar el último 1, ya que conoce el índice que debe estar en el momento en que encuentre el primero y el segundo.

Entonces, tienes n, log (n) y 1 ... O (nlogn)

Editar: Vaya, mi mal. Mi cerebro tenía que establecer que n / 2 era logn ... lo que obviamente no lo es (duplicar el número de elementos todavía duplica el número de iteraciones en el bucle interno). Esto todavía está en n ^ 2, sin resolver el problema. Bueno, al menos tengo que escribir un código :)

Implementación en 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

Creo que he encontrado una manera de resolver el problema, pero no puedo construir una prueba formal. La solución que hice está escrita en Java, y utiliza un contador 'n' para contar cuántos accesos a la lista / matriz tiene. Entonces n debería ser menor o igual que stringLength * log (stringLength) si es correcto. Lo probé para los números del 0 al 2 ^ 22, y funciona.

Comienza iterando sobre la cadena de entrada y haciendo una lista de todos los índices que contienen uno. Esto es solo O (n).

Luego, de la lista de índices, elige un firstIndex y un secondIndex que es mayor que el primero. Estos dos índices deben contener unos, porque están en la lista de índices. A partir de ahí, se puede calcular el tercer índice. Si inputString [thirdIndex] es un 1, entonces se detiene.

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;

}

nota adicional: el contador n no se incrementa cuando itera sobre la cadena de entrada para construir la lista de índices. Esta operación es O (n), por lo que no tendrá un efecto en la complejidad del algoritmo de todos modos.

Una de las vías del problema es pensar en factores y cambios.

Con el desplazamiento, compara la cadena de unos y ceros con una versión desplazada de sí mismo. Luego tomas los que coinciden. Tome este ejemplo desplazado por dos:

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

Los 1's resultantes (AND a nivel de bit), deben representar todos aquellos 1 que están espaciados uniformemente por dos. El mismo ejemplo cambió por tres:

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

En este caso, no hay 1 que estén espaciados uniformemente entre sí.

Entonces, ¿qué te dice esto? Bueno, solo necesitas probar turnos que son números primos. Por ejemplo, supongamos que tiene dos 1 que están separados por seis. Solo tendría que probar los turnos 'dos' y los turnos 'tres' (ya que estos dividen seis). Por ejemplo:

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

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

Por lo tanto, los únicos turnos que debe verificar son 2,3,5,7,11,13, etc. Hasta el primo más cercano a la raíz cuadrada del tamaño de la cadena de dígitos.

¿Casi resuelto?

Creo que estoy más cerca de una solución. Básicamente:

1. Escanee la cadena por 1's. Para cada 1 nota es el resto después de tomar un módulo de su posición. El módulo varía de 1 a la mitad del tamaño de la cadena. Esto se debe a que el tamaño de separación más grande posible es la mitad de la cadena. Esto se hace en O (n ^ 2). PERO. Solo se deben verificar los módulos primos para que O (n ^ 2 / log (n))
2. Ordene primero la lista de módulos / restos en orden de módulo más grande, esto se puede hacer en tiempo O (n * log (n)).
3. Busque tres módulos / restos consecutivos que sean iguales.
4. De alguna manera recuperar la posición de los unos!

Creo que la pista más importante para la respuesta es que los algoritmos de clasificación más rápidos son O (n * log (n)).

INCORRECTO

El paso 1 es incorrecto como lo señaló un colega. Si tenemos 1 en las posiciones 2,12 y 102. Luego, tomando un módulo de 10, ¡todos tendrían los mismos restos y, sin embargo, no estarán separados por igual! Lo siento.

Aquí hay algunos pensamientos que, a pesar de mis mejores esfuerzos, no parecerán envolverse en una reverencia. Aún así, podrían ser un punto de partida útil para el análisis de alguien.

Considere la solución propuesta de la siguiente manera, que es el enfoque que varias personas han sugerido, incluido yo mismo en una versión anterior de esta respuesta. :)

1. Recorte ceros iniciales y finales.
2. Escanee la cadena buscando 1's.
3. Cuando se encuentra un 1:
   1. Suponga que es el medio 1 de la solución.
   2. Para cada 1 anterior, use su posición guardada para calcular la posición anticipada del 1 final.
   3. Si la posición calculada es posterior al final de la cadena, no puede ser parte de la solución, por lo tanto, elimine la posición de la lista de candidatos.
   4. Comprueba la solución.
4. Si no se encontró la solución, agregue el 1 actual a la lista de candidatos.
5. Repita hasta que no se encuentren más 1.

Ahora considere cadenas de entrada como las siguientes, que no tendrán una solución:

101
101001
1010010001
101001000100001
101001000100001000001

En general, esta es la concatenación de k cadenas de la forma j 0 seguidas de un 1 para j de cero a k-1.

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

Tenga en cuenta que las longitudes de las subcadenas son 1, 2, 3, etc. Por lo tanto, el tamaño del problema n tiene subcadenas de longitudes 1 a k, de modo que 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

Tenga en cuenta que k también rastrea el número de 1 que tenemos que tener en cuenta. Recuerde que cada vez que vemos un 1, debemos considerar todos los 1 vistos hasta ahora. Entonces, cuando vemos el segundo 1, solo consideramos el primero, cuando vemos el tercer 1, reconsideramos los dos primeros, cuando vemos el cuarto 1, necesitamos reconsiderar los primeros tres, y así sucesivamente. Al final del algoritmo, hemos considerado k (k-1) / 2 pares de 1. Llama a eso p.

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

La relación entre n y p es que n = p + k.

El proceso de pasar por la cadena lleva O (n) tiempo. Cada vez que se encuentra un 1, se realiza un máximo de (k-1) comparaciones. Como n = k (k + 1) / 2, n> k ** 2, entonces sqrt (n)> k. Esto nos da O (n sqrt (n)) u O (n ** 3/2). Sin embargo, tenga en cuenta que puede que no sea un límite realmente apretado, porque el número de comparaciones va de 1 a un máximo de k, no es k todo el tiempo. Pero no estoy seguro de cómo explicar eso en las matemáticas.

Todavía no es O (n log (n)). Además, no puedo probar que esas entradas sean los peores casos, aunque sospecho que lo son. Creo que un empaque más denso de 1 al frente resulta en un empaque aún más escaso al final.

Como alguien aún puede encontrarlo útil, aquí está mi código para esa solución en 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";

Mientras escanea 1s, agregue sus posiciones a una Lista. Cuando agregue el segundo y sucesivos 1s, compárelos con cada posición en la lista hasta el momento. El espaciado es igual a currentOne (centro) - previousOne (izquierda). El bit del lado derecho es currentOne + spacing. Si es 1, el final.

La lista de unos crece inversamente con el espacio entre ellos. En pocas palabras, si tienes muchos 0 entre los 1 (como en el peor de los casos), tu lista de 1 conocidos crecerá muy lentamente.

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

Pensé en agregar un comentario antes de publicar la solución ingenua número 22 al problema. Para la solución ingenua, no necesitamos mostrar que el número de 1 en la cadena es como máximo O (log (n)), sino que es como máximo O (sqrt (n * log (n)).

Solucionador:

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

Básicamente es bastante similar a la idea e implementación de flybywire, aunque mirando hacia adelante en lugar de hacia atrás.

Greedy String Builder:

#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

(En mi defensa, todavía estoy en la etapa de comprensión de 'aprender pitón')

Además, como resultado potencialmente útil de la codiciosa construcción de cuerdas, hay un salto bastante consistente después de golpear una potencia de 2 en el número de 1 ... que no estaba dispuesto a esperar para presenciar el golpe de 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

Trataré de presentar un enfoque matemático. Esto es más un comienzo que un fin, por lo que cualquier ayuda, comentario o incluso contradicción será muy apreciada. Sin embargo, si se prueba este enfoque, el algoritmo es una búsqueda directa en la cadena.

1. Dado un número fijo de espacios ky una cadena S, la búsqueda de un triplete con espacio k toma O(n): simplemente probamos cada 0<=i<=(n-2k)si S[i]==S[i+k]==S[i+2k]. La prueba toma O(1)y lo hacemos n-kveces donde kes una constante, por lo que toma O(n-k)=O(n).

2. Supongamos que hay una proporción inversa entre el número de 1's' y los espacios máximos que necesitamos buscar. Es decir, si hay muchos 1, debe haber un triplete y debe ser bastante denso; Si solo hay unos pocos 1, el triplete (si lo hay) puede ser bastante escaso. En otras palabras, puedo demostrar que si tengo suficientes 1, este triplete debe existir, y cuanto más 1tengo, se debe encontrar un triplete más denso. Esto puede explicarse por el principio de Pigeonhole : espero profundizar en esto más adelante.

3. Digamos que tengo un límite superior ken el número posible de espacios que tengo que buscar. Ahora, para cada uno 1situado en S[i]lo que necesitamos para comprobar 1en S[i-1]y S[i+1], S[i-2]y S[i+2], ... S[i-k]y S[i+k]. Esto toma O((k^2-k)/2)=O(k^2)para cada 1en S- debido a Gauss Serie Suma Fórmula . Tenga en cuenta que esto difiere de la sección 1: estoy teniendo kcomo límite superior el número de espacios, no como un espacio constante.

Necesitamos probarlo O(n*log(n)). Es decir, tenemos que demostrar que k*(number of 1's)es proporcional a log(n).

Si podemos hacer eso, el algoritmo es trivial: para cada uno 1en Scuyo índice está i, simplemente busque 1's desde cada lado hasta la distancia k. Si se encontraron dos en la misma distancia, regrese iy k. Nuevamente, la parte difícil sería encontrar ky probar la corrección.

Realmente agradecería sus comentarios aquí. He estado tratando de encontrar la relación ky el número de 1's en mi pizarra, hasta ahora sin éxito.

Suposición:

Simplemente incorrecto, hablando de log (n) número de límite superior de unos

EDITAR:

Ahora descubrí que usando números de Cantor (si es correcto), la densidad en el conjunto es (2/3) ^ Log_3 (n) (qué función más extraña) y estoy de acuerdo, la densidad de log (n) / n es demasiado fuerte.

Si este es el límite superior, hay un algoritmo que resuelve este problema en al menos O (n * (3/2) ^ (log (n) / log (3))) complejidad de tiempo y O ((3/2) ^ ( log (n) / log (3))) complejidad del espacio. (verifique la respuesta de Justice para el algoritmo)

Esto sigue siendo mucho mejor que O (n ^ 2)

Esta función ((3/2) ^ (log (n) / log (3))) realmente se parece a n * log (n) a primera vista.

¿Cómo obtuve esta fórmula?

Aplaudir el número de Cantors en la cuerda.
Suponga que la longitud de la cadena es 3 ^ p == n
En cada paso de la generación de la cadena de Cantor, mantiene 2/3 de la cantidad anterior de unidades. Aplicar esto p veces.

Eso significa (n * ((2/3) ^ p)) -> (((3 ^ p)) * ((2/3) ^ p)) restantes y después de la simplificación 2 ^ p. Esto significa 2 ^ p unos en 3 ^ p cadena -> (3/2) ^ p unos. Sustituya p = log (n) / log (3) y obtenga
((3/2) ^ (log (n) / log (3)))

¿Qué tal una solución simple de O (n), con espacio O (n ^ 2)? (Utiliza el supuesto de que todos los operadores bit a bit funcionan en O (1)).

El algoritmo básicamente funciona en cuatro etapas:

Etapa 1: Para cada bit en su número original, averigüe qué tan lejos están los unos, pero considere solo una dirección. (Considere todos los bits en la dirección del bit menos significativo).

Etapa 2: Invierta el orden de los bits en la entrada;

Etapa 3: vuelva a ejecutar el paso 1 en la entrada invertida.

Etapa 4: Compare los resultados de la Etapa 1 y la Etapa 3. Si algún bit está igualmente espaciado arriba Y abajo, debemos tener un éxito.

Tenga en cuenta que ningún paso en el algoritmo anterior lleva más tiempo que O (n). ^ _ ^

Como beneficio adicional, este algoritmo encontrará TODOS los igualmente espaciados de CADA número. Entonces, por ejemplo, si obtiene un resultado de "0x0005", entonces hay espacios igualmente espaciados en AMBAS unidades 1 y 3 de distancia

Realmente no intenté optimizar el código a continuación, pero es un código C # compilable que parece funcionar.

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

Alguien probablemente comentará que para cualquier número suficientemente grande, las operaciones bit a bit no pueden realizarse en O (1). Estarías en lo correcto. Sin embargo, conjeturaría que toda solución que use sumas, restas, multiplicaciones o divisiones (que no se puede hacer cambiando) también tendría ese problema.

A continuación hay una solución. Podría haber algunos pequeños errores aquí y allá, pero la idea es sólida.

Editar: no es n * log (n)

CÓDIGO 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

Código 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;
}

Cómo funciona:

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

Obviamente, necesitamos al menos verificar grupos de trillizos al mismo tiempo, por lo que debemos comprimir los controles de alguna manera. Tengo un algoritmo candidato, pero analizar la complejidad del tiempo está más allá de mi capacidad * umbral de tiempo.

Construya un árbol donde cada nodo tenga tres hijos y cada nodo contenga el número total de 1 en sus hojas. Cree una lista vinculada sobre los 1, también. Asigne a cada nodo un costo permitido proporcional al rango que cubre. Mientras el tiempo que pasamos en cada nodo esté dentro del presupuesto, tendremos un algoritmo O (n lg n).

-

Comience en la raíz. Si el cuadrado del número total de 1 por debajo es menor que su costo permitido, aplique el algoritmo ingenuo. De lo contrario, recurse en sus hijos.

Ahora hemos regresado dentro del presupuesto, o sabemos que no hay trillizos válidos completamente contenidos dentro de uno de los niños. Por lo tanto, debemos verificar los tripletes entre nodos.

Ahora las cosas se vuelven increíblemente desordenadas. Esencialmente, queremos recurrir a los conjuntos potenciales de niños mientras limitamos el rango. Tan pronto como el rango esté lo suficientemente limitado como para que el algoritmo ingenuo se ejecute por debajo del presupuesto, lo haces. Disfruta implementando esto, porque te garantizo que será tedioso. Hay como una docena de casos.

-

La razón por la que creo que el algoritmo funcionará es porque las secuencias sin tripletes válidos parecen alternarse entre grupos de 1 y muchos 0. Divide efectivamente el espacio de búsqueda cercano, y el árbol emula esa división.

El tiempo de ejecución del algoritmo no es obvio, en absoluto. Se basa en las propiedades no triviales de la secuencia. Si los 1 son realmente escasos, entonces el ingenuo algoritmo funcionará por debajo del presupuesto. Si los 1 son densos, entonces se debe encontrar una coincidencia de inmediato. Pero si la densidad es "correcta" (p. Ej., Cerca de ~ n ^ 0.63, que puede lograr al establecer todos los bits en posiciones sin dígitos '2' en la base 3), no sé si funcionará. Tendría que demostrar que el efecto de división es lo suficientemente fuerte.

No hay una respuesta teórica aquí, pero escribí un programa Java rápido para explorar el comportamiento del tiempo de ejecución en función de k y n, donde n es la longitud total de bits yk es el número de 1. Estoy con algunos de los que responden que dicen que el algoritmo "regular" que verifica todos los pares de posiciones de bits y busca el tercer bit, aunque requeriría O (k ^ 2) en el peor de los casos, en realidad porque el peor de los casos necesita cadenas de bits dispersas, es O (n ln n).

De todos modos, aquí está el programa, a continuación. Es un programa de estilo Monte-Carlo que ejecuta una gran cantidad de NTRIALS de prueba para n constante, y genera aleatoriamente conjuntos de bits para un rango de valores k utilizando procesos de Bernoulli con una densidad limitada entre límites que se pueden especificar, y registra el tiempo de ejecución de encontrar o no encontrar un triplete de espaciado uniforme, tiempo medido en pasos NO en tiempo de CPU. Lo ejecuté durante n = 64, 256, 1024, 4096, 16384 * (aún en ejecución), primero una prueba con 500000 pruebas para ver qué valores k toman el tiempo de ejecución más largo, luego otra prueba con 5000000 pruebas con valores reducidos. enfoque de densidad para ver cómo se ven esos valores. Los tiempos de ejecución más largos ocurren con una densidad muy escasa (por ejemplo, para n = 4096 los picos de tiempo de ejecución están en el rango k = 16-64, con un pico suave para el tiempo de ejecución medio en 4212 pasos @ k = 31, el tiempo de ejecución máximo alcanzó su punto máximo en 5101 pasos @ k = 58). Parece que tomaría valores extremadamente grandes de N para que el paso O (k ^ 2) en el peor de los casos se hiciera más grande que el paso O (n) donde escanea la cadena de bits para encontrar los índices de posición del 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

Tengo problemas con los peores escenarios con millones de dígitos. Fuzzing de /dev/urandomesencialmente te da O (n), pero sé que el peor de los casos es peor que eso. Simplemente no puedo decir cuánto peor. Para los pequeños n, es trivial encontrar insumos alrededor 3*n*log(n), pero es sorprendentemente difícil diferenciarlos de algún otro orden de crecimiento para este problema en particular.

¿Puede alguien que estaba trabajando en las entradas del peor de los casos generar una cadena con una longitud mayor que, digamos, cien mil?

Una adaptación del algoritmo Rabin-Karp podría ser posible para usted. Su complejidad es 0 (n), por lo que podría ayudarlo.

Echa un vistazo http://en.wikipedia.org/wiki/Rabin-Karp_string_search_algorithm

¿Podría ser esto una solución? No estoy seguro de si es O (nlogn), pero en mi opinión es mejor que O (n²) porque la única forma de no encontrar un triple sería una distribución de números primos.

Hay margen de mejora, el segundo encontrado 1 podría ser el próximo primero 1. Además, no hay comprobación de errores.

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

Creo que este algoritmo tiene complejidad O (n log n) (C ++, DevStudio 2k5). Ahora, no conozco los detalles de cómo analizar un algoritmo para determinar su complejidad, por lo que he agregado alguna información de recopilación métrica al código. El código cuenta el número de pruebas realizadas en la secuencia de 1 y 0 para cualquier entrada dada (con suerte, no he hecho una bola del algoritmo). Podemos comparar el número real de pruebas con el valor O y ver si hay una correlación.

#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";
  }
}

Este programa genera el número de pruebas para cada longitud de cadena de hasta 32 caracteres. Aquí están los resultados:

 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

También agregué los valores 'n log n'. Grafique estos utilizando su herramienta gráfica de elección para ver una correlación entre los dos resultados. ¿Este análisis se extiende a todos los valores de n? No lo sé.