algorithm - problems - Descubre patrones largos

dynamic programming problems

Question

Dada una lista ordenada de números, me gustaría encontrar la subsecuencia más larga donde las diferencias entre los elementos sucesivos están aumentando geométricamente. Entonces, si la lista es

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

entonces la subsecuencia es 1, 3, 7, 15, 31 . Alternativamente considere 1, 2, 5, 6, 11, 15, 23, 41, 47 que tiene subsecuencia 5, 11, 23, 47 con a = 3 yk = 2.

¿Puede esto resolverse en el tiempo O ( n ² )? Donde n es la longitud de la lista.

Estoy interesado tanto en el caso general donde la progresión de las diferencias es ak , ak ² , ak ³ , etc., donde tanto a como k son números enteros, y en el caso especial donde a = 1, entonces la progresión de la diferencia es k , k ² , k ³ , etc.

Answer 1

Aquí está mi solución en Javascript. Debe estar cerca de O (n ^ 2), excepto en algunos casos patológicos.

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<S.length;i++) H[S[i]]=true;

    for (i=0;i<S.length;i++) {
        for (j=0;j<i;j++) {
            for (k=j+1;k<i;) {
                var possibleSolution=[S[j],S[k],S[i]];

                var K = (S[i] - S[k]) / (S[k] - S[j]);
                var A = (S[k] - S[j]) * (S[k] - S[j]) / (S[i] - S[k]); 

                if ((Math.floor(K) == K) && (Math.floor(A)==A)) {
                    exp= K*K*K;
                    var NextVal= S[i] + A * exp;
                    while (H[NextVal] === true) {
                        possibleSolution.push(NextVal);
                        exp = exp * K;
                        NextVal= NextVal + A * exp;                
                    }

                    if (possibleSolution.length > 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]<NextPossibleMidValue) {
                        k=bsearch(S,NextPossibleMidValue, k+1, i);
                    }
                } else {
                    k=i;
                }
            }        
        }
    }
    return bestSolution;
}


function Run() {
    var MyS= [0.7, 1, 2, 3, 4, 5,6,7, 15, 27, 30,31, 81];

    var sol = findLongestGeometricSequence(MyS); 

    alert(JSON.stringify(sol));
}

Pequeña explicación

Si tomamos 3 números de la matriz S (j) <S (k) <S (i), entonces puede calcular a y k para que: S (k) = S (j) + a * ky S (i) = S (k) + a * k ^ 2 (2 ecuaciones y 2 incógnitas). Con eso en mente, puede verificar si existe un número en la matriz que sea S (siguiente) = S (i) + a * k ^ 3. Si ese es el caso, continúe comprobando para S (next2) = S (siguiente) + a * k ^ 4 y así sucesivamente.

Esta sería una solución O (n ^ 3), pero puede tener la ventaja de que k debe ser un número entero para limitar los puntos S (k) seleccionados.

En caso de que a se conozca, entonces puede calcular a (k) y necesita verificar solo un número en el tercer bucle, por lo que este caso será claramente un O (n ^ 2).

Answer 2

Creo que esta tarea está relacionada con no hace mucho tiempo publicada Subsecuencia más espaciada igualmente espaciada . Acabo de modificar mi algoritmo en Python un poco:

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

explicación

• Atravesando la matriz
• Para cada elemento anterior de la matriz, calcule los factores de la diferencia entre el elemento anterior actual y el anterior, y luego precalcule el siguiente elemento posible de la secuencia y guárdelo en la matriz precalculada
• Por lo tanto, al llegar al elemento i ya existen todas las secuencias posibles con el elemento i en la matriz precalculada, por lo que debemos calcular el siguiente elemento posible y guardarlo en precalcificación.

Actualmente hay un lugar en el algoritmo que podría ser la factorización lenta de cada número anterior. Creo que podría hacerse más rápido con dos optimizaciones:

• algoritmo de factorización más efectivo
• encuentre una forma de no ver en cada elemento de la matriz, usando el hecho de que la matriz está ordenada y ya hay secuencias precalculadas

Answer 3

De hecho, es exactamente la misma pregunta que la subsecuencia de espaciamiento equitativo más largo , solo debes considerar el logaritmo de tus datos. Si la secuencia es a, ak, ak ^ 2, ak ^ 3 , el valor logarítmico es ln (a), ln (a) + ln (k), ln (a) + 2ln (k), ln (a) + 3ln (k) , por lo que está igualmente espaciado. Lo opuesto es por supuesto cierto. Hay muchos códigos diferentes en la pregunta anterior.

