1votos

Bactracking básico continuación en Haskell

por josejuan hace 3 años

map (foldl1 (.|.)) $ combinaciones m $ map (2^) [0..n-1]

Dado los números n y m obtener de la manera mas eficiente posible un array de todas las combinaciones de un número binario de n dígitos en donde aparezcan m veces repetidas el 1.

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
import System.Environment 
import Data.Bits 
 
-- Con backtracking directo (ineficiente) 
combs n m = 
  if      m == 0 then t 0 
  else if m == n then t 1 
  else                r 0 ++ r 1 
 
  where t k = [take n [k,k..]] 
        r k = map (k:) $ combs (n - 1) (m - k) 
 
 
-- También podemos hacer un backtracking para sacar las posiciones 
combinaciones 0     _  = [[]] 
combinaciones _    []  = [] 
combinaciones n (x:xs) = [x:ys | ys <- combinaciones (n - 1) xs] ++ combinaciones n xs 
 
-- Entonces, obtener lo que se pide es sólo poner los bits a 1 (eficiente) 
combs' :: Int -> Int -> [Int] 
combs' n m = map (foldl1 (.|.)) $ combinaciones m $ map (2^) [0..n-1] 
 
 
-- Comparando rendimiento 
main = do 
  (t:n:m:_) <- getArgs 
  case t of 
          "1" -> print $ length $ combs   (read n) (read m) 
          "2" -> print $ length $ combs'  (read n) (read m) 
 
{- 
 
[josejuan@centella solveet]$ ghc -O3 -fforce-recomp nmbits.hs 
[1 of 1] Compiling Main             ( nmbits.hs, nmbits.o ) 
Linking nmbits ... 
 
[josejuan@centella solveet]$ for i in 1 2; do time -f "%E, %M" ./nmbits $i 27 12; done 
17383860 
0:16.23, 3576 
17383860 
0:08.19, 3572 
 
-} 

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.