Sistemas de ternas de Steiner en Haskell

Un sistema de Steiner de ternas de orden $n$ , $S(n)$ , es un conjunto de ternas tal que los elementos de cada terna son números del $1$ al $n$ y cualquier par de elementos $\{i,j\}$ (con $\text{[math]}$ 1 \leq i < j \leq n[/latex]) pertenece exactamente a una terna. Por ejemplo, [latex]S(3) = \{\{1,2,3\}\}[/latex] [latex]S(7) = \{\{1,2,4\}, \{2,3,5\}, \{3,4,6\}, \{4,5,7\}, \{5,6,1\}, \{6,7,2\}, \{7,1,3\}\}[/latex] Se verifica que [latex]S(n)[/latex] es no vacío si, y sólo si, si [latex]n[/latex] es congruente con 1 o con 3 módulo 6. En ese caso, el número de elementos de [latex]S(n)[/latex] es [latex]\frac{n(n-1)}{6}[/latex]. En la Wikipedia se encuentra más información sobre los sistemas de Steiner.

El objetivo de esta relación es definir en Haskell una función para calcular los sistemas de ternas de Steiner de orden n.

-- ---------------------------------------------------------------------
-- § Librerías auxiliares                                             --
-- ---------------------------------------------------------------------

import Data.List

-- ---------------------------------------------------------------------
-- § Reconocimiento de sistemas de Steiner                            --
-- ---------------------------------------------------------------------

-- ---------------------------------------------------------------------
-- Ejercicio 1. Definir los tipos sinónimos Par y Terna para representar
-- los pares y laa ternas de números enteros. 
-- ---------------------------------------------------------------------

type Par   = (Int,Int)
type Terna = (Int,Int,Int)

-- ---------------------------------------------------------------------
-- Nota. En lo que sigue, cuando se usen pares y ternas, se supondrá que
-- sus elementos están ordenados de forma estrictamente creciente.
-- ---------------------------------------------------------------------

-- ---------------------------------------------------------------------
-- Ejercicio 2. Definir la función
--    pares:: Int -> [Par]
-- tal que (pares n) es la lista de los subconjuntos de 2 elementos
-- de {1,2,...,n}. Por ejemplo,
--    pares 4  ==  [(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)]
-- ---------------------------------------------------------------------

pares:: Int -> [Par]
pares n = [(x,y) | x <- [1..n], y <- [x+1..n]]

-- ---------------------------------------------------------------------
-- Ejercicio 3. Definir la función
--    contenido :: Par -> Terna -> Bool
-- tal que (contenido (p1,p2) (t1,t2,t3)) se verifica si {p1,p2} está
-- contenido en {t1,t2,t3}, suponiendo que p1 < p2 y t1 < t2 < t3. Por
-- ejemplo,
--    contenido (1,3) (1,3,5)  ==  True
--    contenido (1,3) (1,2,3)  ==  True
--    contenido (1,3) (1,2,4)  ==  False
--    contenido (2,3) (1,2,3)  ==  True
--    contenido (2,3) (1,2,4)  ==  False
--    contenido (3,4) (1,2,3)  ==  False
-- ---------------------------------------------------------------------

contenido :: Par -> Terna -> Bool
contenido (p1,p2) (t1,t2,t3)
    | p1 == t1  = p2 == t2 || p2 == t3
    | p1 == t2  = p2 == t3
    | otherwise = False

-- ---------------------------------------------------------------------
-- Ejercicio 4. Definir la función
--    parOcurreUnaVez :: Par -> [Terna] -> Bool
-- tal que (parOcurreUnaVez p ts) se verifica si el par p está contenido 
-- exactamente en una de las ternas de ts. Por ejemplo,
--    parOcurreUnaVez (1,3) [(1,2,4),(1,2,3)]  ==  True
--    parOcurreUnaVez (1,3) [(1,2,4),(1,2,5)]  ==  False
--    parOcurreUnaVez (1,3) [(1,3,4),(1,2,3)]  ==  False
-- ---------------------------------------------------------------------

parOcurreUnaVez :: Par -> [Terna] -> Bool
parOcurreUnaVez p ts = length [1 | t <- ts, contenido p t] == 1

