Algorithme O (nlogn) - Trouvez trois algorithmes espacés uniformément dans une chaîne binaire

J'ai eu cette question sur un test d'algorithmes hier, et je ne peux pas trouver la réponse. Cela me rend complètement fou, car cela valait environ 40 points. Je suppose que la plupart des élèves ne l'ont pas résolu correctement, car je n'ai pas trouvé de solution au cours des dernières 24 heures.

Étant donné une chaîne binaire arbitraire de longueur n, trouvez trois chaînes régulièrement espacées dans la chaîne si elles existent. Écrivez un algorithme qui résout cela en O (n * log (n)) temps.

Ainsi, les chaînes comme celles-ci en ont trois qui sont "régulièrement espacées": 11100000, 0100100100

edit: C'est un nombre aléatoire, il devrait donc pouvoir fonctionner pour n'importe quel nombre. Les exemples que j'ai donnés visaient à illustrer la propriété "régulièrement espacés". Donc 1001011 est un nombre valide. Avec 1, 4 et 7 étant ceux qui sont régulièrement espacés.

Finalement! En suivant les pistes de la réponse de sdcvvc , nous l'avons: l'algorithme O (n log n) pour le problème! C'est simple aussi, une fois que vous l'avez compris. Ceux qui ont deviné FFT avaient raison.

Le problème: on nous donne une chaîne binaire Sde longueur n , et nous voulons y trouver trois 1 régulièrement espacés. Par exemple, Speut être 110110010, où n = 9. Il a des 1 régulièrement espacés aux positions 2, 5 et 8.

1. Balayez de Sgauche à droite et faites une liste Lde positions de 1. Pour ce qui S=110110010précède, nous avons la liste L = [1, 2, 4, 5, 8]. Cette étape est O (n). Le problème est maintenant de trouver une progression arithmétique de longueur 3 en L, c'est-à-dire de trouver distincte a, b, c en Ltelle que ba = cb , ou de manière équivalente a + c = 2b . Pour l'exemple ci-dessus, nous voulons trouver la progression (2, 5, 8).

2. Faire un polynôme p avec des termes x ^k pour chaque k dans L. Pour l'exemple ci-dessus, nous faisons le polynôme p (x) = (x + x ² + x ⁴ + x ⁵ + x ⁸ ) . Cette étape est O (n).

3. Trouvez le polynôme q= p ² , en utilisant la transformation de Fourier rapide . Pour l'exemple ci-dessus, nous obtenons le polynôme q (x) = x ¹⁶ + 2x ¹³ + 2x ¹² + 3x ¹⁰ + 4x ⁹ + x ⁸ + 2x ⁷ + 4x ⁶ + 2x ⁵ + x ⁴ + 2x ³ + x ² . Cette étape est O (n log n).

4. Ignorez tous les termes sauf ceux correspondant à x ^2k pour certains k in L. Pour l'exemple ci-dessus, nous obtenons les termes x ¹⁶ , 3x ¹⁰ , x ⁸ , x ⁴ , x ² . Cette étape est O (n), si vous choisissez de la faire du tout.

Voici le point crucial: le coefficient de tout x ^2b pour b dansL est précisément le nombre de paires (a, c) en Lsorte que a + c = 2b . [CLRS, Ex. 30.1-7] Une telle paire est toujours (b, b) (donc le coefficient est au moins 1), mais s'il existe une autre paire (a, c) , alors le coefficient est au moins 3, de (a, c ) et (c, a) . Pour l'exemple ci-dessus, nous avons le coefficient de x ¹⁰ à 3 précisément à cause de l'AP (2,5,8). (Ces coefficients x ^2bseront toujours des nombres impairs, pour les raisons ci-dessus. Et tous les autres coefficients de q seront toujours pairs.)

Donc, l'algorithme doit regarder les coefficients de ces termes x ^2b , et voir si l'un d'entre eux est supérieur à 1. S'il n'y en a pas, alors il n'y a pas de 1 régulièrement espacés. S'il est un b dans Lpour laquelle le coefficient de x ^2b est supérieur à 1, alors nous savons qu'il ya une paire (a, c) - autre que (b, b) - pour lequel a + c = 2b . Pour trouver la paire réelle, nous essayons simplement chaque a inL(le c correspondantserait 2b-a ) et voyons s'il y a un 1 à la position 2b-a inS. Cette étape est O (n).

C'est tout, les gars.

On pourrait se demander: devons-nous utiliser FFT? De nombreuses réponses, telles que bêta , flybywire et rsp , suggèrent que l'approche qui vérifie chaque paire de 1 et voit s'il y a un 1 à la «troisième» position, pourrait fonctionner en O (n log n), en fonction de l'intuition que s'il y a trop de 1, nous trouverions facilement un triple, et s'il y a trop peu de 1, vérifier toutes les paires prend peu de temps. Malheureusement, bien que cette intuition soit correcte et que l'approche simple soit meilleure que O (n ² ), elle n'est pas significativement meilleure. Comme dans la réponse de sdcvvc , nous pouvons prendre le "jeu de type Cantor" de chaînes de longueur n = 3 ^k, avec des 1 aux positions dont la représentation ternaire ne contient que des 0 et 2 (pas de 1). Une telle chaîne a 2 ^k = n ^{(log 2) / (log 3)} ≈ n ^0,63 uns et pas de 1 régulièrement espacés, donc vérifier toutes les paires serait de l'ordre du carré du nombre de 1: c'est 4 ^k ≈ n ^1,26 qui est malheureusement asymptotiquement beaucoup plus grand que (n log n). En fait, le pire des cas est encore pire: Leo Moser en 1953 a construit (effectivement) de telles chaînes qui contiennent n ^{1-c / √ (log n)} 1 mais pas de 1 régulièrement espacées, ce qui signifie que sur de telles chaînes, le simple l'approche prendrait Θ (n ^{2-2c / √ (log n)} )- seulement un tout petit peu mieux que Θ (n ² ) , étonnamment!

