0votos
Minimal Superpermutations en Haskell
por

josejuan

hace 4 años

El algoritmo trivial (concatenar permutaciones hasta terminar) puede hacerse en tiempo casi lineal O(p), lo que pasa que como el número de permutaciones es p=n! resulta que el coste práctico respecto el nº de símbolos es O(n!), aún así puede mejorarse mucho este algoritmo. La pena es que no sirve (ver A007489).

0votos
Escalera en Haskell
por

josejuan

hace 4 años

Se refuerza mi hipótesis de que existe una expresión única para el cálculo del problema. En esta solución doy una expresión O(1) para n <= 2k+1 y queda indicada que existe una expresión para n <= qk+1 para cualquier q. Por tanto, puede calcularse la expresión con coste constante (realmente el coste no es constante debido al coste de las operaciones con precisión arbitraria que no son constantes).

1voto
Escalera en Haskell
por

josejuan

hace 4 años

Pensando un rato en el problema, veo una estrategia de partición que hace al algoritmo con coste lineal O(N), por lo que calcula en milésimas lo que antes calculaba en minutos. Además, me da que podría calcularse más rápidamente, cuando no con coste O(1). Calcula N=100.000 y k=1.000 en menos de 7 segundos (a la versión de C le lleva 3 minutos).

0votos
Escalera en Haskell
por

josejuan

hace 4 años

Como N es menor de 10.000, entonces, está claro que al restar cualquier valor (válido) a N, vamos a tener un elemento de entre 10.000 y sólo de entre esos 10.000. Así, es obvio que memoizando una función de recurrencia tendremos una eficiencia muy buena (máximo habrá que calcular N * k veces esa función). Ésto no quita, que buscando alguna propiedad pueda mejorarse...

0votos
Listas palíndromas en Haskell
por

ebrasca

hace 4 años

Dedicado a jose juan , mi primer modulo en haskell que consigo que me funcione en mi eclipse XD.El único inconveniente que le veo es que no consigui hacer andar el remarcado de las palabras clave con colores.

0votos
Subsecuencias monotonicas crecientes en C en Haskell
por

josejuan

hace 4 años

No me gusta que se exija sin razón un lenguaje concreto. Se puede resolver fácilmente usando LPI, con sólo exigir que para dos índices i<j debe ser Ai<Aj (u otra según monotonía). Mi función permite obtener la subsecuencia más larga de cualquier tipo de monotonía (creciente, nocreciente, decreciente y nodecreciente).