Marc A. Ziegert wrote:
i see only two solutions.
let menu = [215, 275, 335, 355, 420, 580]
let run x menu = [[c]|c<-menu,c==x]++[c:cs|c<-menu,c<x,cs<-run (x-c) (dropWhile
(/=c) menu)]
run 1505 menu
->
[[215,215,215,215,215,215,215],[215,355,355,580]]
You are right, I saw many solutions but they were all equivalent to just
those two. I did not avoid permutation-induced redundancy.
I was unsure how to eliminate that redundancy. After reading your
algorithm, I see it. Here is my algorithm modified.
import Data.List
import Control.Monad
-- exactly n v
-- items in v that sum to exactly n
-- returns list of solutions, each solution list of items
exactly :: (Real a) => a -> [a] -> [[a]]
exactly 0 v = return []
exactly n v = do
w@(c:w') <- tails v
guard (c <= n)
liftM (c :) (exactly (n - c) w)
-- for solutions that use items at most once,
-- change w to w'
play = exactly 1505 menu
menu = [215, 275, 335, 355, 420, 580]
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