No creo que el caso especial a = 1 se pueda resolver de manera más eficiente que una adaptación de un algoritmo anterior.

Answer 4

Para comenzar, hay una solución 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("<p>[" + output[i] + "]</p>");
    }
}

Salida:

[1, 3, 7, 15, 31]

Encuentro los primeros tres ítems de cada candidato a subsecuencia, calculo el factor de escala y la razón común a partir de ellos, y si la razón común es entera, entonces itero sobre los elementos restantes después del tercero, y los agrego a la subsecuencia, que encajar en la progresión geométrica definida por los primeros tres elementos. Como último paso, selecciono la / s secuencia / s que tiene / tiene la longitud más grande.

Answer 5

Pitón:

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

El tiempo de ejecución es O(dn^3) , donde d es la distancia (promedio?) Entre dos elementos, y n es, por supuesto, len(a) .

Answer 6

Actualizar

Hice una mejora del algoritmo que toma un promedio de O (M + N ^ 2) y las necesidades de memoria de O (M + N). Principalmente es el mismo que el protocolo descrito a continuación, pero para calcular los posibles factores A, K para la diferencia D, precomprimo una tabla. Esta tabla tarda menos de un segundo en construirse para M = 10 ^ 7.

He realizado una implementación C que requiere menos de 10 minutos para resolver N = 10 ^ 5 elementos enteros aleatorios diferentes.

