# List algorithm

12 messages
Open this post in threaded view
|

## List algorithm

 Hello,is there an efficient algorithm that takes two positive numbers n and m andthat computes all lists l of numbers 0sum l == m) (powerSet [1..n]) would do the job,however I am looking for a more efficient approach. Help is greatlyappreciated, even a google search term would be fine :-) I really hope for a polynomial algorithm although I am not very optimisticabout this.Ciao,Steffen _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Open this post in threaded view
|

## Re: List algorithm

 "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
Open this post in threaded view
|

## Re: List algorithm

 [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
Open this post in threaded view
|

## Re: List algorithm

 [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
Open this post in threaded view
|

## Re: List algorithm

 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
Open this post in threaded view
|

## Re: List algorithm

 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
Open this post in threaded view
|

## Re: List algorithm

 Thank you for your responses.My algorithm that needs the described function performsso 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 iI wanted to iterate over all productions p, countingthe number n of Nonterminals at the right-hand side of p, computing all lists with n numbers whose sum is i andsplit the span accordingly. It works, however, the stringshave to be very, very short *g*Ciao and Thx,Steffen 2007/5/22, Jules Bean <[hidden email]>: 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 asyou're access the elements in 'some sensible order' (that is thecalculation dependencies are well-ordered)._______________________________________________ Haskell-Cafe mailing list[hidden email]http://www.haskell.org/mailman/listinfo/haskell-cafe -- Dipl.-Inform. Steffen MazanekInstitut für SoftwaretechnologieFakultät InformatikUniversität der Bundeswehr München85577 NeubibergTel: +49 (0)89 6004-2505 Fax: +49 (0)89 6004-4447E-Mail: [hidden email] _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Open this post in threaded view
|

## Re: List algorithm

 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 > 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.hsalg  =  flip partitionsDec _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Open this post in threaded view
|

## Re: List algorithm

 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
Open this post in threaded view
|

## Re: List algorithm

 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