-- ---------------------------------------------------------------------
-- Ejercicio 5. Definir la función
--    enRango :: Terna -> Int -> Bool
-- tal que (enRango t n) se verifica si los elementos de la ternas t
-- están entre 1 y n. Por ejemplo,
--    enRango (1,3,6) 7  ==  True
--    enRango (1,3,6) 5  ==  False
-- ---------------------------------------------------------------------

enRango :: Terna -> Int -> Bool
enRango (t1,t2,t3) n = and [x `elem` [1..n] | x <- [t1,t2,t3]]

-- ---------------------------------------------------------------------
-- Ejercicio 6. Definir la función
--    esSistemaSteiner :: [Terna] -> Int -> Bool
-- tal que (esSistemaSteiner ts 7) se verifica si ts es un sistema de
-- Steiner de orden n; es decir, ts es un conjunto de ternas en el rango
-- n y para cualquier par de elementos {i,j} (con 1 <= i < j <= n)
-- pertenece exactamente a una terna de ts. Por ejemplo,
-- esSistemaSteiner [(3,5,6),(3,4,7),(2,5,7),(2,4,6),(1,6,7),(1,4,5),(1,2,3)] 7
-- == True
-- ---------------------------------------------------------------------

esSistemaSteiner :: [Terna] -> Int -> Bool
esSistemaSteiner ts n = 
    and [enRango t n | t <- ts] &&
    and [parOcurreUnaVez p ts | p <- ps]
    where ps = pares n

-- ---------------------------------------------------------------------
-- § Cálculo de sistemas de Steiner                                   --
-- ---------------------------------------------------------------------

-- ---------------------------------------------------------------------
-- El cálculo de los sistemas de Steiner de orden n se basa en completar
-- soluciones parciales. La soluciones parciales son pares de la forma
-- (ps,ts) donde ps representa la lista de pares no cubiertos por las
-- ternas de ts. Inicialmente, la solución parcial es (pares n, []). En
-- cada paso, se completa la solución parcial (ps,ts) eligiendo el
-- primer par (x,y) de ps y buscando los elementos z entre y+1 y n tales
-- que (x,z) e (y,z) pertenecen a ps; las nuevas soluciones parciales
-- son (ps',ts'), donde ps' se obtiene quitando a ps los pares (x,y), (x,z) e 
-- (y,z) y ts' se obtiene añadiendo a ts la terna (x,y,z).
-- ---------------------------------------------------------------------

-- ---------------------------------------------------------------------
-- Ejercicio 7. Definir el sinónimo de tipo SolPar como un par formado
-- por una lista de pares y una lista de ternas.
-- ---------------------------------------------------------------------
    
type SolPar = ([Par],[Terna])

-- ---------------------------------------------------------------------
-- Ejercicio 8. Definir la función
--    completableCon :: Par -> Int -> [Par] -> Bool 
-- tal que (completableCon (x,y) z ps) se verifica si el par (x,y) es
-- completable con z respecto de ps; es decir, si (x,z) e (y,z) están en
-- la lista de pares ps. Por ejemplo, 
--    completableCon (1,3) 5 [(1,5),(2,6),(3,5)]  ==  True
--    completableCon (1,3) 5 [(1,5),(2,6),(3,7)]  ==  False
-- ---------------------------------------------------------------------

completableCon :: Par -> Int -> [Par] -> Bool 
completableCon (x,y) z ps = elem (x,z) ps && elem (y,z) ps

-- ---------------------------------------------------------------------
-- Ejercicio 9. Definir la función
--    completacion :: Par -> Int -> SolPar -> SolPar
-- tal que (completacion (x,y) z (ps,ts)) es el par (ps',ts') donde ps'
-- es la lista de pares obtenida eliminando en ps los pares (x,z) e
-- (y,z) y ts'es la lista de ternas obtenida añadiéndole a ts la terna
-- (x,y,z). Por ejemplo,
--    ghci> completacion (1,3) 4 ([(1,2),(1,4),(2,3),(3,4)],[(2,5,7)])
--    ([(1,2),(2,3)],[(1,3,4),(2,5,7)])
-- ---------------------------------------------------------------------

