1votos

Variante del problema de Ullman en JavaScript

por josejuan hace 6 años

Ok, si el conjunto de elementos que pueden sumar k es finito, he encontrado un algoritmo que lo resuelve en, como mucho, O(|xs| + k +1) y no depende de 'n' (el peor caso). Es decir, lineal. En la práctica, la restricción es que 'k' sea relativamente "pequeño" (eg. 2^32) lo cual excluye los números reales. Podría adaptarse a los reales usando intervalos, pero ya no sería lineal (sería cuasi-lineal; es decir, tiende a lineal según se aumente el número de intervalos).

Calcular los subconjuntos de un tamaño dado y con su suma acotada.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function UllmanUInt(xs, n, k) { 
    var K = [], S = 0, N = n; 
    for(var i = 0; i <= k; i++) K[i] = 0; // (k + 1) veces 
    for(var i = 0, L = xs.length; i < L; i++) if(xs[i] <= k) K[xs[i]]++; // |xs| veces 
    for(var i = 0; i <= k; i++) { // máx (k + 1) veces 
        if(N <= K[i]) {S += i * N; N = 0; break} 
        N -= K[i]; S += i * K[i]; 
    return (N == 0) && (S < k); 
 
/* 
    Recorremos linealmente cada 'x' de 'xs' contando el número de elementos entre 0 y k. 
    Después, apilamos hasta llegar a 'n' elementos o descartar con False. 
*/ 
2 comentarios
0votos

Escrito por nax hace 6 años

No se si estoy planteando algo descabelladísimo, pero entre a solveet para aprender más en cuanto a optimizar este tipo de estructuras así que ahí va.

Me estaba planteando si el ordenar xs antes de buscar los subconjuntos aceleraría el proceso o sería un paso innecesario.

La principal razón es el hacer un primer paso de eliminar todos los numeros mayores a k para evitar comprobaciones innecesarias.
0votos

Escrito por josejuan hace 6 años

Si ordenas el conjunto "tal cual" esa ordenación tiene un coste O(n log n) lo cual ya es mayor que el coste mencionado, luego no interesa.

Si la ordenación la haces por bipartición y lazy (vaya, Quick sort) el coste teórico tiende a lineal (pero no es lineal), por ejemplo

ullman xs n k = s < k where s = take n $ sort xs


Al ser lazy, sólo los conjuntos menores que va forzando "take" se irán ordenando.

De todos modos, aunque elegante y conciso, tiene una constante multiplicativa bastante alta y sigue siendo mayor que lineal, ya que en el peor caso hay que intercambiar n elementos en el primer caso, n/2 en el segundo, ... que sigue siendo O(n log n) pero mejorado (se aproxima mucho a una lineal).

Pero sí, en una situación práctica podría interesar la versión lazy de ordenación.

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.