Programación dinámica en el paradigma funcional

Question

Estoy viendo Problem thirty one en Project Euler, que pregunta, ¿cuántas formas diferentes hay para hacer £ 2 usando cualquier cantidad de monedas de 1p, 2p, 5p, 10p, 20p, 50p, £ 1 (100p) y £ 2 (200p).

hay soluciones recursivas, tales como éste en Scala (crédito a Pavel Fatin)

def f(ms: List[Int], n: Int): Int = ms match { 
    case h :: t => 
    if (h > n) 0 else if (n == h) 1 else f(ms, n - h) + f(t, n) 
    case _ => 0 
} 
val r = f(List(1, 2, 5, 10, 20, 50, 100, 200), 200) 

y aunque corre lo suficientemente rápido, es relativamente ineficaz, llamando a la función f alrededor de 5,6 millones de veces.

vi solución de otra persona en Java que fue programado dinámicamente (crédito a Wizeman de Portugal)

final static int TOTAL = 200; 

public static void main(String[] args) { 
    int[] coins = {1, 2, 5, 10, 20, 50, 100, 200}; 
    int[] ways = new int[TOTAL + 1]; 
    ways[0] = 1; 

    for (int coin : coins) { 
     for (int j = coin; j <= TOTAL; j++) { 
      ways[j] += ways[j - coin]; 
     } 
    } 

    System.out.println("Result: " + ways[TOTAL]); 
} 

Esto es mucho más eficiente y pasa el bucle interno sólo 1.220 veces.

Si bien obviamente pude traducir esto más o menos al pie de la letra en Scala usando objetos Array, ¿hay una forma idiomática funcional de hacer esto usando estructuras de datos inmutables, preferiblemente con concisión y rendimiento similares?

He intentado y me he quedado atrapado tratando de actualizar recursivamente un List antes de decidir que probablemente me estoy acercando al camino equivocado.

Answer 1

Cuando alguna parte de una lista de datos se calcula en base a un elemento anterior, pienso en la recursión Stream. Desafortunadamente, dicha recursión no puede ocurrir dentro de las definiciones o funciones del método, así que tuve que convertir una función en una clase para que funcione.

class IterationForCoin(stream: Stream[Int], coin: Int) { 
    val (lower, higher) = stream splitAt coin 
    val next: Stream[Int] = lower #::: (higher zip next map { case (a, b) => a + b }) 
} 
val coins = List(1, 2, 5, 10, 20, 50, 100, 200) 
val result = coins.foldLeft(1 #:: Stream.fill(200)(0)) { (stream, coin) => 
    new IterationForCoin(stream, coin).next 
} last 

Las definiciones de lower y higher no son necesarios - Yo podría reemplazarlos con stream take coin y stream drop coin, pero yo creo que es un poco más claro (y más eficiente) de esta manera.

Answer 2

No sé lo suficiente sobre Scala para comentar específicamente sobre eso, pero la forma típica de traducir una solución de DP a una recursiva es a la memorización (use http://en.wikipedia.org/wiki/Memoization). Esto es básicamente el almacenamiento en caché del resultado de su función para todos los valores del dominio

Encontré esto también como http://michid.wordpress.com/2009/02/23/function_mem/. HTH

Answer 3

Ok, aquí está la versión memorada del código de Pavel Fatin. Estoy usando material de memora Scalaz, aunque es muy simple escribir tu propia clase de memoialización.

import scalaz._ 
import Scalaz._ 

val memo = immutableHashMapMemo[(List[Int], Int), Int] 
def f(ms: List[Int], n: Int): Int = ms match { 
    case h :: t => 
    if (h > n) 0 else if (n == h) 1 else memo((f _).tupled)(ms, n - h) + memo((f _).tupled)(t, n) 
    case _ => 0 
} 
val r = f(List(1, 2, 5, 10, 20, 50, 100, 200), 200) 

Answer 4

programación dinámica funcional en realidad puede ser muy bonito en un lenguaje vago, como Haskell (hay an article on it en el wiki de Haskell). Esta es una solución de programación dinámica al problema:

import Data.Array 

makeChange :: [Int] -> Int -> Int 
makeChange coinsList target = arr ! (0,target) 
    where numCoins = length coinsList 
     coins = listArray (0,numCoins-1) coinsList 
     bounds = ((0,0),(numCoins,target)) 
     arr  = listArray bounds . map (uncurry go) $ range bounds 
     go i n | i == numCoins = 0 
       | otherwise  = let c = coins ! i 
            in case c `compare` n of 
             GT -> 0 
             EQ -> 1 
             LT -> (arr ! (i, n-c)) + (arr ! (i+1,n)) 

main :: IO() 
main = putStrLn $ "Project Euler Problem 31: " 
       ++ show (makeChange [1, 2, 5, 10, 20, 50, 100, 200] 200) 

Es cierto que esta utiliza O (cn) de memoria, donde c es el número de monedas y n es la diana (a diferencia de la La versión O de Java (n) memoria); para obtener eso, tendrías que usar alguna técnica para capturar el estado mutable (probablemente un STArray).Sin embargo, ambos se ejecutan en O (cn) vez. La idea es codificar la solución recursiva casi directamente de forma recursiva, pero en lugar de recurrir a vaya, buscamos la respuesta en la matriz. ¿Y cómo construimos la matriz? Al llamar al , vaya al en cada índice. Como Haskell es flojo, solo computa las cosas cuando se le pide, por lo que todo lo relacionado con el orden de evaluación necesario para la programación dinámica se maneja de forma transparente.

Y gracias a los parámetros de Scala por nombre y lazy val s, podemos imitar esta solución en Scala:

class Lazy[A](x: => A) { 
    lazy val value = x 
} 

object Lazy { 
    def apply[A](x: => A) = new Lazy(x) 
    implicit def fromLazy[A](z: Lazy[A]): A = z.value 
    implicit def toLazy[A](x: => A): Lazy[A] = Lazy(x) 
} 

import Lazy._ 

def makeChange(coins: Array[Int], target: Int): Int = { 
    val numCoins = coins.length 
    lazy val arr: Array[Array[Lazy[Int]]] 
    = Array.tabulate(numCoins+1,target+1) { (i,n) => 
     if (i == numCoins) { 
      0 
     } else { 
      val c = coins(i) 
      if (c > n) 
      0 
      else if (c == n) 
      1 
      else 
      arr(i)(n-c) + arr(i+1)(n) 
     } 
     } 
    arr(0)(target) 
} 

// makeChange(Array(1, 2, 5, 10, 20, 50, 100, 200), 200) 

La clase Lazy codifica valores que sólo se evalúan en la demanda, y luego construir un arsenal completo de ellos. Ambas soluciones funcionan para un valor objetivo de 10000 prácticamente al instante, aunque van mucho más grandes y se encontrará con un desbordamiento de enteros o (en Scala, al menos) un desbordamiento de la pila.

Answer 5

En aras de la exhaustividad, aquí es una ligera variante de la respuesta anterior que no utiliza Stream:

object coins { 
    val coins = List(1, 2, 5, 10, 20, 50, 100, 200) 
    val total = 200 
    val result = coins.foldLeft(1 :: List.fill(total)(0)) { (list, coin) => 
    new IterationForCoin(list, coin).next(total) 
    } last 
} 

class IterationForCoin(list: List[Int], coin: Int) { 
    val (lower, higher) = list splitAt coin 
    def next (total: Int): List[Int] = { 
    val listPart = if (total>coin) next(total-coin) else lower 
    lower ::: (higher zip listPart map { case (a, b) => a + b }) 
    } 
}