completacion :: Par -> Int -> SolPar -> SolPar
completacion (x,y) z (ps,ts) =
    (ps \\ [(x,z),(y,z)], (x,y,z):ts)

-- ---------------------------------------------------------------------
-- Ejercicio 10. Definir la función
--    completaciones :: SolPar -> Int -> [SolPar] 
-- tal que (completaciones (ps,ts) n) es la lista de las completaciones
-- del primer elemento de ps con los elementos de {y+1, y+2, ..., n}
-- respecto de (ps,ts). Por ejemplo, 
--    ghci> (pares 5, [])
--    ([(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],[])
--    ghci> completaciones it 5
--    [([(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],[(1,2,3)]),
--     ([(1,3),(1,5),(2,3),(2,5),(3,4),(3,5),(4,5)],[(1,2,4)]),
--     ([(1,3),(1,4),(2,3),(2,4),(3,4),(3,5),(4,5)],[(1,2,5)])]
--    ghci> completaciones (head it) 5
--    [([(2,4),(2,5),(3,4),(3,5)],[(1,4,5),(1,2,3)])]
--    ghci> completaciones (head it) 5
--    []
-- ---------------------------------------------------------------------

completaciones :: SolPar -> Int -> [SolPar] 
completaciones ((x,y):ps,ts) n =
    [completacion (x,y) z (ps,ts) | 
     z <- [y+1..n],
     completableCon (x,y) z ps]

-- ---------------------------------------------------------------------
-- Ejercicio 11. Definir la función
--    sistemasSteiner :: Int -> [[Terna]]
-- tal que (sistemasSteiner n) es el conjunto de los sistemas de Steiner
-- de ternas de orden n. Por ejemplo,
--    ghci> sistemasSteiner 3
--    [[(1,2,3)]]
--    ghci> sistemasSteiner 4
--    []
--    ghci> take 2 (sistemasSteiner 7)
--    [[(5,6,7),(3,4,7),(2,4,6),(2,3,5),(1,4,5),(1,3,6),(1,2,7)],
--     [(4,6,7),(3,5,7),(2,5,6),(2,3,4),(1,4,5),(1,3,6),(1,2,7)]]
-- --------------------------------------------------------------------- 

sistemasSteiner :: Int -> [[Terna]]
sistemasSteiner n = aux n [(pares n, [])] []
    where
      aux n [] tss              = tss
      aux n (([],ts):lss) tss   = aux n lss (ts:tss)
      aux n ((p:ps,ts):lss) tss =
          aux n (completaciones (p:ps,ts) n ++ lss) tss

-- ---------------------------------------------------------------------
-- Ejercicio 12. Definir la función
--    prop_correccion_Steiner :: Int -> Bool
-- tal que (prop_correccion_Steiner n) se verifica si (sistemasSteiner n)
-- es un sistema de Steiner de orden n. Comprobar la propiedad para n=7.
-- ---------------------------------------------------------------------

prop_correccion_Steiner :: Int -> Bool
prop_correccion_Steiner n =
    and [esSistemaSteiner ts n | ts <- sistemasSteiner n']
    where n' = abs n

-- La comprobación es
--    ghci> prop_correccion_Steiner 7
--    True

-- ---------------------------------------------------------------------
-- Ejercicio 13. Definir la función
--    steiner :: Int -> [Terna]
-- tal que (steiner n) es un sistema de Steiner de ternas de orden
-- n, usando el ejercicio anterior. Por ejemplo, 
--    ghci> steiner 7
--    [(5,6,7),(3,4,7),(2,4,6),(2,3,5),(1,4,5),(1,3,6),(1,2,7)]
-- ---------------------------------------------------------------------

steiner :: Int -> [Terna]
steiner = head . sistemasSteiner

-- ---------------------------------------------------------------------
-- Ejercicio 14. Definir la función
--    steiner' :: Int -> [Terna]
-- tal que (steiner' n) es un sistema de Steiner de ternas de orden
-- n, que sea más eficiente que la del ejercicio anterior. Por ejemplo,
--    ghci> steiner' 7
--    [(3,5,6),(3,4,7),(2,5,7),(2,4,6),(1,6,7),(1,4,5),(1,2,3)]
-- ---------------------------------------------------------------------

steiner' :: Int -> [Terna]
steiner' n = head (aux n [(pares n, [])] [])
    where
      aux n [] tss              = tss
      aux n (([],ts):lss) tss   = [ts]
      aux n ((p:ps,ts):lss) tss =
          aux n (completaciones (p:ps,ts) n ++ lss) tss

-- ---------------------------------------------------------------------
-- Ejercicio 15. Comparar la eficiencia de steiner y steiner' comparando
-- los tiempos empleados en calcular (steiner 9) y (steiner' 9).
-- ---------------------------------------------------------------------

-- La comparación es
--    ghci> steiner 9
--    ...
--    (0.28 secs, 13379652 bytes)
--    ghci> steiner' 9
--    ... 
--    (0.01 secs, 0 bytes)

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

-- ---------------------------------------------------------------------

-- § Librerías auxiliares --

-- ---------------------------------------------------------------------

import Data.List

-- ---------------------------------------------------------------------

-- § Reconocimiento de sistemas de Steiner --

-- ---------------------------------------------------------------------

-- Ejercicio 1. Definir los tipos sinónimos Par y Terna para representar

-- los pares y laa ternas de números enteros.

-- ---------------------------------------------------------------------

type Par = (Int,Int)

type Terna = (Int,Int,Int)

-- ---------------------------------------------------------------------

-- Nota. En lo que sigue, cuando se usen pares y ternas, se supondrá que

-- sus elementos están ordenados de forma estrictamente creciente.

-- ---------------------------------------------------------------------

-- Ejercicio 2. Definir la función

-- pares:: Int -> [Par]

-- tal que (pares n) es la lista de los subconjuntos de 2 elementos

-- de {1,2,...,n}. Por ejemplo,

-- pares 4 == [(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)]

-- ---------------------------------------------------------------------

pares:: Int -> [Par]

pares n = [(x,y) | x <- [1..n], y <- [x+1..n]]

-- ---------------------------------------------------------------------

-- Ejercicio 3. Definir la función

-- contenido :: Par -> Terna -> Bool

-- tal que (contenido (p1,p2) (t1,t2,t3)) se verifica si {p1,p2} está

-- contenido en {t1,t2,t3}, suponiendo que p1 < p2 y t1 < t2 < t3. Por

-- ejemplo,

-- contenido (1,3) (1,3,5) == True

-- contenido (1,3) (1,2,3) == True

-- contenido (1,3) (1,2,4) == False

-- contenido (2,3) (1,2,3) == True

-- contenido (2,3) (1,2,4) == False

-- contenido (3,4) (1,2,3) == False

-- ---------------------------------------------------------------------

contenido :: Par -> Terna -> Bool

contenido (p1,p2) (t1,t2,t3)

| p1 == t1 = p2 == t2 || p2 == t3

| p1 == t2 = p2 == t3

| otherwise = False

-- ---------------------------------------------------------------------

-- Ejercicio 4. Definir la función

-- parOcurreUnaVez :: Par -> [Terna] -> Bool

-- tal que (parOcurreUnaVez p ts) se verifica si el par p está contenido

-- exactamente en una de las ternas de ts. Por ejemplo,

-- parOcurreUnaVez (1,3) [(1,2,4),(1,2,3)] == True

-- parOcurreUnaVez (1,3) [(1,2,4),(1,2,5)] == False

-- parOcurreUnaVez (1,3) [(1,3,4),(1,2,3)] == False

-- ---------------------------------------------------------------------

parOcurreUnaVez :: Par -> [Terna] -> Bool

parOcurreUnaVez p ts = length [1 | t <- ts, contenido p t] == 1

-- ---------------------------------------------------------------------

-- Ejercicio 5. Definir la función

-- enRango :: Terna -> Int -> Bool

-- tal que (enRango t n) se verifica si los elementos de la ternas t

-- están entre 1 y n. Por ejemplo,

-- enRango (1,3,6) 7 == True

-- enRango (1,3,6) 5 == False

-- ---------------------------------------------------------------------

enRango :: Terna -> Int -> Bool

enRango (t1,t2,t3) n = and [x `elem` [1..n] | x <- [t1,t2,t3]]

-- ---------------------------------------------------------------------

-- Ejercicio 6. Definir la función

-- esSistemaSteiner :: [Terna] -> Int -> Bool

-- tal que (esSistemaSteiner ts 7) se verifica si ts es un sistema de

-- Steiner de orden n; es decir, ts es un conjunto de ternas en el rango

-- n y para cualquier par de elementos {i,j} (con 1 <= i < j <= n)

-- pertenece exactamente a una terna de ts. Por ejemplo,

-- esSistemaSteiner [(3,5,6),(3,4,7),(2,5,7),(2,4,6),(1,6,7),(1,4,5),(1,2,3)] 7

-- == True

-- ---------------------------------------------------------------------

esSistemaSteiner :: [Terna] -> Int -> Bool

esSistemaSteiner ts n =

and [enRango t n | t <- ts] &&

and [parOcurreUnaVez p ts | p <- ps]

where ps = pares n

-- ---------------------------------------------------------------------

-- § Cálculo de sistemas de Steiner --

-- ---------------------------------------------------------------------

-- El cálculo de los sistemas de Steiner de orden n se basa en completar

-- soluciones parciales. La soluciones parciales son pares de la forma

-- (ps,ts) donde ps representa la lista de pares no cubiertos por las

-- ternas de ts. Inicialmente, la solución parcial es (pares n, []). En

-- cada paso, se completa la solución parcial (ps,ts) eligiendo el

-- primer par (x,y) de ps y buscando los elementos z entre y+1 y n tales

-- que (x,z) e (y,z) pertenecen a ps; las nuevas soluciones parciales

-- son (ps',ts'), donde ps' se obtiene quitando a ps los pares (x,y), (x,z) e

-- (y,z) y ts' se obtiene añadiendo a ts la terna (x,y,z).

-- ---------------------------------------------------------------------

-- Ejercicio 7. Definir el sinónimo de tipo SolPar como un par formado

-- por una lista de pares y una lista de ternas.

-- ---------------------------------------------------------------------

type SolPar = ([Par],[Terna])

-- ---------------------------------------------------------------------

-- Ejercicio 8. Definir la función

-- completableCon :: Par -> Int -> [Par] -> Bool

-- tal que (completableCon (x,y) z ps) se verifica si el par (x,y) es

-- completable con z respecto de ps; es decir, si (x,z) e (y,z) están en

-- la lista de pares ps. Por ejemplo,

-- completableCon (1,3) 5 [(1,5),(2,6),(3,5)] == True

-- completableCon (1,3) 5 [(1,5),(2,6),(3,7)] == False

-- ---------------------------------------------------------------------

completableCon :: Par -> Int -> [Par] -> Bool

completableCon (x,y) z ps = elem (x,z) ps && elem (y,z) ps

-- ---------------------------------------------------------------------

-- Ejercicio 9. Definir la función

-- completacion :: Par -> Int -> SolPar -> SolPar

-- tal que (completacion (x,y) z (ps,ts)) es el par (ps',ts') donde ps'

-- es la lista de pares obtenida eliminando en ps los pares (x,z) e

-- (y,z) y ts'es la lista de ternas obtenida añadiéndole a ts la terna

-- (x,y,z). Por ejemplo,

-- ghci> completacion (1,3) 4 ([(1,2),(1,4),(2,3),(3,4)],[(2,5,7)])

-- ([(1,2),(2,3)],[(1,3,4),(2,5,7)])

-- ---------------------------------------------------------------------

completacion :: Par -> Int -> SolPar -> SolPar

completacion (x,y) z (ps,ts) =

(ps \\ [(x,z),(y,z)], (x,y,z):ts)

-- ---------------------------------------------------------------------

-- Ejercicio 10. Definir la función

-- completaciones :: SolPar -> Int -> [SolPar]

-- tal que (completaciones (ps,ts) n) es la lista de las completaciones

-- del primer elemento de ps con los elementos de {y+1, y+2, ..., n}

-- respecto de (ps,ts). Por ejemplo,

-- ghci> (pares 5, [])

-- ([(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],[])

-- ghci> completaciones it 5

-- [([(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],[(1,2,3)]),

-- ([(1,3),(1,5),(2,3),(2,5),(3,4),(3,5),(4,5)],[(1,2,4)]),

-- ([(1,3),(1,4),(2,3),(2,4),(3,4),(3,5),(4,5)],[(1,2,5)])]

-- ghci> completaciones (head it) 5

-- [([(2,4),(2,5),(3,4),(3,5)],[(1,4,5),(1,2,3)])]

-- ghci> completaciones (head it) 5

-- []

-- ---------------------------------------------------------------------

completaciones :: SolPar -> Int -> [SolPar]

completaciones ((x,y):ps,ts) n =

[completacion (x,y) z (ps,ts) |

z <- [y+1..n],

completableCon (x,y) z ps]

-- ---------------------------------------------------------------------

-- Ejercicio 11. Definir la función

-- sistemasSteiner :: Int -> [[Terna]]

-- tal que (sistemasSteiner n) es el conjunto de los sistemas de Steiner

-- de ternas de orden n. Por ejemplo,

-- ghci> sistemasSteiner 3

-- [[(1,2,3)]]

-- ghci> sistemasSteiner 4

-- []

-- ghci> take 2 (sistemasSteiner 7)

-- [[(5,6,7),(3,4,7),(2,4,6),(2,3,5),(1,4,5),(1,3,6),(1,2,7)],

-- [(4,6,7),(3,5,7),(2,5,6),(2,3,4),(1,4,5),(1,3,6),(1,2,7)]]

-- ---------------------------------------------------------------------

sistemasSteiner :: Int -> [[Terna]]

sistemasSteiner n = aux n [(pares n, [])] []

where

aux n [] tss = tss

aux n (([],ts):lss) tss = aux n lss (ts:tss)

aux n ((p:ps,ts):lss) tss =

aux n (completaciones (p:ps,ts) n ++ lss) tss

-- ---------------------------------------------------------------------

-- Ejercicio 12. Definir la función

-- prop_correccion_Steiner :: Int -> Bool

-- tal que (prop_correccion_Steiner n) se verifica si (sistemasSteiner n)

-- es un sistema de Steiner de orden n. Comprobar la propiedad para n=7.

-- ---------------------------------------------------------------------

prop_correccion_Steiner :: Int -> Bool

prop_correccion_Steiner n =

and [esSistemaSteiner ts n | ts <- sistemasSteiner n']

where n' = abs n

-- La comprobación es

-- ghci> prop_correccion_Steiner 7

-- True

-- ---------------------------------------------------------------------

-- Ejercicio 13. Definir la función

-- steiner :: Int -> [Terna]

-- tal que (steiner n) es un sistema de Steiner de ternas de orden

-- n, usando el ejercicio anterior. Por ejemplo,

-- ghci> steiner 7

-- [(5,6,7),(3,4,7),(2,4,6),(2,3,5),(1,4,5),(1,3,6),(1,2,7)]

-- ---------------------------------------------------------------------

steiner :: Int -> [Terna]

steiner = head . sistemasSteiner

-- ---------------------------------------------------------------------

-- Ejercicio 14. Definir la función

-- steiner' :: Int -> [Terna]

-- tal que (steiner' n) es un sistema de Steiner de ternas de orden

-- n, que sea más eficiente que la del ejercicio anterior. Por ejemplo,

-- ghci> steiner' 7

-- [(3,5,6),(3,4,7),(2,5,7),(2,4,6),(1,6,7),(1,4,5),(1,2,3)]

-- ---------------------------------------------------------------------

steiner' :: Int -> [Terna]

steiner' n = head (aux n [(pares n, [])] [])

where

aux n [] tss = tss

aux n (([],ts):lss) tss = [ts]

aux n ((p:ps,ts):lss) tss =

aux n (completaciones (p:ps,ts) n ++ lss) tss

-- ---------------------------------------------------------------------

-- Ejercicio 15. Comparar la eficiencia de steiner y steiner' comparando

-- los tiempos empleados en calcular (steiner 9) y (steiner' 9).

-- ---------------------------------------------------------------------

-- La comparación es

-- ghci> steiner 9

-- ...

-- (0.28 secs, 13379652 bytes)

-- ghci> steiner' 9

-- ...

-- (0.01 secs, 0 bytes)

Se puede imprimir o compartir con