À propos du nombre maximum de 1 dans une chaîne de longueur n sans 3 espacés uniformément (ce que nous avons vu ci-dessus était au moins n ^0,63 de la construction facile de type Cantor, et au moins n ^{1-c / √ (log n)} avec Construction de Moser) - il s'agit de l' OEIS A003002 . Il peut également être calculé directement à partir de l' OEIS A065825 comme k tel que A065825 (k) ≤ n <A065825 (k + 1). J'ai écrit un programme pour les trouver, et il s'avère que l'algorithme glouton ne donne pas la plus longue chaîne de ce type. Par exemple, pour n = 9, on peut obtenir 5 1s (110100011) mais le gourmand n'en donne que 4 (110110000), pour n= 26 nous pouvons obtenir 11 1s (11001010001000010110001101) mais le gourmand n'en donne que 8 (11011000011011000000000000), et pour n = 74 nous pouvons obtenir 22 1s (11000010110001000001011010001000000000000000010001011010000010001101000011) mais le gourmand ne donne que 16000000001000001010001100000100000101000110000010000010 Ils sont d'accord à un certain nombre d'endroits jusqu'à 50 (par exemple tous de 38 à 50), cependant. Comme le disent les références OEIS, il semble que Jaroslaw Wroblewski s'intéresse à cette question, et il maintient un site Web sur ces ensembles sans moyenne . Les chiffres exacts ne sont connus que jusqu'à 194.

Votre problème s'appelle MOYENNE en cet article (1999):

Un problème est 3SUM-difficile s'il y a une réduction sous-quadratique du problème 3SUM: Étant donné un ensemble A de n entiers, y a-t-il des éléments a, b, c dans A tels que a + b + c = 0? On ne sait pas si la MOYENNE est 3SUM-dure. Cependant, il existe une simple réduction en temps linéaire de MOYENNE à 3SUM, dont nous omettons la description.

Wikipédia :

Lorsque les nombres entiers sont dans l'intervalle [−u ... u], 3SUM peut être résolu en temps O (n + u lg u) en représentant S comme un vecteur de bits et en effectuant une convolution en utilisant la FFT.

Cela suffit à résoudre votre problème :).

Ce qui est très important, c'est que O (n log n) est la complexité en termes de nombre de zéros et de uns, et non le nombre de uns (qui pourrait être donné sous forme de tableau, comme [1,5,9,15]). Vérifier si un ensemble a une progression arithmétique, des termes de nombre de 1, est difficile, et selon cet article à partir de 1999, aucun algorithme plus rapide que O (n ² ) n'est connu, et on suppose qu'il n'existe pas.Quiconque ne tient pas compte de cela tente de résoudre un problème ouvert.

Autres informations intéressantes, pour la plupart non pertinentes:

Borne inférieure:

Une borne inférieure facile est un ensemble de type Cantor (les nombres 1..3 ^ n-1 ne contenant pas 1 dans leur expansion ternaire) - sa densité est n ^ (log_3 2) (environ 0,631). Donc, vérifier si l'ensemble n'est pas trop grand, puis vérifier toutes les paires ne suffit pas pour obtenir O (n log n). Vous devez étudier la séquence plus intelligemment. Une meilleure borne inférieure est citée ici - c'est n ^{1-c / (log (n)) ^ (1/2)} . Cela signifie que le jeu de Cantor n'est pas optimal.

Limite supérieure - mon ancien algorithme:

On sait que pour n grand, un sous-ensemble de {1,2, ..., n} ne contenant pas de progression arithmétique a au plus n / (log n) ^ (1/20) éléments. L'étude Sur les triplets en progression arithmétique prouve davantage: l'ensemble ne peut contenir plus de n * 2 ²⁸ * (log log n / log n) ^1/2 éléments. Vous pouvez donc vérifier si cette limite est atteinte et sinon, vérifier naïvement les paires. Il s'agit de l' algorithme O (n ² * log log n / log n), plus rapide que O (n ² ). Malheureusement, "On triples ..." est sur Springer - mais la première page est disponible, et l'exposition de Ben Green est disponible ici , page 28, théorème 24.

Soit dit en passant, les journaux datent de 1999 - la même année que le premier que j'ai mentionné, c'est probablement pourquoi le premier ne mentionne pas ce résultat.

Ce n'est pas une solution, mais une ligne de pensée similaire à ce que pensait Olexiy

Je jouais avec la création de séquences avec un nombre maximum d'unités, et elles sont toutes assez intéressantes, j'ai obtenu jusqu'à 125 chiffres et voici les 3 premiers nombres trouvés en essayant d'insérer autant de bits '1' que possible:

• 11011000011011000000000000001101100001101100000000000000000000000000000000000000000110110000110110000000000000011011000011011
• 10110100010110100000000000010110100010110100000000000000000000000000000000000000000101101000101101000000000000101101000101101
• 10011001010011001000000000010011001010011001000000000000000000000000000000000000010011001010011001000000000010011001010011001

Remarquez qu'ils sont tous fractales (pas trop surprenant compte tenu des contraintes). Il peut y avoir quelque chose à penser en arrière, peut-être que si la corde n'est pas une fractale avec une caractéristique, alors elle doit avoir un motif répétitif?

Merci à beta pour le meilleur terme pour décrire ces chiffres.

Mise à jour: Hélas, il semble que le modèle se décompose en commençant par une chaîne initiale suffisamment grande, telle que: 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

Je soupçonne qu'une approche simple qui ressemble à O (n ^ 2) donnera en fait quelque chose de mieux, comme O (n ln (n)). Les séquences qui prennent le plus de temps à tester (pour un n donné) sont celles qui ne contiennent pas de trios, ce qui impose des restrictions sévères sur le nombre de 1 qui peuvent être dans la séquence.

Je suis venu avec quelques arguments ondulants, mais je n'ai pas été en mesure de trouver une bonne preuve. Je vais essayer dans le noir: la réponse est une idée très intelligente que le professeur connaît depuis si longtemps qu'elle en est venue à paraître évidente, mais c'est beaucoup trop difficile pour les étudiants. (Soit cela, soit vous avez dormi pendant la conférence qui l'a couvert.)

