List algorithm

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
12 messages Options
Reply | Threaded
Open this post in threaded view
|

List algorithm

Steffen Mazanek-5
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
Reply | Threaded
Open this post in threaded view
|

Re: List algorithm

Mark T.B. Carroll
"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
Reply | Threaded
Open this post in threaded view
|

Re: List algorithm

Mark T.B. Carroll-2
[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
Reply | Threaded
Open this post in threaded view
|

Re: List algorithm

Mark T.B. Carroll-2
[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
Reply | Threaded
Open this post in threaded view
|

Re: List algorithm

Matthew Brecknell
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
Reply | Threaded
Open this post in threaded view
|

Re: List algorithm

Jules Bean
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
Reply | Threaded
Open this post in threaded view
|

Re: List algorithm

Steffen Mazanek-5
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:
> 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



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

Re: List algorithm

Henning Thielemann
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
Reply | Threaded
Open this post in threaded view
|

Re: List algorithm

Henning Thielemann
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
Reply | Threaded
Open this post in threaded view
|

Re: List algorithm

Mark T.B. Carroll-2
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
Reply | Threaded
Open this post in threaded view
|

Re: List algorithm

haskell-2
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
Reply | Threaded
Open this post in threaded view
|

Re: List algorithm

Christian Maeder
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
*Combinatorics.Partitions> partitionsDec 5 3
[[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