Hello,
is there an efficient algorithm that takes two positive numbers n and m and that computes all lists l of numbers 0<x<=n such that sum l = m? For instance alg 5 1 = [[1]] alg 5 2 = [[1,1],[2]] alg 5 3 = [[1,1,1],[1,2],[2,1],[3]] ... I know that filter (\l->sum l == m) (powerSet [1..n]) would do the job, however I am looking for a more efficient approach. Help is greatly appreciated, even a google search term would be fine :-) I really hope for a polynomial algorithm although I am not very optimistic about this. Ciao, Steffen _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
"Steffen Mazanek" <[hidden email]> writes:
> alg 5 1 = [[1]] > alg 5 2 = [[1,1],[2]] > alg 5 3 = [[1,1,1],[1,2],[2,1],[3]] Would this be better? alg n m = case signum m of -1 -> [] 0 -> [[]] 1 -> [ x : xs | x <- [1..n], xs <- alg n (m - x) ] -- Mark _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
[hidden email] (Mark T.B. Carroll) writes:
> alg n m = > case signum m of > -1 -> [] > 0 -> [[]] > 1 -> [ x : xs | x <- [1..n], xs <- alg n (m - x) ] FWIW it's faster if you do some memoising: algMemo n m = lookupMemo m where memo = [[]] : map helper [1..m] lookupMemo m = if m < 0 then [] else memo !! m helper m' = [ x : xs | x <- [1..n], xs <- lookupMemo (m' - x) ] -- Mark _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
[hidden email] (Mark T.B. Carroll) writes:
(snip) > algMemo n m = lookupMemo m > where > memo = [[]] : map helper [1..m] > lookupMemo m = if m < 0 then [] else memo !! m > helper m' = [ x : xs | x <- [1..n], xs <- lookupMemo (m' - x) ] which, I suppose, is rather like, algMemo n m = last memo where memo = [[]] : map helper [1 .. m] helper m' = [ x : xs | x <- [1 .. min m' n], xs <- memo !! (m' - x) ] -- Mark _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
Mark T.B. Carroll:
> algMemo n m = last memo > where > memo = [[]] : map helper [1 .. m] > helper m' = [ x : xs | x <- [1 .. min m' n], xs <- memo !! (m' - x) ] This made me wonder whether it's safe to access an array while it's still under construction: > import Data.Array.IArray > > algArr n m = memo ! m where > memo :: Array Int [[Int]] > memo = listArray (0,m) $ [[]] : map helper [1..m] > helper i = [ x:xs | x <- [1..min i n], xs <- memo ! (i-x) ] This seems to work, but presumably only because it's a boxed array, and the construction makes no circular references. However, I'm doubtful that memoisation is really beneficial in this function. I think it only gains a constant-factor speedup, but loses the ability to work in constant space. _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
Matthew Brecknell wrote:
> This seems to work, but presumably only because it's a boxed array, and > the construction makes no circular references. Yes, AIUI the boxed arrays are strict in indices but lazy in values. Therefore they can be used for this kind of memoization trick as long as you're access the elements in 'some sensible order' (that is the calculation dependencies are well-ordered). _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
Thank you for your responses.
My algorithm that needs the described function performs so horribily bad that I understand now the need for CNF :-) The idea was to write a CYK-style parser for an arbitrary context-free grammar without transformation to CNF. To compute derivations for a span of length i I wanted to iterate over all productions p, counting the number n of Nonterminals at the right-hand side of p, computing all lists with n numbers whose sum is i and split the span accordingly. It works, however, the strings have to be very, very short *g* Ciao and Thx, Steffen
2007/5/22, Jules Bean <[hidden email]>: Matthew Brecknell wrote: -- Dipl.-Inform. Steffen Mazanek Institut für Softwaretechnologie Fakultät Informatik Universität der Bundeswehr München 85577 Neubiberg Tel: +49 (0)89 6004-2505 Fax: +49 (0)89 6004-4447 E-Mail: [hidden email] _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Steffen Mazanek-5
On Mon, 21 May 2007, Steffen Mazanek wrote: > is there an efficient algorithm that takes two positive numbers n and m and > that computes all lists l of numbers 0<x<=n such that sum l = m? > > For instance > alg 5 1 = [[1]] > alg 5 2 = [[1,1],[2]] > alg 5 3 = [[1,1,1],[1,2],[2,1],[3]] > ... http://darcs.haskell.org/htam/src/Combinatorics/Partitions.hs alg = flip partitionsDec _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Mark T.B. Carroll
On Mon, 21 May 2007, Mark T.B. Carroll wrote: > "Steffen Mazanek" <[hidden email]> writes: > > > alg 5 1 = [[1]] > > alg 5 2 = [[1,1],[2]] > > alg 5 3 = [[1,1,1],[1,2],[2,1],[3]] > > Would this be better? > > alg n m = > case signum m of > -1 -> [] > 0 -> [[]] > 1 -> [ x : xs | x <- [1..n], xs <- alg n (m - x) ] This would produce compiler warnings. What about: case compare m 0 of GT -> EQ -> LT -> ? _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Matthew Brecknell
"Matthew Brecknell" <[hidden email]> writes:
(snip) > This seems to work, but presumably only because it's a boxed array, and > the construction makes no circular references. Yes. (-: > However, I'm doubtful that memoisation is really beneficial in this > function. I think it only gains a constant-factor speedup, but loses the > ability to work in constant space. I don't know. The memoised version certainly calls the bit with the list comprehension fewer times. I'd have to think about it more. -- Mark _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Matthew Brecknell
Matthew Brecknell wrote:
> Mark T.B. Carroll: >> algMemo n m = last memo >> where >> memo = [[]] : map helper [1 .. m] >> helper m' = [ x : xs | x <- [1 .. min m' n], xs <- memo !! (m' - x) ] > > This made me wonder whether it's safe to access an array while it's > still under construction: > >> import Data.Array.IArray >> >> algArr n m = memo ! m where >> memo :: Array Int [[Int]] >> memo = listArray (0,m) $ [[]] : map helper [1..m] >> helper i = [ x:xs | x <- [1..min i n], xs <- memo ! (i-x) ] > > This seems to work, but presumably only because it's a boxed array, and > the construction makes no circular references. > > However, I'm doubtful that memoisation is really beneficial in this > function. I think it only gains a constant-factor speedup, but loses the > ability to work in constant space. > If you call this function many times you may want to keep (some of) the memo table between calls: m'store,m'store'temp :: Int m'store = 4 m'store'temp = 10 m'arr :: Array Int [[Int]] m'arr = listArray (0,m'store) $ [[]] : map helper [1..m'store] where helper i = [ x:xs | x <- [1..i], xs <- m'arr ! (i-x) ] alg :: Int -> Int -> [[Int]] alg _n m | m < 0 = error "alg: Cannot total to negative" alg n m = if m > m'store'temp then [ x : xs | x <- [1..min n m], xs <- alg n (m-x) ] else let cached = if m <= m'store then m'arr ! m else m'temp ! m in if n >= m then cached else filter (all (<=n)) cached where bound = (succ m'store, min m m'store'temp) m'temp :: Array Int [[Int]] m'temp = listArray bound (map help (range bound)) help i = [ x : xs | x <- [1..min n i], xs <- alg i (m-i) ] The above uses some space for the global memo table m'arr and for a given call may use additional space for m'temp. For m larger than m'store'temp it will not allocate a memo table will run slower (but without consuming so much space). *Main> alg 6 5 [[1,1,1,1,1],[1,1,1,2],[1,1,2,1],[1,1,3],[1,2,1,1],[1,2,2],[1,3,1],[1,4],[2,1,1,1],[2,1,2],[2,2,1],[2,3],[3,1,1],[3,2],[4,1],[5]] _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Henning Thielemann
Henning Thielemann schrieb:
> On Mon, 21 May 2007, Steffen Mazanek wrote: > >> is there an efficient algorithm that takes two positive numbers n and m and >> that computes all lists l of numbers 0<x<=n such that sum l = m? >> >> For instance >> alg 5 1 = [[1]] >> alg 5 2 = [[1,1],[2]] >> alg 5 3 = [[1,1,1],[1,2],[2,1],[3]] >> ... > > http://darcs.haskell.org/htam/src/Combinatorics/Partitions.hs > > alg = flip partitionsDec [[3],[2,1],[1,1,1]] so [1,2] is missing. And for these partitions I've also the attached module. *Partition> parts 3 [3,2 1,1 1 1] Christian module Partition where {- | a strictly increasing list of pairs where the second components are the frequencies -} newtype Part = Part [(Int, Int)] deriving (Eq, Ord) instance Show Part where show (Part l) = showIntList $ partToList $ reverse l showIntList :: [Int] -> String showIntList = unwords . map show partToList :: [(Int, Int)] -> [Int] partToList = concatMap ( \ (v, f) -> replicate f v) infixr 5 >: (>:) :: (Int, Int) -> [(Int, Int)] -> [(Int, Int)] p@(_, c) >: l = if c == 0 then l else p : l extendPart :: [(Int, Int)] -> [[(Int, Int)]] extendPart l = case l of [] -> [] (v, c) : r -> if v == 1 then case r of [] -> [l] (v2, c2) : s -> let i = v2 - 1 (di, mi) = divMod (c + v2) i in l : extendPart ( (if mi == 0 then id else ((mi, 1) :)) $ (i, di) : (v2, c2 - 1) >: s) else l : extendPart ( (if v == 2 then [(1, 2)] else [(1, 1), (v - 1, 1)]) ++ (v, c - 1) >: r) parts :: Int -> [Part] parts n = if n < 0 then [] else if n == 0 then [Part []] else map Part $ extendPart [(n, 1)] _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
Free forum by Nabble | Edit this page |