Révision: 17/10/2009 23:00

J'ai exécuté cela sur de grands nombres (comme des chaînes de 20 millions) et je crois maintenant que cet algorithme n'est pas O (n logn). Malgré cela, c'est une implémentation assez cool et contient un certain nombre d'optimisations qui la rendent très rapide. Il évalue tous les arrangements de chaînes binaires de 24 chiffres ou moins en moins de 25 secondes.

J'ai mis à jour le code pour inclure l' 0 <= L < M < U <= X-1observation du début de la journée.

Original

C'est, dans le concept, similaire à une autre question à laquelle j'ai répondu . Ce code a également examiné trois valeurs dans une série et déterminé si un triplet satisfaisait une condition. Voici le code C # adapté de cela:

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

Les principales différences sont:

1. Recherche exhaustive de solutions
   Ce code génère un ensemble puissant de données pour trouver l'entrée la plus difficile à résoudre pour cet algorithme.
2. Toutes les solutions contre les plus difficiles à résoudre
   Le code de la question précédente a généré toutes les solutions à l'aide d'un générateur python. Ce code affiche simplement le plus difficile pour chaque longueur de motif.
3. Algorithme de notation
   Ce code vérifie la distance entre l'élément central et ses bords gauche et droit. Le code python testait si une somme était supérieure ou inférieure à 0.
4. Convergence sur un candidat
   Le code actuel fonctionne du milieu vers le bord pour trouver un candidat. Le code du problème précédent fonctionnait des bords vers le milieu. Ce dernier changement donne une grande amélioration des performances.
5. Utilisation de pools pairs et impairs
   Sur la base des observations à la fin de cet article, le code recherche des paires de nombres pairs de paires de nombres impairs pour trouver L et U, en gardant M fixe. Cela réduit le nombre de recherches en pré-calculant les informations. En conséquence, le code utilise deux niveaux d'indirection dans la boucle principale de FindCandidate et nécessite deux appels à FindCandidate pour chaque élément du milieu: une fois pour les nombres pairs et une fois pour les nombres impairs.

L'idée générale est de travailler sur des index, pas sur la représentation brute des données. Le calcul d'un tableau dans lequel les 1 apparaissent permet à l'algorithme de s'exécuter dans le temps proportionnel au nombre de 1 dans les données plutôt que dans le temps proportionnel à la longueur des données. Il s'agit d'une transformation standard: créez une structure de données qui permet un fonctionnement plus rapide tout en gardant l'équivalent du problème.

Les résultats sont obsolètes: supprimés.

Edit: 16/10/2009 18:48

Sur les données de yx, qui ont une certaine crédibilité dans les autres réponses comme représentatives de données concrètes sur lesquelles calculer, j'obtiens ces résultats ... Je les ai supprimés. Ils ne sont plus à jour.

Je tiens à souligner que ces données ne sont pas les plus difficiles pour mon algorithme, donc je pense que l'hypothèse selon laquelle les fractales de yx sont les plus difficiles à résoudre est erronée. Le pire des cas pour un algorithme particulier, je suppose, dépendra de l'algorithme lui-même et ne sera probablement pas cohérent entre les différents algorithmes.

Edit: 17/10/2009 13:30

Autres observations à ce sujet.

Commencez par convertir la chaîne de 0 et de 1 en un tableau d'index pour chaque position des 1. Disons que la longueur de ce tableau A est X. Alors le but est de trouver

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

tel que

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

ou

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

Puisque A [L] et A [U] sont un nombre pair, ils ne peuvent pas être (pair, impair) ou (impair, pair). La recherche d'une correspondance pourrait être améliorée en divisant A [] en groupes pairs et impairs et en recherchant des correspondances sur A [M] dans les groupes de candidats pairs et impairs à tour de rôle.

Cependant, il s'agit plus d'une optimisation des performances qu'une amélioration algorithmique, je pense. Le nombre de comparaisons devrait baisser, mais l'ordre de l'algorithme devrait être le même.

Edit 2009-10-18 00:45

Une autre optimisation me vient à l'esprit, dans la même veine que la séparation des candidats en pairs et impairs. Étant donné que les trois index doivent s'ajouter à un multiple de 3 (a, a + x, a + 2x - mod 3 est 0, indépendamment de a et x), vous pouvez séparer L, M et U dans leurs valeurs 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

En fait, vous pouvez combiner cela avec l'observation paire / impaire et les séparer en leurs valeurs mod 6:

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

etc. Cela fournirait une optimisation supplémentaire des performances, mais pas une accélération algorithmique.

Je n'ai pas encore pu trouver la solution :(, mais j'ai quelques idées.

Et si nous partions d'un problème inverse: construisons une séquence avec le nombre maximum de 1 et SANS trios régulièrement espacés. Si vous pouvez prouver que le nombre maximum de 1 est o (n), alors vous pouvez améliorer votre estimation en itérant uniquement sur une liste de 1.

Cela peut aider ...

Ce problème se réduit à ce qui suit:

Étant donné une séquence d'entiers positifs, trouvez une sous-séquence contiguë partitionnée en un préfixe et un suffixe tels que la somme du préfixe de la sous-séquence soit égale à la somme du suffixe de la sous-séquence.

Par exemple, étant donné une séquence de [ 3, 5, 1, 3, 6, 5, 2, 2, 3, 5, 6, 4 ], nous trouverions une sous-séquence de [ 3, 6, 5, 2, 2]avec un préfixe de [ 3, 6 ]avec préfixe somme de 9et un suffixe de [ 5, 2, 2 ]avec suffixe somme de9 .

La réduction est la suivante:

Étant donné une séquence de zéros et de uns, et en commençant à l'extrême gauche, continuez à vous déplacer vers la droite. Chaque fois qu'un autre est rencontré, enregistrez le nombre de coups depuis que le précédent a été rencontré et ajoutez ce numéro à la séquence résultante.

Par exemple, étant donné une séquence de [ 0, 1, 1, 0, 0, 1, 0, 0, 0, 1 0 ], nous trouverions la réduction de [ 1, 3, 4]. À partir de cette réduction, nous calculons la sous-séquence contiguë de [ 1, 3, 4], le préfixe de [ 1, 3]avec somme de 4et le suffixe de [ 4 ]avec somme de4 .