Aquí está el código fuente en C: Para ejecutar simplemente hacer: gcc -O3 -o findgeo findgeo.c

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <memory.h>
#include <time.h>

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<R) {
            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;i<factorsL;i++) {
        while (factors[i].next) {
            f=factors[i].next->next;
            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<L;i++) {
        H[ Arr[i]-Arr[0] ]=1;
    }
    for (i=0; i<L-2;i++) {
        for (j=i+2; j<L; j++) {
            D=Arr[j]-Arr[i];
            if (D & 1) continue;
            f = factors + (D >>1);
            while (f) {
                idx=Arr[i] + f->a * f->k  - Arr[0];
                if ((f->k <= kMax)&& (f->a<aMax)&&(idx<=R)&&H[idx]) {
                    if (f->k ==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)&&(i<L); i++ ) {
            possibleSolution[possibleSolutionL]=Arr[i];
            possibleSolutionL++;
        }
        *bestSolution = possibleSolution;
        *bestSolutionL=possibleSolutionL;
    } else {
        free(possibleSolution);
    }
    DestructFactors();
    free(H);

    end = clock();
    seconds = (float)(end - start) / CLOCKS_PER_SEC;
    printf("findGeo: %f/n",seconds);
}

int compareInt (const void * a, const void * b)
{
    return *(int *)a - *(int *)b;
}

int main(void) {
    int N=100000;
    int R=10000000;
    int *A = malloc(sizeof(int)*N);
    int *Sol;
    int SolL;
    int i;


    int *S=malloc(sizeof(int)*R);
    for (i=0;i<R;i++) S[i]=i+1;

    for (i=0;i<N;i++) {
        int r = rand() % (R-i);
        A[i]=S[r];
        S[r]=S[R-i-1];
    }

    free(S);
    qsort(A,N,sizeof(int),compareInt);

/*
    int step = floor(R/N);
    A[0]=1;
    for (i=1;i<N;i++) {
        A[i]=A[i-1]+step;
    }
*/

    findGeo(&Sol,&SolL,A,N);

    printf("[");
    for (i=0;i<SolL;i++) {
        if (i>0) printf(",");
        printf("%d",Sol[i]);
    }
    printf("]/n");
    printf("Size: %d/n",SolL);

    free(Sol);
    free(A);
    return EXIT_SUCCESS;
}

Demostración

Trataré de demostrar que el algoritmo que propuse es en promedio para una secuencia aleatoria igualmente distribuida. No soy matemático y no estoy acostumbrado a hacer este tipo de demostraciones, así que no dudes en corregirme cualquier error que puedas ver.

Hay 4 bucles sangrados, los dos primeros son el factor N ^ 2. La M es para el cálculo de la tabla de posibles factores).

El tercer ciclo se ejecuta solo una vez en promedio para cada par. Puede ver esto comprobando el tamaño de la tabla de factores precalculados. Su tamaño es M cuando N-> inf. Entonces, los pasos promedio para cada par son M / M = 1.

Entonces la prueba pasa para verificar que el cuarto ciclo. (El que atraviesa las secuencias bien hechas se ejecuta menos que o igual a O (N ^ 2) para todos los pares.

Para demostrar eso, consideraré dos casos: uno donde M >> N y otro donde M ~ = N. Donde M es la diferencia máxima de la matriz inicial: M = S (n) -S (1).

Para el primer caso, (M >> N) la probabilidad de encontrar una coincidencia es p = N / M. Para comenzar una secuencia, debe coincidir el segundo elemento y b + 1, donde b es la longitud de la mejor secuencia hasta ahora. Entonces el ciclo entrará veces. Y la duración promedio de esta serie (suponiendo una serie infinita) es . Entonces, el número total de veces que se ejecutará el ciclo es . Y esto está cerca de 0 cuando M >> N. El problema aquí es cuando M ~ = N.

Ahora consideremos este caso donde M ~ = N. Consideremos que b es la mejor longitud de secuencia hasta ahora. Para el caso A = k = 1, entonces la secuencia debe comenzar antes de Nb, entonces el número de secuencias será Nb, y los tiempos que irán para el ciclo serán un máximo de (Nb) * b.

Para A> 1 yk = 1 podemos extrapolar a donde d es M / N (la distancia promedio entre los números). Si sumamos para todas las A desde 1 a dN / b, vemos un límite superior de:

Para los casos donde k> = 2, vemos que la secuencia debe comenzar antes , Entonces el ciclo ingresará un promedio de y agregar para todos Como de 1 a dN / k ^ b, da un límite de

Aquí, el peor caso es cuando b es mínimo. Debido a que estamos considerando series mínimas, consideremos un peor caso de b = 2, por lo que el número de pases para el 4º ciclo para un k determinado será menor que

.

Y si sumamos todas las k de 2 a infinito, seremos:

Entonces, sumando todos los pases para k = 1 y k> = 2, tenemos un máximo de:

Tenga en cuenta que d = M / N = 1 / p.

Entonces tenemos dos límites, Uno que va al infinito cuando d = 1 / p = M / N va a 1 y otro que va a infinito cuando d va a infinito. Entonces nuestro límite es el mínimo de ambos, y el peor caso es cuando ambas equedades se cruzan. Entonces, si resolvemos la ecuación:

vemos que el máximo es cuando d = 1.353

Por lo tanto, se demuestra que los cuatro bucles serán procesados ​​a menos de 1.55N ^ 2 veces en total.

Por supuesto, esto es para el caso promedio. En el peor de los casos, no puedo encontrar una forma de generar series cuyo cuarto ciclo sea más alto que O (N ^ 2), y creo firmemente que no existen, pero no soy un matemático para probarlo.

Vieja respuesta

Aquí hay una solución en promedio de O ((n ^ 2) * cube_root (M)) donde M es la diferencia entre el primer y el último elemento de la matriz. Y los requisitos de memoria de O (M + N).

1.- Construye una matriz H de longitud M para que M [i - S [0]] = verdadero si existe en la matriz inicial y falso si no existe.

2.- Para cada par en la matriz S [j], S [i] do:

2.1 Verifique si puede ser el primer y tercer elemento de una posible solución. Para hacerlo, calcule todos los posibles pares A, K que cumplan con la ecuación S (i) = S (j) + AK + AK ^ 2. Consulte esta pregunta SO para ver cómo resolver este problema. Y compruebe que exista el segundo elemento: S [i] + A * K

2.2 Comprobar también que existe el elemento una posición más allá que la mejor solución que tenemos. Por ejemplo, si la mejor solución que tenemos hasta ahora es de 4 elementos, entonces verifique que exista el elemento A [j] + A K + A K ^ 2 + A K ^ 3 + A K ^ 4

2.3 Si 2.1 y 2.2 son verdaderas, entonces itere cuánto tiempo es esta serie y configurada como la mejor Solución hasta ahora es más larga que la última.

Aquí está el código 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));

Puede verificar el código aquí: http://jsfiddle.net/6yHyR/1/

Mantengo la otra solución porque creo que todavía es mejor cuando M es muy grande en comparación con N.