Découvrez de longs motifs

Étant donné une liste sortingée de nombres, je voudrais trouver la plus longue sous-séquence où les différences entre les éléments successifs augmentent géomésortingquement. Donc, si la liste est

1, 2, 3, 4, 7, 15, 27, 30, 31, 81 

alors la sous-séquence est 1, 3, 7, 15, 31 . En variante, considérons 1, 2, 5, 6, 11, 15, 23, 41, 47 qui ont les sous-séquences 5, 11, 23, 47 avec a = 3 et k = 2.

Cela peut-il être résolu en O ( n 2 ) temps? Où n est la longueur de la liste.

Je m’intéresse à la fois au cas général où la progression des différences est ak , ak 2 , ak 3 , etc., où a et k sont des nombres entiers, et dans le cas particulier où a = 1, la progression de la différence est k , k 2 , k 3 , etc.

Mettre à jour

J’ai amélioré l’algorithme en prenant une moyenne de O (M + N ^ 2) et des besoins en mémoire de O (M + N). Principalement, c’est le même que le protocole décrit ci-dessous, mais pour calculer les facteurs possibles A, K pour ech diference D, je précharge une table. Ce tableau prend moins d’une seconde pour être construit pour M = 10 ^ 7.

J’ai réalisé une implémentation en C qui prend moins de 10 minutes pour résoudre N = 10 ^ 5 éléments entiers aléatoires différents.

Voici le code source de C: Pour exécuter, il suffit de faire: gcc -O3 -o findgeo findgeo.c

 #include  #include  #include  #include  #include  struct Factor { int a; int k; struct Factor *next; }; struct Factor *factors = 0; int factorsL=0; void ConstructFactors(int R) { int a,k,C; int R2; struct Factor *f; float seconds; clock_t end; clock_t start = clock(); if (factors) free(factors); factors = malloc (sizeof(struct Factor) *((R>>1) + 1)); R2 = R>>1 ; for (a=0;a<=R2;a++) { factors[a].a= a; factors[a].k=1; factors[a].next=NULL; } factorsL=R2+1; R2 = floor(sqrt(R)); for (k=2; k<=R2; k++) { a=1; C=a*k*(k+1); while (C>= 1; f=malloc(sizeof(struct Factor)); *f=factors[C]; factors[C].a=a; factors[C].k=k; factors[C].next=f; a++; C=a*k*(k+1); } } end = clock(); seconds = (float)(end - start) / CLOCKS_PER_SEC; printf("Construct Table: %f\n",seconds); } void DestructFactors() { int i; struct Factor *f; for (i=0;inext; free(factors[i].next); factors[i].next=f; } } free(factors); factors=NULL; factorsL=0; } int ipow(int base, int exp) { int result = 1; while (exp) { if (exp & 1) result *= base; exp >>= 1; base *= base; } return result; } void findGeo(int **bestSolution, int *bestSolutionL,int *Arr, int L) { int i,j,D; int mustExistToBeBetter; int R=Arr[L-1]-Arr[0]; int *possibleSolution; int possibleSolutionL=0; int exp; int NextVal; int idx; int kMax,aMax; float seconds; clock_t end; clock_t start = clock(); kMax = floor(sqrt(R)); aMax = floor(R/2); ConstructFactors(R); *bestSolutionL=2; *bestSolution=malloc(0); possibleSolution = malloc(sizeof(int)*(R+1)); struct Factor *f; int *H=malloc(sizeof(int)*(R+1)); memset(H,0, sizeof(int)*(R+1)); for (i=0;i>1); while (f) { idx=Arr[i] + f->a * f->k - Arr[0]; if ((f->k <= kMax)&& (f->ak ==1) { mustExistToBeBetter = Arr[i] + f->a * (*bestSolutionL); } else { mustExistToBeBetter = Arr[i] + f->a * f->k * (ipow(f->k,*bestSolutionL) - 1)/(f->k-1); } if (mustExistToBeBetter< Arr[L-1]+1) { idx= floor(mustExistToBeBetter - Arr[0]); } else { idx = R+1; } if ((idx<=R)&&H[idx]) { possibleSolution[0]=Arr[i]; possibleSolution[1]=Arr[i] + f->a*f->k; possibleSolution[2]=Arr[j]; possibleSolutionL=3; exp = f->k * f->k * f->k; NextVal = Arr[j] + f->a * exp; idx=NextVal - Arr[0]; while ( (idx<=R) && H[idx]) { possibleSolution[possibleSolutionL]=NextVal; possibleSolutionL++; exp = exp * f->k; NextVal = NextVal + f->a * exp; idx=NextVal - Arr[0]; } if (possibleSolutionL > *bestSolutionL) { free(*bestSolution); *bestSolution = possibleSolution; possibleSolution = malloc(sizeof(int)*(R+1)); *bestSolutionL=possibleSolutionL; kMax= floor( pow (R, 1/ (*bestSolutionL) )); aMax= floor(R / (*bestSolutionL)); } } } f=f->next; } } } if (*bestSolutionL == 2) { free(*bestSolution); possibleSolutionL=0; for (i=0; (i<2)&&(i0) printf(","); printf("%d",Sol[i]); } printf("]\n"); printf("Size: %d\n",SolL); free(Sol); free(A); return EXIT_SUCCESS; } 