Cette réduction peut être calculée en O(n) .

Malheureusement, je ne sais pas trop où aller à partir d'ici.

Pour le type de problème simple (c'est-à-dire que vous recherchez trois "1" avec seulement (c'est-à-dire zéro ou plus) "0" entre eux), c'est assez simple: vous pouvez simplement diviser la séquence à chaque "1" et rechercher deux sous-séquences adjacentes ayant la même longueur (la deuxième sous-séquence n'étant pas la dernière, bien sûr). Évidemment, cela peut être fait en temps O (n) .

Pour la version plus complexe (c'est-à-dire que vous recherchez un index i et un intervalle g > 0 tels que s[i]==s[i+g]==s[i+2*g]=="1"), je ne suis pas sûr, s'il existe une solution O (n log n) , car il y a éventuellement des triplets O (n²) ayant cette propriété (pensez à une chaîne de tous, il y a environ n² / 2 triplets de ce type). Bien sûr, vous ne recherchez qu'un seul d'entre eux, mais je n'ai actuellement aucune idée, comment le trouver ...

Une question amusante, mais une fois que vous vous rendez compte que le modèle réel entre deux '1 n'a pas d'importance, l'algorithme devient:

• rechercher un «1»
• à partir du prochain balayage de position pour un autre '1' (jusqu'à la fin du tableau moins la distance du premier '1' actuel ou bien le 3e '1' serait hors limites)
• si à la position du 2e «1» plus la distance au premier 1 », un troisième« 1 »est trouvé, nous avons des espaces réguliers.

Dans le code, mode JTest, (notez que ce code n'est pas écrit pour être le plus efficace et j'ai ajouté quelques println pour voir ce qui se passe.)

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

J'ai pensé à une approche de division et de conquête qui pourrait fonctionner.

Tout d'abord, lors du prétraitement, vous devez insérer tous les nombres inférieurs à la moitié de votre taille d'entrée ( n / 3) dans une liste.

Étant donné une chaîne: 0000010101000100(notez que cet exemple particulier est valide)

Insérez tous les nombres premiers (et 1) de 1 à (16/2) dans une liste: {1, 2, 3, 4, 5, 6, 7}

Puis divisez-le en deux:

100000101 01000100

Continuez à faire cela jusqu'à ce que vous arriviez à des chaînes de taille 1. Pour toutes les chaînes de taille un avec un 1, ajoutez l'index de la chaîne à la liste des possibilités; sinon, retournez -1 en cas d'échec.

Vous devrez également renvoyer une liste des distances d'espacement encore possibles, associées à chaque index de départ. (Commencez par la liste que vous avez faite ci-dessus et supprimez les nombres au fur et à mesure) Ici, une liste vide signifie que vous n'avez affaire qu'à un 1 et que tout espacement est donc possible à ce stade; sinon, la liste comprend des espacements qui doivent être exclus.

Continuez donc avec l'exemple ci-dessus:

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

Dans la première étape de combinaison, nous avons maintenant huit séries de deux. Dans le premier, on a la possibilité d'un ensemble, mais on apprend que l'espacement de 1 est impossible à cause de la présence de l'autre zéro. Nous retournons donc 0 (pour l'index) et {2,3,4,5,7} pour le fait que l'espacement de 1 est impossible. Dans le second, nous n'avons rien et retournons donc -1. Dans le troisième, nous avons une correspondance sans espacement éliminé dans l'index 5, donc renvoyez 5, {1,2,3,4,5,7}. Dans la quatrième paire, nous retournons 7, {1,2,3,4,5,7}. Dans le cinquième, renvoyez 9, {1,2,3,4,5,7}. Dans le sixième, retournez -1. Dans le septième, retournez 13, {1,2,3,4,5,7}. Au huitième, retournez -1.

En combinant à nouveau en quatre séries de quatre, nous avons:

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

Combinaison en ensembles de huit:

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

Combinant en un ensemble de seize:

10000101 01000100

Au fur et à mesure que nous progressons, nous continuons à vérifier toutes les possibilités jusqu'à présent. Jusqu'à cette étape, nous avons laissé des éléments qui dépassaient la fin de la chaîne, mais nous pouvons maintenant vérifier toutes les possibilités.

Fondamentalement, nous vérifions le premier 1 avec des espacements de 5 et 7, et constatons qu'ils ne s'alignent pas sur les 1. (Notez que chaque vérification est CONSTANTE et non linéaire) Ensuite, nous vérifions la seconde (index 5) avec des espacements de 2, 3, 4, 5, 6 et 7 - ou nous le ferions, mais nous pouvons nous arrêter à 2 puisque qui correspond en fait.

Phew! C'est un algorithme assez long.

Je ne sais pas à 100% si c'est O (n log n) à cause de la dernière étape, mais tout jusqu'à là est définitivement O (n log n) pour autant que je sache. J'y reviendrai plus tard et j'essaierai d'affiner la dernière étape.

EDIT: J'ai changé ma réponse pour refléter le commentaire de Welbog. Désolé pour l'erreur. J'écrirai aussi un pseudocode plus tard, quand j'aurai un peu plus de temps pour déchiffrer ce que j'ai écrit à nouveau. ;-)

Je vais vous donner une estimation approximative ici et laisser ceux qui sont meilleurs avec le calcul de la complexité pour m'aider sur la façon dont mon algorithme se comporte en notation O

1. donnée chaîne binaire 0000010101000100 (comme exemple)
2. tête de récolte et queue de zéros -> 00000 101010001 00
3. nous obtenons 101010001 du calcul précédent
4. vérifier si le bit du milieu est 'un', s'il est vrai, trouvé trois 'uns' valides espacés régulièrement (seulement si le nombre de bits est impaire)
5. corrélativement, si le nombre de bits resté recadré est numéroté pair, la tête et la queue `` un '' ne peuvent pas faire partie de `` un '' régulièrement espacées,
6. nous utilisons 1010100001 comme exemple (avec un `` zéro '' supplémentaire pour devenir une culture paire), dans ce cas, nous devons recadrer à nouveau, puis devient -> 10101 00001
7. nous obtenons 10101 du calcul précédent, et vérifions le bit du milieu, et nous avons retrouvé le bit régulièrement espacé

Je n'ai aucune idée de comment calculer la complexité pour cela, quelqu'un peut-il m'aider?

edit: ajoutez du code pour illustrer mon idée

edit2: j'ai essayé de compiler mon code et j'ai trouvé des erreurs majeures, corrigé

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

J'ai trouvé quelque chose comme ça:

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

Ceci est inspiré par andycjw.

1. Tronquez les zéros.
2. Si même alors testez deux sous-chaînes 0 - (len-2) (sauter le dernier caractère) et de 1 - (len-1) (sauter le premier caractère)
3. Si ce n'est même pas si le caractère du milieu est un, nous avons du succès. Sinon, divisez la chaîne au milieu sans l'élément médian et vérifiez les deux parties.

Quant à la complexité, cela pourrait être O (nlogn) car dans chaque récursion, nous divisons par deux.

J'espère que ça aide.

Ok, je vais tenter un autre coup au problème. Je pense que je peux prouver un algorithme O (n log (n)) similaire à ceux déjà discutés en utilisant un arbre binaire équilibré pour stocker les distances entre les 1. Cette approche a été inspirée par l'observation de Justice sur la réduction du problème à une liste de distances entre les 1.

Pourrions-nous balayer la chaîne d'entrée pour construire un arbre binaire équilibré autour de la position des 1 de sorte que chaque nœud stocke la position du 1 et que chaque bord soit étiqueté avec la distance au 1 adjacent pour chaque nœud enfant. Par exemple:

10010001 gives the following tree

      3
     / \
  2 /   \ 3
   /     \
  0       7

Cela peut être fait en O (n log (n)) puisque, pour une chaîne de taille n, chaque insertion prend O (log (n)) dans le pire des cas.

Ensuite, le problème est de rechercher dans l'arborescence pour découvrir si, à n'importe quel nœud, il existe un chemin de ce nœud à l'enfant gauche qui a la même distance qu'un chemin à travers l'enfant droit. Cela peut être fait de manière récursive sur chaque sous-arbre. Lors de la fusion de deux sous-arbres dans la recherche, nous devons comparer les distances des chemins dans le sous-arbre de gauche avec les distances des chemins dans la droite. Étant donné que le nombre de chemins dans un sous-arbre sera proportionnel à log (n) et que le nombre de nœuds est n, je pense que cela peut être fait en temps O (n log (n)).

Ai-je manqué quelque chose?

Cela semblait être un problème amusant, alors j'ai décidé de m'essayer.

Je suppose que 111000001 trouverait les 3 premiers et réussirait. Essentiellement, le nombre de zéros suivant le 1 est la chose importante, puisque 0111000 équivaut à 111000 selon votre définition. Une fois que vous avez trouvé deux cas de 1, le suivant 1 trouvé complète la trilogie.

Le voici 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

C'est un premier essai, donc je suis sûr que cela pourrait être écrit de manière plus propre. Veuillez énumérer les cas où cette méthode échoue ci-dessous.

Je suppose que la raison pour laquelle il s'agit de nlog (n) est due à ce qui suit:

• Pour trouver le 1 qui est le début du triplet, vous devez vérifier (n-2) caractères. Si vous ne l'avez pas trouvé à ce stade, vous ne le ferez pas (les caractères n-1 et n ne peuvent pas démarrer un triplet) (O (n))
• Pour trouver le deuxième 1 qui fait partie du triplet (commencé par le premier), vous devez vérifier m / 2 (m = nx, où x est le décalage du premier 1) caractères. C'est parce que, si vous n'avez pas trouvé le deuxième 1 au moment où vous êtes à mi-chemin du premier à la fin, vous ne le ferez pas ... puisque le troisième 1 doit être exactement à la même distance que le second. (O (log (n)))
• Cochez O (1) pour trouver le dernier 1 puisque vous connaissez l'index auquel il doit se trouver au moment où vous trouvez le premier et le second.

Donc, vous avez n, log (n) et 1 ... O (nlogn)

Edit: Oups, mon mal. Mon cerveau avait établi que n / 2 était connecté ... ce qui n'est évidemment pas le cas (doubler le nombre d'éléments double toujours le nombre d'itérations sur la boucle interne). Ceci est toujours à n ^ 2, ne résolvant pas le problème. Au moins, je dois écrire du code :)

Implémentation 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

Je pense avoir trouvé un moyen de résoudre le problème, mais je ne peux pas construire une preuve formelle. La solution que j'ai faite est écrite en Java et utilise un compteur «n» pour compter le nombre d'accès aux listes / tableaux. Ainsi, n doit être inférieur ou égal à stringLength * log (stringLength) s'il est correct. Je l'ai essayé pour les nombres 0 à 2 ^ 22, et ça marche.

Il commence par itérer sur la chaîne d'entrée et en faisant une liste de tous les index qui en contiennent un. Ceci est juste O (n).

Ensuite, dans la liste des index, il choisit un firstIndex et un secondIndex qui est supérieur au premier. Ces deux index doivent en contenir, car ils sont dans la liste des index. De là, le troisièmeIndex peut être calculé. Si inputString [thirdIndex] est un 1, alors il s'arrête.

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;

}

