A shop is giving 10% of the price you pay free for the next thing you buy. You need to buy n things. In what order should you pay them in order to spend as few money as possible ?

prix.hs

-- A shop is giving a voucher of 10% of the price you pay for everything you buy.
-- The voucher is usable only on the next article you buy.
-- You need to buy n things. In what order should you pay them in order to spend as few money as possible ?

-- Example:
--   You need to buy 3 articles, which cost respectively $1, $10 and $100
--   Then you should buy them in the following order: $1, $100, $10
--   Thus, you will pay 1 + 100 - 1 * 10% + 10 - (100 - 1 * 10%) * 10% = 1 + 99.9 + 0.01 = 100.91
--   This is better than you would do with any other ordering.

-- (of course, if at one point you happen to have a reduction higher then the price of the next article
-- you want to buy, the shop doesn't give you money. You can only pay positive amounts of money) 

-- Complexity of this implementation: O(n!) (just tries everything)

q = 0.1

-- Given an ordered list of raw product prices, return the list of the prices you will actually pay
prices :: [Double] -> [Double]
prices us =
  let
    reducer (v:vs) u = (max 0 (u - q*v)) : v : vs
  in
    foldl reducer [0] us

-- Given an ordered list of raw product prices, return the total price you will pay
price = sum . prices

-- Returns a list of all possible orderings of a list
allorders :: [a] -> [[a]]
allorders [] = [[]]
allorders xs =
  let
    sublists [] = []
    sublists (a:as) = (a,as) : (map (\(x,xs) -> (x,a:xs)) (sublists as))
  in
    concatMap (\(a,as) -> map (a:) (allorders as)) (sublists xs) 

-- Given a list of unordered product prices, returns a tuple (best price, best ordering)
bestprice :: [Double] -> (Double, [Double])
bestprice us =
  let
    o = allorders us
    orders = zip (map price o) o
  in
    minimum orders

-- Print information about the solution
affiche :: [Double] -> [Char]
affiche us =
  let
    (p, order) = bestprice us
    succ = tail $ reverse $ prices order
  in
    "Price: " ++ (show p) ++ "\n" ++
    "Order: " ++ (show order) ++ "\n" ++
    "Paid prices for each product: " ++ (show succ) ++ "\n"

-- Compile: ghc ./prix.hs
-- Use: echo "[1,2,3,4]" | ./prix
main = do
  us <- getLine
  putStrLn $ affiche ((read us)::[Double])