0votos

Obtener todas las sumas con números anteriores a uno dado en Haskell

por josejuan hace 4 años

Un bonito ejercicio.

Dado un número n y numero de sumandos = m, sacar todas las sumas con números enteros no negativos (es decir, los números naturales y el 0) anteriores a él que dan como resultado n pero sin repetir)

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
{- 
- Como las formas de sumar no deben repetirse (y queremos mostrar 
- los sumandos descendentemente aunque ésto da igual), vamos a 
- escribir una función que nos de *TODAS* las formas de sumar un 
- número `n` pero, cuyos sumandos no pueden ser mayores que cierto 
- número `c`. 
- Así, si pedimos 
-       sumaHastaConNoMasDe 5 1 
- sólo puede devolver 
-       1 + 1 + 1 + 1 + 1 
- porque los sumandos no pueden superar 1. 
- Por tanto, si tenemos cierto `n` y cierto `c` el siguiente sumando 
- posible deberá ser menor que `c`, es decir, si el próximo sumando 
- es `i`, tenemos que 
-       i € [1..c] 
- pero como queremos los sumandos descendentemente 
-       i € [c..1] 
- por ejemplo, si n=5 y c=3 
-     para i=3 
-       3 + ? 
-     para i=2 
-       2 + ? 
-     para i=1 
-       1 + ? 
- ese interrogante deberá sumar n-i, porque es lo que queda 
- hasta llegar a n, es decir, el "?" que falta son las formas 
- de sumar n-i pero sin usar números mayores que i (y tales 
- que no superen n). 
- Es decir, desarrollando el "?" anterior tenemos 
-       3 + | 2 
-           | 1 + | 1 
-       2 + | 2 + | 1 
-           | 1 + | 1 + | 1 
- Donde las barras "|" indican que la suma de 3 es con dos alternativas 
- la del (+ 2) y la del (+ 1 + 1). 
-} 
sumaHastaConNoMasDe :: Int -> Int -> [[Int]] 
sumaHastaConNoMasDe 0 _ = [[]] 
sumaHastaConNoMasDe n c = concat [ map (i:) (sumaHastaConNoMasDe d i) 
                                 | i <- [c, c-1 ..1] 
                                 , let d = n - i 
                                 , d >= 0 ] 
 
-- NOTA: la función `sumaHastaConNoMasDe` puede ser memoizada porque se 
--       repetirán muchas formas de sumar. 
 
-- Como la función anterior nos da *TODAS* las formas de sumar, nos quedamos 
-- con ellas pero sólo mientras no tengan más de `m` sumandos. 
sumas :: Int -> Int -> [[Int]] 
sumas n m = takeWhile ((<=m).length) $ sumaHastaConNoMasDe n n 
 
 
 
-- Por ejemplo: 
main = mapM_ print $ sumas 5 4 
 
{- 
- [5] 
- [4,1] 
- [3,2] 
- [3,1,1] 
- [2,2,1] 
- [2,1,1,1] 
-} 

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.