0votos

Mejor factorización triple en Haskell

por josejuan hace 5 años

Yo no encuentro ninguna propiedad que me permita resolver eficientemente el problema. Para mí hay que factorizar n (que tiene complejidad "casi" exponencial) y luego empaquetar una suma de enteros (que en general es NP-hard). Pueden usarse heurísticas, pero no veo ninguna invarianza o suavidad que pueda usarse para acercarse al objetivo. Aquí la solución trivial.

Calcular la factorización de n en un producto de tres números (a,b,c) tales que 1 ≤ a ≤ b ≤ c y c/a es mínima.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
import Data.Numbers.Primes 
import Data.List 
import System.Environment 
 
-- Dados los factores primos, obtiene la mejor partición según el criterio "minimizar c/a" 
bestri = head .                                                            -- El menor 
         sortBy (\(a, _, c) (a', _, c') -> compare (c * a') (a * c')) .    -- minimizando "c/a" 
         filter (\(a, b, c) -> 1 <= a && a <= b && b <= c) .               -- cumpliendo "1 <= a <= b <= c" 
         gentri                                                            -- de todas las particiones de divisores de N 
 
-- Reparte, de todas las formas posibles, N elementos en 3 grupos (el grupo A, el grupo B y el grupo C) 
div3 n = [(a, b, n - a - b) | a <- [0..n], b <- [0..n - a]] 
 
-- Genera todas las formas es que pueden dividirse los factores de N en tres grupos 
gentri [] = [(1, 1, 1)] 
gentri ((f, s):fs) = [(f^pa * a, f^pb * b, f^pc * c) | (pa, pb, pc) <- div3 s, (a, b, c) <- gentri fs] 
 
-- Obtiene la factorización devolviendo las potencias de cada primo 
potenciasPrimas = map (\ps -> (head ps, length ps)) . group . primeFactors 
 
-- bestri a partir de N 
bestri' = bestri . potenciasPrimas 
 
 
 
 
 
-- Para probar podría hacerse 
main = do 
  xs <- getArgs 
  if length xs == 1 
    then print $ bestri' $ read $ head xs 
    else print $ bestri $ readFactores xs 
 
readFactores [] = [] 
readFactores (x:y:xs) = (read x, read y):readFactores xs 
 
{- 
 
Por ejemplo: 
 
solveet]$ time -f "%E, %M" ./trifac 3042467131516312500000 
(14478750,14491750,14500200) 
0:21.74, 2723280 
 
 
-} 

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.