note supplémentaire: le compteur n n'est pas incrémenté lorsqu'il itère sur la chaîne d'entrée pour construire la liste des index. Cette opération est O (n), donc elle n'aura pas d'effet sur la complexité de l'algorithme de toute façon.

Une des incursions dans le problème consiste à penser aux facteurs et aux changements.

Avec le décalage, vous comparez la chaîne de uns et de zéros avec une version décalée de lui-même. Vous prenez ensuite ceux qui correspondent. Prenons cet exemple décalé de deux:

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

Les 1 résultants (AND au niveau du bit), doivent représenter tous ces 1 qui sont régulièrement espacés de deux. Le même exemple décalé de trois:

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

Dans ce cas, il n'y a pas de 1 qui sont régulièrement espacés de trois.

Alors qu'est-ce que cela vous dit? Eh bien, il vous suffit de tester les décalages qui sont des nombres premiers. Par exemple, disons que vous avez deux 1 séparés de six. Il vous suffirait de tester «deux» équipes et «trois» équipes (puisque celles-ci divisent six). Par exemple:

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

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

Ainsi, les seuls décalages que vous ayez jamais besoin de vérifier sont 2,3,5,7,11,13 etc. Jusqu'au premier plus proche de la racine carrée de la taille de la chaîne de chiffres.

