Détecter une sous-séquence qui est une progression arithmétique, dans une séquence triée

cs.stackexchange https://cs.stackexchange.com/questions/18951

Question

J'ai un problème suivant: j'ai une séquence triée de $ n $ entiers (supposons qu'ils augmentent monotone). Je tiens à vérifier s'il y a une sous-séquence de longueur $ ge n / 4 $, de sorte que les éléments consécutifs de la sous-séquence diffèrent tous de la même valeur.

Par exemple, dans la séquence [3,4,5,8,12], il existe deux de ces sous-séquences: [3,4,5] (la différence est 1) et [4,8,12] (la différence est 4) . Ainsi, la longueur de la plus longue subséquence est 3 pour cet exemple. Puisque 3 $ ge 5/4 $, la réponse est oui, il y a une sous-séquence de longueur $ ge n / 4 $ avec la propriété souhaitée.

Dans ma situation réelle, la séquence est de longueur $ n environ 10 ^ 6 $, et les éléments sont tous des numéros à 9 chiffres. Existe-t-il un algorithme efficace pour résoudre ce problème?

Mon approche naïve était de créer un produit cartésien avec des différences absolues entre les nombres:

$$ Left ( begin {array} {ccccc} 0 & 1 & 2 & 5 & 9 1 & 0 & 1 & 4 & 8 2 & 1 & 0 & 3 & 7 5 & 4 & 3 & 0 & 4 9 & 8 & 7 & 4 & 0 end {array} droite) $$

Puis concentrez-vous sur la partie supérieure-droite et calculez le nombre d'occurrences de chaque différence, donc:

$$ || text {diff-by-1} || = 2 => text {3 nombres diff by 1} || text {diff-by-4} || = 2 => text {3 nombres diff by 4} $$

C'est très simple et très inefficace. Il nécessite beaucoup de comparaisons et ne fait pas évoluer (du tout): son temps d'exécution est $ theta (n ^ 2) $. Dans mon scénario réel, ma séquence est de ~ 10 ^ 6 de long, donc c'est trop lent.

Pour vous donner une image plus large car il y a peut-être une approche beaucoup meilleure (probabiliste) de ce problème: après que la plus grande sous-séquence est trouvée, je veux calculer le rapport simple:

$$ r: = frac { text {la plus grande longueur de sous-séquence}} { text {longueur de séquence}} $$

Et si $ r $ est plus grand, une valeur fixe, je veux relancer l'alarme (ou faire tout ce que j'ai à faire ;-)).

Merci pour toute aide, références, pointeurs, etc.

BTW: Voici des choses que je regardais / je regardais:

Mise à jour: pensait un peu plus à ce sujet et a commencé de la fin, donc au lieu de calculer toutes les différences entre les nombres (coin supérieur droit de la matrice), je peux dériver une petite valeur $ k $ de "valeur fixe" que j'ai mentionnée à la fin de question originale. Par exemple, si je vais augmenter l'alarme lorsque 25% de tous les nombres sont dans une certaine séquence, je dois me concentrer sur de petits "triangles" dans la matrice et le nombre de calculs requis est plus petit (beaucoup plus petit). Lorsque j'ajoute un échantillonnage, il devrait être assez simple pour implémenter à grande échelle.

MISE À JOUR 2 - Algorithme @DW implémenté, échantillon d'exécution ci-dessous:

    11:51:06 ~$ time nodejs progression.js 
    L: 694000000,694000002,694000006,694000007,694000009,694000010,
        694000013,694000015,694000018,694000019,694000021,694000022,694000023,
    694000026,694000028,694000030,694000034,694000036,694000038,694000040,
    694000043,694000045,694000046,694000048,694000051,694000053,694000055,
    694000057,694000060,694000061,694000063,694000067,694000069,694000072,
    694000074,694000076,694000077,694000079,694000080,694000082,694000083,
    694000084,694000086,694000090,694000091,694000093,694000095,694000099,
    694000102,694000103,694000105,694000108,694000109,694000113,694000116,
    694000118,694000122,694000125,694000128,694000131,694000134,694000137,
    694000141,694000143,694000145,694000148,694000152,694000153,694000154,
    694000157,694000160,694000162,694000163,694000166,694000170,694000173,
    694000174,694000177,694000179,694000180,694000181,694000184,694000185,
    694000187,694000189,694000193,694000194,694000198,694000200,694000203,
    694000207,694000211,694000215,694000219,694000222,694000226,694000228,
    694000232,694000235,694000236
    N: 100
    P: 0.1
    L: 10 (min)
    D: 26 (max)
    [ 9, 18, 27, 36, 45, 54, 63, 72, 81, 90 ]
    Found progression of 10 elements, difference: 16 starts: 694000045, ends: 694000189.

    real    0m0.065s
    user    0m0.052s
    sys 0m0.004s

Pas de solution correcte

Licencié sous: CC-BY-SA avec attribution
Non affilié à cs.stackexchange
scroll top