如何以1,1,4,5,1,4固定顺序，不论计算方式组合，排列出0-99的所有数字？ https://www.zhihu.com/question/269086028

gen-arith-expr-puzzle.hs

import Data.List
import GHC.Exts

type Number = Int

data Op = Add | Sub | Mul | Div | Pow deriving (Show, Eq, Ord, Enum, Bounded)
data AST = BinOp Op AST AST | Lit [Number] deriving (Eq, Ord)

instance Show AST where
    show (BinOp op x y) = "(" ++ show x ++ pure ("+-*/^" !! fromEnum op) ++ show y ++ ")"
    show (Lit xs) = concatMap show xs

eval :: AST -> [(Number, AST)]
eval ast@(BinOp Add ex ey) = [(x + y, ast) | (x, _) <- eval ex, (y, _) <- eval ey]
eval ast@(BinOp Sub ex ey) = [(x - y, ast) | (x, _) <- eval ex, (y, _) <- eval ey]
eval ast@(BinOp Mul ex ey) = [(x * y, ast) | (x, _) <- eval ex, (y, _) <- eval ey]
eval ast@(BinOp Div ex ey) = [(x `div` y, ast) | (x, _) <- eval ex, (y, _) <- eval ey , y /= 0]
eval ast@(BinOp Pow ex ey) = [(x ^ y, ast) | (x, _) <- eval ex, (y, _) <- eval ey , y >= 0]
eval ast@(Lit xs) = [(read (concatMap show xs), ast)]

numbers ops (x:xs) = e (x:xs) ++ e (-x:xs) where
    e [x] = eval (Lit [x])
    e xs = eval (Lit xs) ++ concat [eval (BinOp op x y) | op <- ops, k <- [1 .. length xs - 1], (_, x) <- e (take k xs), (_, y) <- e (drop k xs)]

solve xs ops = map head . groupWith fst . sort . filter (\(x, t) -> x >= 0 && x < 100) $ numbers ops xs

solution = length solutions
solutions = (solve [1, 1, 4, 5, 1, 4] [Add, Sub, Mul])
printSolutions = mapM_ print solutions

--powerset :: [a] -> [[a]]
--powerset [] = [[]]
--powerset (x: xs) = let pxs = powerset xs in pxs ++ map (x:) pxs

--enumOps = [(ops, length (solve [1, 1, 4, 5, 1, 4] ops)) | ops <- powerset [minBound .. maxBound]]
--validOps = filter ((==100) . snd) enumOps

{-

GHCi> printSolutions
(0,(((1+(1-4))+5)+(1-4)))
(1,(((-11+4)+(5-1))+4))
(2,((((-1-1)+(4-5))+1)+4))
(3,((((-11+4)+5)+1)+4))
(4,((((-1+1)+(4-5))+1)+4))
(5,(((((-1*1)-4)+5)+1)+4))
(6,((((-1+(1-4))+5)+1)+4))
(7,(((((1*1)-4)+5)+1)+4))
(8,((((1+(1-4))+5)+1)+4))
(9,(((11-4)+5)+(1-4)))
(10,((((-1-1)+4)+(5-1))+4))
(11,((((-1-1)+4)+(5*1))+4))
(12,(((((-1-1)+4)+5)+1)+4))
(13,(((((-1*1)+4)+5)+1)+4))
(14,(((((-1+1)+4)+5)+1)+4))
(15,(((((1*1)+4)+5)+1)+4))
(16,(((((1+1)+4)+5)+1)+4))
(17,((((11-4)+5)+1)+4))
(18,(((((1+1)*4)+5)+1)+4))
(19,(((1+1)+(4*5))+(1-4)))
(20,(((-1+1)+(4*(5-1)))+4))
(21,((((-1-1)+4)+5)+14))
(22,((((-1*1)+4)+5)+14))
(23,((((-1+1)+4)+5)+14))
(24,((((-1*1)+(4*5))+1)+4))
(25,((((-1+1)+(4*5))+1)+4))
(26,((((1*1)+(4*5))+1)+4))
(27,((((1+1)+(4*5))+1)+4))
(28,(((-1+1)+(4*(5+1)))+4))
(29,(((-1+((1+4)*5))+1)+4))
(30,(((1+1)+(4*(5+1)))+4))
(31,(((1+((1+4)*5))+1)+4))
(32,(((-1+14)+5)+14))
(33,(((-1*1)+(4*5))+14))
(34,(((-1+1)+(4*5))+14))
(35,(((((1+1)+4)*5)+1)+4))
(36,(((1+1)+(4*5))+14))
(37,((-1+14)+((5+1)*4)))
(38,((-1+((1+4)*5))+14))
(39,(((-11+45)+1)+4))
(40,(((-1-1)+45)+(1-4)))
(41,(((-1*1)+45)+(1-4)))
(42,(((-1+1)+45)+(1-4)))
(43,(((1*1)+45)+(1-4)))
(44,(((1+1)+45)+(1-4)))
(45,((((1+1)*(4*5))+1)+4))
(46,(((-1-1)+(45-1))+4))
(47,(((-1-1)+(45*1))+4))
(48,((((-1-1)+45)+1)+4))
(49,((((-1*1)+45)+1)+4))
(50,((((-1+1)+45)+1)+4))
(51,((((1*1)+45)+1)+4))
(52,((((1+1)+45)+1)+4))
(53,(((1+(1-4))+51)+4))
(54,((((11*4)+5)+1)+4))
(55,((((-1+1)*4)+51)+4))
(56,(((-1+14)*(5-1))+4))
(57,((((-1-1)+4)+51)+4))
(58,((((-1*1)+4)+51)+4))
(59,((((-1+1)+4)+51)+4))
(60,((((1*1)+4)+51)+4))
(61,((((1+1)+4)+51)+4))
(62,(((11-4)+51)+4))
(63,((((1+1)*4)+51)+4))
(64,((-1+1)+((4*(5-1))*4)))
(65,(((-1*1)-4)+(5*14)))
(66,((-1+(1-4))+(5*14)))
(67,(((1*1)-4)+(5*14)))
(68,(((-1+14)+51)+4))
(69,(((1*14)+51)+4))
(70,(((1+14)+51)+4))
(71,(-1+((14+(5-1))*4)))
(72,(((-1-1)+4)+(5*14)))
(73,(((-1*1)+4)+(5*14)))
(74,(((-1+(14*5))+1)+4))
(75,((((1*14)*5)+1)+4))
(76,(((1+(14*5))+1)+4))
(77,((11-4)+(5*14)))
(78,((1+1)+(((4*5)-1)*4)))
(79,(((-1+14)*5)+14))
(80,((((1+14)*5)+1)+4))
(81,((1*1)+(((4*5)*1)*4)))
(82,((1+1)+(((4*5)*1)*4)))
(83,((-1+(14*5))+14))
(84,((-1+1)+(((4*5)+1)*4)))
(85,((1+(14*5))+14))
(86,((1+1)+(((4*5)+1)*4)))
(87,((-1+(14*(5+1)))+4))
(88,(((1*14)*(5+1))+4))
(89,((1+(14*(5+1)))+4))
(90,(-114+(51*4)))
(91,((11*4)+(51-4)))
(92,(((1+1)*(45-1))+4))
(93,((((1+1)*45)-1)+4))
(94,((-1-1)+((4*(5+1))*4)))
(95,((((1+1)*45)+1)+4))
(96,((-1+1)+((4*(5+1))*4)))
(97,((1*1)+((4*(5+1))*4)))
(98,((1+1)+((4*(5+1))*4)))
(99,(((11*4)+51)+4))

-}