Presque résolu?

Je pense que je suis plus proche d'une solution. Fondamentalement:

1. Balayez la chaîne pour les 1. Pour chaque note, c'est le reste après avoir pris un module de sa position. Le module varie de 1 à la moitié de la taille de la chaîne. En effet, la plus grande taille de séparation possible est la moitié de la chaîne. Cela se fait en O (n ^ 2). MAIS. Seuls les modules premiers doivent être vérifiés donc O (n ^ 2 / log (n))
2. Trier la liste des modules / restes dans l'ordre le plus grand module en premier, cela peut être fait en temps O (n * log (n)).
3. Recherchez trois modules / restes consécutifs identiques.
4. Récupérez en quelque sorte la position de ceux-ci!

Je pense que le plus gros indice de la réponse est que les algorithmes de tri les plus rapides sont O (n * log (n)).

FAUX

L'étape 1 est fausse comme l'a souligné un collègue. Si nous avons des 1 aux positions 2,12 et 102. Alors en prenant un module de 10, ils auraient tous les mêmes restes, et pourtant ne sont pas également espacés! Désolé.

Voici quelques réflexions qui, malgré tous mes efforts, ne sembleront pas s'envelopper dans un arc. Pourtant, ils pourraient être un point de départ utile pour l'analyse de quelqu'un.

Considérez la solution proposée comme suit, qui est l'approche que plusieurs personnes ont suggérée, y compris moi-même dans une version précédente de cette réponse. :)

1. Coupez les zéros de début et de fin.
2. Scannez la chaîne à la recherche de 1.
3. Lorsqu'un 1 est trouvé:
   1. Supposons que ce soit le milieu 1 de la solution.
   2. Pour chaque 1 antérieur, utilisez sa position enregistrée pour calculer la position anticipée du 1 final.
   3. Si la position calculée est après la fin de la chaîne, elle ne peut pas faire partie de la solution, supprimez donc la position de la liste des candidats.
   4. Vérifiez la solution.
4. Si la solution n'est pas trouvée, ajoutez le 1 actuel à la liste des candidats.
5. Répétez jusqu'à ce qu'il n'y ait plus de 1.

Considérez maintenant les chaînes de chaînes d'entrée comme les suivantes, qui n'auront pas de solution:

101
101001
1010010001
101001000100001
101001000100001000001

En général, il s'agit de la concaténation de k chaînes de la forme j 0 suivies d'un 1 pour j de zéro à k-1.

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

Notez que les longueurs des sous-chaînes sont 1, 2, 3, etc. Ainsi, la taille du problème n a des sous-chaînes de longueurs 1 à k telles 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

Notez que k suit également le nombre de 1 que nous devons considérer. N'oubliez pas que chaque fois que nous voyons un 1, nous devons considérer tous les 1 vus jusqu'à présent. Ainsi, lorsque nous voyons le deuxième 1, nous ne considérons que le premier, lorsque nous voyons le troisième 1, nous reconsidérons les deux premiers, lorsque nous voyons le quatrième 1, nous devons reconsidérer les trois premiers, et ainsi de suite. À la fin de l'algorithme, nous avons considéré k (k-1) / 2 paires de 1. Appelez ça 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 relation entre n et p est que n = p + k.

Le processus pour parcourir la chaîne prend un temps O (n). Chaque fois qu'un 1 est rencontré, un maximum de (k-1) comparaisons sont effectuées. Puisque n = k (k + 1) / 2, n> k ** 2, donc sqrt (n)> k. Cela nous donne O (n sqrt (n)) ou O (n ** 3/2). Notez cependant que ce n'est peut-être pas une limite très serrée, car le nombre de comparaisons va de 1 à un maximum de k, ce n'est pas k tout le temps. Mais je ne sais pas comment expliquer cela en mathématiques.

Ce n'est toujours pas O (n log (n)). De plus, je ne peux pas prouver que ces entrées sont les pires cas, même si je soupçonne qu'elles le sont. Je pense qu'un emballage plus dense de 1 à l'avant entraîne un emballage encore plus clairsemé à la fin.

Puisque quelqu'un peut encore le trouver utile, voici mon code pour cette solution 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";

Lors de la numérisation des 1, ajoutez leurs positions à une liste. Lors de l'ajout du deuxième 1 et des 1 successifs, comparez-les à chaque position de la liste jusqu'à présent. L'espacement est égal à currentOne (centre) - previousOne (à gauche). Le bit de droite est currentOne + espacement. Si c'est 1, la fin.

La liste de ceux-ci augmente inversement avec l'espace entre eux. En termes simples, si vous avez beaucoup de 0 entre les 1 (comme dans le pire des cas), votre liste de 1 connus augmentera assez lentement.

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

J'ai pensé ajouter un commentaire avant de publier la 22e solution naïve au problème. Pour la solution naïve, nous n'avons pas besoin de montrer que le nombre de 1 dans la chaîne est au plus O (log (n)), mais plutôt qu'il est au plus O (sqrt (n * log (n)).

Solveur:

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

C'est fondamentalement un peu similaire à l'idée et à la mise en œuvre de flybywire, mais en regardant vers l'avant plutôt que vers l'arrière.

Générateur de cordes gourmandes:

#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

(Pour ma défense, je suis toujours au stade de compréhension `` apprendre python '')

