0votos
Concatenación de números en Haskell
por

josejuan

hace 1 año

Bonito problema. Quizás exista una solución óptima analizando las palabras de entrada hasta aquella de máxima longitud (obteniendo O(n) o más probable O(n log n), ...). A lo bruto (pero eficiente) basta establecer el orden (que NO ES el habitual) y concatenar usando un heap de prioridad hasta encontrar uno.

0votos
Spotify, tráfico de influencias en Haskell
por

josejuan

hace 2 años

Hace dos años comenté que el problema es NP-completo, estaba equivocado, pues en el caso de grafos bipartitos (como ocurre aquí) usando el teorema de König existe un algoritmo polinomial fácil de implementar (siguiendo la demostración de http://en.wikipedia.org/wiki/K%C3%B6nig%27s_theorem_%28graph_theory%29 )