Démostration

Je vais essayer de démontrer que l’algorithme que j’ai proposé est O (N`2 + M) en moyenne pour une séquence aléatoire également dissortingbuée. Je ne suis pas un mathématicien et je n’ai pas l’habitude de faire ce genre de démonstrations, alors n’hésitez pas à me corriger si vous voyez une erreur.

Il y a 4 boucles en retrait, les deux premières sont le facteur N ^ 2. Le M est pour le calcul du tableau des facteurs possibles).

La troisième boucle est exécutée une seule fois en moyenne pour chaque paire. Vous pouvez voir cela vérifier la taille du tableau des facteurs pré-calculés. Sa taille est M lorsque N-> inf. Donc, la moyenne des étapes pour chaque paire est M / M = 1.

Donc, la preuve arrive à vérifier que la quasortingème boucle. (Celui qui parcourt les bonnes séquences est exécuté moins que ou égal à O (N ^ 2) pour toutes les paires.

Pour démontrer cela, je considérerai deux cas: un où M >> N et d’autres où M ~ = N. où M est la différence maximale du tableau initial: M = S (n) -S (1).

Pour le premier cas, (M >> N) la probabilité de trouver une coïncidence est p = N / M. Pour démarrer une séquence, celle-ci doit coïncider avec le deuxième élément et l’élément b + 1, où b est la longueur de la meilleure séquence jusqu’à maintenant. Donc la boucle entrera N ^ 2 * (N / M) ^ 2 fois. Et la longueur moyenne de cette série (en supposant une série infinie) est p / (1-p) = N / (M-N) . Donc, le nombre total de fois que la boucle sera exécutée est N ^ 2 * (N / M) ^ 2 * N / (M-N) . Et c’est proche de 0 quand M >> N. Le problème est que M ~ = N.

Considérons maintenant ce cas où M ~ = N. Considérons que b est la meilleure longueur de séquence jusqu’à maintenant. Pour le cas A = k = 1, alors la séquence doit commencer avant Nb, donc le nombre de séquences sera Nb, et les temps qui iront pour la boucle seront un maximum de (Nb) * b.

Pour A> 1 et k = 1 on peut extrapoler à (N-A * b / d) * b où d est M / N (la distance moyenne entre les nombres). Si nous ajoutons pour tous les A de 1 à dN / b, nous voyons une limite supérieure de:

\ sum_ {A = 1} ^ {dN / b} \ left (N- \ frac {Ab} {d} \ right) b = \ frac {N ^ 2d} {2}

Pour les cas où k> = 2, on voit que la séquence doit commencer avant N-A * k ^ b / d Ainsi, la boucle entrera une moyenne de A * k ^ b / d) * b et en ajoutant pour tout À partir de 1 à dN / k ^ b, il donne une limite de

\ sum_ {A = 1} ^ {dN / k ^ b} \ left (N- \ frac {Ak ^ b} {d} \ right) b = \ frac {bN ^ 2d} {2k ^ b}

Ici, le pire des cas est quand b est minimum. Puisque nous considérons des séries minimales, considérons un très mauvais cas de b = 2, donc le nombre de passes pour la 4ème boucle pour un k donné sera inférieur à

\ frac {dN ^ 2} {k ^ 2} .

Et si on ajoute tous les k de 2 à l’infini sera:

\ sum_ {k = 2} ^ {\ infty} \ frac {dN ^ 2} {k ^ 2} = dN ^ 2 \ gauche (\ frac {\ pi ^ 2} {6} -1 \ droit)

Donc, en ajoutant toutes les passes pour k = 1 et k> = 2, nous avons un maximum de:

\ frac {N ^ 2d} {2} + N ^ 2d \ gauche (\ frac {\ pi ^ 2} {6} -1 \ droit) = N ^ 2d \ gauche (\ frac {\ pi ^ 2} {6 } - \ frac {1} {2} \ right) \ simeq 1.45N ^ 2d

Notez que d = M / N = 1 / p.

Nous avons donc deux limites, une qui va à l’infini quand d = 1 / p = M / N passe à 1 et l’autre qui va à l’infini quand d passe à l’infini. Donc, notre limite est le minimum des deux, et le pire est lorsque les deux équations se croisent. Donc, si nous résolvons l’équation:

N ^ 2d \ left (\ frac {\ pi ^ 2} {6} - \ frac {1} {2} \ right) = N ^ 2 \ gauche (\ frac {N} {M} \ right) ^ 2 \ frac {N} {MN} = N ^ 2 \ gauche (\ frac {1} {d} \ right) ^ 2 \ frac {1} {d-1}

on voit que le maximum est quand d = 1.353

Il est donc démontré que les quatre dernières boucles seront traitées moins de 1,55 N ^ 2 fois au total.

Bien sûr, c’est pour le cas moyen. Dans le pire des cas, je ne suis pas en mesure de trouver un moyen de générer des séries dont la quasortingème boucle est supérieure à O (N ^ 2) et je crois fermement qu’elles n’existent pas, mais je ne suis pas mathématicien pour le prouver.

Ancienne réponse

Voici une solution en moyenne de O ((n ^ 2) * racine_cube (M)) où M est la différence entre le premier et le dernier élément du tableau. Et les besoins en mémoire de O (M + N).

1.- Construis un tableau H de longueur M pour que M [i – S [0]] = true si j’existe dans le tableau initial et faux si ce dernier n’existe pas.

2.- Pour chaque paire du tableau S [j], S [i] fait:

2.1 Vérifier s’il peut s’agir des premier et troisième éléments d’une solution possible. Pour ce faire, calculez toutes les paires A, K possibles qui correspondent à l’équation S (i) = S (j) + AK + AK ^ 2. Cochez cette question pour voir comment résoudre ce problème. Et vérifiez qu’il existe le deuxième élément: S [i] + A * K

2.2 Vérifiez également l’existence de l’élément une position plus loin que la meilleure solution que nous ayons. Par exemple, si la meilleure solution que nous ayons jusqu’ici est 4 éléments longs, vérifiez qu’il existe l’élément A [j] + A K + A K ^ 2 + A K ^ 3 + A K ^ 4

2.3 Si les versions 2.1 et 2.2 sont vraies, itérez combien de temps cette série est définie et définissez-la comme la meilleure solution jusqu’à maintenant est plus longue que la dernière.

Voici le code en javascript:

 function getAKs(A) { if (A / 2 != Math.floor(A / 2)) return []; var solution = []; var i; var SR3 = Math.pow(A, 1 / 3); for (i = 1; i <= SR3; i++) { var B, C; C = i; B = A / (C * (C + 1)); if (B == Math.floor(B)) { solution.push([B, C]); } B = i; C = (-1 + Math.sqrt(1 + 4 * A / B)) / 2; if (C == Math.floor(C)) { solution.push([B, C]); } } return solution; } function getBestGeometricSequence(S) { var i, j, k; var bestSolution = []; var H = Array(S[S.length-1]-S[0]); for (i = 0; i < S.length; i++) H[S[i] - S[0]] = true; for (i = 0; i < S.length; i++) { for (j = 0; j < i; j++) { var PossibleAKs = getAKs(S[i] - S[j]); for (k = 0; k < PossibleAKs.length; k++) { var A = PossibleAKs[k][0]; var K = PossibleAKs[k][17]; var mustExistToBeBetter; if (K==1) { mustExistToBeBetter = S[j] + A * bestSolution.length; } else { mustExistToBeBetter = S[j] + A * K * (Math.pow(K,bestSolution.length) - 1)/(K-1); } if ((H[S[j] + A * K - S[0]]) && (H[mustExistToBeBetter - S[0]])) { var possibleSolution=[S[j],S[j] + A * K,S[i]]; exp = K * K * K; var NextVal = S[i] + A * exp; while (H[NextVal - S[0]] === true) { possibleSolution.push(NextVal); exp = exp * K; NextVal = NextVal + A * exp; } if (possibleSolution.length > bestSolution.length) { bestSolution = possibleSolution; } } } } } return bestSolution; } //var A= [ 1, 2, 3,5,7, 15, 27, 30,31, 81]; var A=[]; for (i=1;i<=3000;i++) { A.push(i); } var sol=getBestGeometricSequence(A); $("#result").html(JSON.stringify(sol)); 

Vous pouvez vérifier le code ici: http://jsfiddle.net/6yHyR/1/

Je maintiens l'autre solution car je crois que c'est encore mieux quand M est très gros comparé à N.

Pour commencer avec quelque chose, voici une solution simple en JavaScript:

 var input = [0.7, 1, 2, 3, 4, 7, 15, 27, 30, 31, 81], output = [], indexes, values, i, index, value, i_max_length, i1, i2, i3, j1, j2, j3, difference12a, difference23a, difference12b, difference23b, scale_factor, common_ratio_a, common_ratio_b, common_ratio_c, error, EPSILON = 1e-9, common_ratio_is_integer, resultDiv = $("#result"); for (i1 = 0; i1 < input.length - 2; ++i1) { for (i2 = i1 + 1; i2 < input.length - 1; ++i2) { scale_factor = difference12a = input[i2] - input[i1]; for (i3 = i2 + 1; i3 < input.length; ++i3) { difference23a = input[i3] - input[i2]; common_ratio_1a = difference23a / difference12a; common_ratio_2a = Math.round(common_ratio_1a); error = Math.abs((common_ratio_2a - common_ratio_1a) / common_ratio_1a); common_ratio_is_integer = error < EPSILON; if (common_ratio_2a > 1 && common_ratio_is_integer) { indexes = [i1, i2, i3]; j1 = i2; j2 = i3 difference12b = difference23a; for (j3 = j2 + 1; j3 < input.length; ++j3) { difference23b = input[j3] - input[j2]; common_ratio_1b = difference23b / difference12b; common_ratio_2b = Math.round(common_ratio_1b); error = Math.abs((common_ratio_2b - common_ratio_1b) / common_ratio_1b); common_ratio_is_integer = error < EPSILON; if (common_ratio_is_integer && common_ratio_2a === common_ratio_2b) { indexes.push(j3); j1 = j2; j2 = j3 difference12b = difference23b; } } values = []; for (i = 0; i < indexes.length; ++i) { index = indexes[i]; value = input[index]; values.push(value); } output.push(values); } } } } if (output !== []) { i_max_length = 0; for (i = 1; i < output.length; ++i) { if (output[i_max_length].length < output[i].length) i_max_length = i; } for (i = 0; i < output.length; ++i) { if (output[i_max_length].length == output[i].length) resultDiv.append("

[" + output[i] + "]

"); } }

Sortie:

 [1, 3, 7, 15, 31] 

Je trouve les trois premiers éléments de chaque candidat de sous-séquence, calcule le facteur d’échelle et le ratio commun à partir d’eux, et si le ratio commun est un nombre entier, je répète les éléments restants après le troisième et les ajoute à la suite. s’insère dans la progression géomésortingque définie par les trois premiers éléments. En dernier lieu, je sélectionne la séquence / s qui a / a la plus grande longueur.

Voici ma solution en Javascript. Il devrait être proche de O (n ^ 2) sauf peut-être dans certains cas pathologiques.

 function bsearch(Arr,Val, left,right) { if (left == right) return left; var m=Math.floor((left + right) /2); if (Val <= Arr[m]) { return bsearch(Arr,Val,left,m); } else { return bsearch(Arr,Val,m+1,right); } } function findLongestGeometricSequence(S) { var bestSolution=[]; var i,j,k; var H={}; for (i=0;i bestSolution.length) bestSolution=possibleSolution; K--; } else { K=Math.floor(K); } if (K>0) { var NextPossibleMidValue= (S[i] + K*S[j]) / (K +1); k++; if (S[k] 

Petite explication

Si nous prenons 3 nombres du tableau S (j)

Ce serait une solution O (n ^ 3), mais vous pouvez avoir l'avantage que k doit être entier pour limiter les points S (k) sélectionnés.

Dans le cas où un est connu, alors vous pouvez calculer a (k) et vous devez vérifier un seul numéro dans la troisième boucle, donc ce cas sera clairement un O (n ^ 2).

Je pense que cette tâche est liée à il n’y a pas si longtemps publié la plus longue sous-séquence équidistante . Je viens de modifier un peu mon algorithme en Python:

 from math import sqrt def add_precalc(precalc, end, (a, k), count, res, N): if end + a * k ** res[1]["count"] > N: return x = end + a * k ** count if x > N or x < 0: return if precalc[x] is None: return if (a, k) not in precalc[x]: precalc[x][(a, k)] = count return def factors(n): res = [] for x in range(1, int(sqrt(n)) + 1): if n % x == 0: y = n / x res.append((x, y)) res.append((y, x)) return res def work(input): precalc = [None] * (max(input) + 1) for x in input: precalc[x] = {} N = max(input) res = ((0, 0), {"end":0, "count":0}) for i, x in enumerate(input): for y in input[i::-1]: for a, k in factors(x - y): if (a, k) in precalc[x]: continue add_precalc(precalc, x, (a, k), 2, res, N) for step, count in precalc[x].iteritems(): count += 1 if count > res[1]["count"]: res = (step, {"end":x, "count":count}) add_precalc(precalc, x, step, count, res, N) precalc[x] = None d = [res[1]["end"]] for x in range(res[1]["count"] - 1, 0, -1): d.append(d[-1] - res[0][0] * res[0][1] ** x) d.reverse() return d 

explication

  • Traverser le tableau
  • Pour chaque élément précédent du tableau, calculer les facteurs de la différence entre l’élément précédent et l’élément précédent, puis calculer le prochain élément possible de la séquence et le sauvegarder dans le tableau précalculé.
  • Donc, quand on arrive à l’élément i il y a déjà toutes les séquences possibles avec l’élément i dans le tableau de précalc. Nous devons donc calculer le prochain élément possible et le sauvegarder dans Precalc.

Actuellement, il y a une place dans l’algorithme qui pourrait être une factorisation lente de chaque numéro précédent. Je pense que cela pourrait être rendu plus rapide avec deux optimisations:

  • algorithme de factorisation plus efficace
  • trouver un moyen de ne pas voir à chaque élément du tableau, en utilisant le fait que le tableau est sortingé et qu’il existe déjà des séquences précalculées

Python:

 def subseq(a): seq = [] aset = set(a) for i, x in enumerate(a): # elements after x for j, x2 in enumerate(a[i+1:]): j += i + 1 # enumerate starts j at 0, we want a[j] = x2 bk = x2 - x # b*k (assuming k and k's exponent start at 1) # given b*k, bruteforce values of k for k in range(1, bk + 1): items = [x, x2] # our subsequence so far nextdist = bk * k # what x3 - x2 should look like while items[-1] + nextdist in aset: items.append(items[-1] + nextdist) nextdist *= k if len(items) > len(seq): seq = items return seq 

Le temps d’exécution est O(dn^3) , où d est la distance (moyenne?) Entre deux éléments, et n est bien sûr len(a) .

En fait, c’est exactement la même question que la sous -séquence à espacement égal le plus long , il suffit de considérer le logarithme de vos données. Si la suite est a, ak, ak ^ 2, ak ^ 3 , la valeur logarithmique est ln (a), ln (a) + ln (k), ln (a) + 2ln (k), ln (a) + 3ln (k) , il est donc également espacé. Le contraire est bien sûr vrai. Il y a beaucoup de code différent dans la question ci-dessus.

Je ne pense pas que le cas particulier a = 1 puisse être résolu plus efficacement qu’une adaptation d’un algorithme ci-dessus.