De plus, sortie potentiellement utile de la construction gourmande de cordes, il y a un saut assez cohérent après avoir atteint une puissance de 2 dans le nombre de 1 ... ce que je n'étais pas prêt à attendre pour assister à 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

Je vais essayer de présenter une approche mathématique. C'est plus un début qu'une fin, donc toute aide, commentaire ou même contradiction - sera profondément apprécié. Cependant, si cette approche est prouvée, l'algorithme est une recherche directe dans la chaîne.

1. Étant donné un nombre fixe d'espaces ket une chaîne S, la recherche d'un triplet d'espacement k prend O(n)- Nous testons simplement pour chaque 0<=i<=(n-2k)si S[i]==S[i+k]==S[i+2k]. Le test prend O(1)et nous le faisons n-kfois où kest une constante, donc il faut O(n-k)=O(n).

2. Supposons qu'il existe une proportion inverse entre le nombre de 1's et le maximum d'espaces que nous devons rechercher. Autrement dit, s'il y en a beaucoup 1, il doit y avoir un triplet et il doit être assez dense; S'il n'y en a que peu 1, le triplet (le cas échéant) peut être assez clairsemé. En d'autres termes, je peux prouver que si j'en ai assez 1, un tel triplet doit exister - et plus 1j'en ai, un triplet plus dense doit être trouvé. Cela peut être expliqué par le principe de Pigeonhole - J'espère développer cela plus tard.

3. Disons avoir une limite supérieure ksur le nombre possible d'espaces que je dois rechercher. Maintenant, pour chaque 1situé dans S[i]nous devons vérifier 1dans S[i-1]et S[i+1], S[i-2]et S[i+2], ... S[i-k]et S[i+k]. Cela prend O((k^2-k)/2)=O(k^2)pour chaque 1enS - en raison de Gauss Series Formula Summation . Notez que cela diffère de la section 1 - j'ai kcomme limite supérieure pour le nombre d'espaces, pas comme un espace constant.

Nous devons prouver O(n*log(n)). Autrement dit, nous devons montrer que k*(number of 1's)c'est proportionnel àlog(n) .

Si nous pouvons faire cela, l'algorithme est trivial - pour chacun 1dans Sdont l'index est i, cherchez simplement 1de chaque côté jusqu'à la distancek . Si deux ont été trouvés à la même distance, retournez iet k. Encore une fois, la partie délicate serait de trouver ket de prouver l'exactitude.

J'apprécierais vraiment vos commentaires ici - j'ai essayé de trouver la relation entre ket le nombre de 1's sur mon tableau blanc, jusqu'à présent sans succès.

Supposition:

Tout simplement faux, parler du nombre log (n) de la limite supérieure de uns

ÉDITER:

Maintenant, j'ai trouvé qu'en utilisant les nombres de Cantor (si corrects), la densité sur le plateau est (2/3) ^ Log_3 (n) (quelle fonction étrange) et je suis d'accord, la densité log (n) / n est trop forte.

S'il s'agit d'une limite supérieure, il existe un algorithme qui résout ce problème en au moins O (n * (3/2) ^ (log (n) / log (3))) complexité de temps et O ((3/2) ^ ( complexité de l'espace log (n) / log (3))). (Vérifiez la réponse de Justice pour l'algorhitm)

C'est toujours de loin meilleur que O (n ^ 2)

Cette fonction ((3/2) ^ (log (n) / log (3))) ressemble vraiment à n * log (n) à première vue.

Comment ai-je obtenu cette formule?

Appliquant le nombre de Cantors sur la chaîne.
Supposons que la longueur de la chaîne est de 3 ^ p == n
A chaque étape de la génération de la chaîne Cantor, vous gardez 2/3 du nombre précédent de chaînes. Appliquez ce p fois.

Cela signifie (n * ((2/3) ^ p)) -> (((3 ^ p)) * ((2/3) ^ p)) restants et après simplification 2 ^ p. Cela signifie 2 ^ p unités dans 3 ^ p chaîne -> (3/2) ^ p unités. Remplacez p = log (n) / log (3) et obtenez
((3/2) ^ (log (n) / log (3)))

Que diriez-vous d'une simple solution O (n), avec un espace O (n ^ 2)? (Utilise l'hypothèse que tous les opérateurs au niveau du bit fonctionnent dans O (1).)

L'algorithme fonctionne essentiellement en quatre étapes:

Étape 1: Pour chaque bit de votre numéro d'origine, déterminez à quelle distance se trouvent ceux-ci, mais ne considérez qu'une seule direction. (J'ai considéré tous les bits dans le sens du bit le moins significatif.)

Étape 2: Inversez l'ordre des bits dans l'entrée;

Étape 3: Relancez l'étape 1 sur l'entrée inversée.

Étape 4: Comparez les résultats des étapes 1 et 3. Si des bits sont également espacés au-dessus ET au-dessous, nous devons avoir un hit.

Gardez à l'esprit qu'aucune étape de l'algorithme ci-dessus ne prend plus de O (n). ^ _ ^

Comme avantage supplémentaire, cet algorithme trouvera TOUS les numéros également espacés de CHAQUE numéro. Ainsi, par exemple, si vous obtenez un résultat de "0x0005", il y en a des espacés de manière égale à 1 et 3 unités.

Je n'ai pas vraiment essayé d'optimiser le code ci-dessous, mais c'est du code C # compilable qui semble fonctionner.

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

Quelqu'un dira probablement que pour un nombre suffisamment grand, les opérations au niveau du bit ne peuvent pas être effectuées dans O (1). Vous auriez raison. Cependant, je suppose que chaque solution qui utilise l'addition, la soustraction, la multiplication ou la division (ce qui ne peut pas être fait par décalage) aurait également ce problème.

Voici une solution. Il peut y avoir quelques petites erreurs ici et là, mais l'idée est bonne.

Edit: Ce n'est pas n * log (n)

CODE 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

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

Comment ça fonctionne:

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

De toute évidence, nous devons au moins vérifier des groupes de triplés en même temps, nous devons donc compresser les contrôles d'une manière ou d'une autre. J'ai un algorithme candidat, mais l'analyse de la complexité temporelle dépasse mon seuil de capacité * temps.

Construisez une arborescence où chaque nœud a trois enfants et chaque nœud contient le nombre total de 1 à ses feuilles. Créez également une liste chaînée sur les 1. Attribuez à chaque nœud un coût autorisé proportionnel à la plage qu'il couvre. Tant que le temps que nous passons à chaque nœud est dans les limites du budget, nous aurons un algorithme O (n lg n).

-

Commencez à la racine. Si le carré du nombre total de 1 en dessous est inférieur à son coût autorisé, appliquez l'algorithme naïf. Sinon, récurer ses enfants.

Maintenant, soit nous sommes revenus dans les limites du budget, soit nous savons qu'il n'y a pas de triplés valides entièrement contenus dans l'un des enfants. Il faut donc vérifier les triplets inter-nœuds.

Maintenant, les choses deviennent incroyablement compliquées. Nous voulons essentiellement revenir sur les groupes potentiels d'enfants tout en limitant la gamme. Dès que la plage est suffisamment limitée pour que l'algorithme naïf s'exécute sous le budget, vous le faites. Profitez de la mise en œuvre de cela, car je vous garantis que ce sera fastidieux. Il y a comme une douzaine de cas.

-

La raison pour laquelle je pense que cet algorithme fonctionnera est que les séquences sans triplets valides semblent alterner entre des paquets de 1 et beaucoup de 0. Il divise efficacement l'espace de recherche à proximité et l'arborescence émule ce fractionnement.

Le temps d'exécution de l'algorithme n'est pas du tout évident. Il repose sur les propriétés non triviales de la séquence. Si les 1 sont vraiment rares, l'algorithme naïf fonctionnera sous le budget. Si les 1 sont denses, une correspondance doit être trouvée immédiatement. Mais si la densité est «juste bonne» (par exemple près de ~ n ^ 0,63, ce que vous pouvez obtenir en définissant tous les bits à des positions sans chiffre «2» en base 3), je ne sais pas si cela fonctionnera. Il faudrait prouver que l'effet de division est suffisamment fort.

Aucune réponse théorique ici, mais j'ai écrit un programme Java rapide pour explorer le comportement au moment de l'exécution en fonction de k et n, où n est la longueur totale en bits et k le nombre de 1. Je suis avec quelques-uns des répondants qui disent que l'algorithme "régulier" qui vérifie toutes les paires de positions de bits et recherche le 3ème bit, même s'il nécessiterait O (k ^ 2) dans le pire des cas, en réalité parce que le pire des cas a besoin de chaînes binaires éparses, est O (n ln n).

Bref, voici le programme ci-dessous. C'est un programme de style Monte-Carlo qui exécute un grand nombre d'essais NTRIALS pour la constante n, et génère aléatoirement des ensembles de bits pour une plage de valeurs k en utilisant des processus de Bernoulli avec une densité de un contrainte entre des limites pouvant être spécifiées, et enregistre le temps d'exécution de trouver ou de ne pas trouver un triplet de triples espacés uniformément, temps mesuré en pas PAS en temps CPU. Je l'ai couru pendant n = 64, 256, 1024, 4096, 16384 * (toujours en cours d'exécution), d'abord un test avec 500000 essais pour voir quelles valeurs k prennent le temps de fonctionnement le plus long, puis un autre test avec 5000000 essais avec des essais réduits- focus sur la densité pour voir à quoi ressemblent ces valeurs. Les temps de fonctionnement les plus longs se produisent avec une densité très faible (par exemple pour n = 4096, les pics de temps de fonctionnement sont dans la plage k = 16-64, avec un pic doux pour le temps de fonctionnement moyen à 4212 étapes @ k = 31, la durée de fonctionnement maximale a culminé à 5101 étapes @ k = 58). Il semble qu'il faudrait des valeurs extrêmement élevées de N pour que le pas O (k ^ 2) du cas le plus défavorable devienne plus grand que le pas O (n) où vous parcourez la chaîne de bits pour trouver les indices de position de 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

J'ai des problèmes avec les pires scénarios avec des millions de chiffres. Fuzzing /dev/urandomvous donne essentiellement O (n), mais je sais que le pire des cas est pire que cela. Je ne peux pas dire à quel point c'est pire. Pour les petits n, il est trivial de trouver des intrants aux alentours 3*n*log(n), mais il est étonnamment difficile de les différencier d'un autre ordre de croissance pour ce problème particulier.

Est-ce que quelqu'un qui travaillait sur des entrées du pire des cas peut générer une chaîne avec une longueur supérieure, disons, cent mille?

Une adaptation de l'algorithme de Rabin-Karp pourrait vous être possible. Sa complexité est de 0 (n) donc cela pourrait vous aider.

Jetez un œil à http://en.wikipedia.org/wiki/Rabin-Karp_string_search_algorithm

Serait-ce une solution? Je ne sais pas si c'est O (nlogn) mais à mon avis c'est mieux que O (n²) car le seul moyen de ne pas trouver un triplet serait une distribution de nombres premiers.

Il y a place à amélioration, le deuxième trouvé 1 pourrait être le suivant premier 1. Aussi pas de vérification d'erreur.

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

Je pense que cet algorithme a une complexité O (n log n) (C ++, DevStudio 2k5). Maintenant, je ne connais pas les détails sur la façon d'analyser un algorithme pour déterminer sa complexité, j'ai donc ajouté des informations de collecte de métriques au code. Le code compte le nombre de tests effectués sur la séquence de 1 et de 0 pour une entrée donnée (j'espère que je n'ai pas fait une boule de l'algorithme). Nous pouvons comparer le nombre réel de tests à la valeur O et voir s'il existe une corrélation.

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

Ce programme génère le nombre de tests pour chaque longueur de chaîne jusqu'à 32 caractères. Voici les résultats:

 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

J'ai également ajouté les valeurs «n log n». Tracez-les à l'aide de l'outil graphique de votre choix pour voir une corrélation entre les deux résultats. Cette analyse s'étend-elle à toutes les valeurs de n? Je ne sais pas.