Text only | Text with Images

newLISP Fan Club

Forum => newLISP in the real world => Topic started by: cameyo on May 30, 2019, 10:28:30 AM

Title: Maximum Product Sublist
Post by: cameyo on May 30, 2019, 10:28:30 AM
Maximum Product Sublist

Given a list that contains both positive and negative integers, find the product of the maximum product sublist.
Code Select
(define (maxProd lst)
  (local (n maxprod pos neg)
    (setq n (length lst))
    (setq pos (array n '(0)))
    (setq neg (array n '(0)))
    (setq (pos 0) (lst 0)) ; pos[i] contains the positive product up to lst[i]
    (setq (neg 0) (lst 0)) ; neg[i] contains the negative product up to lst[i]
    (setq maxprod (lst 0))
    (for (i 0 (- n 1))
      ; the maximum of the three values
      (setq (pos i) (max (max (* (pos (- i 1)) (lst i)) (* (neg (- i 1)) (lst i))) (lst i)))
      ; the minimum of the three values
      (setq (neg i) (min (min (* (pos (- i 1)) (lst i)) (* (neg (- i 1)) (lst i))) (lst i)))
      (setq maxprod (max maxprod (pos i)))
    )
    maxprod
  )
)

(setq lst '(6 -3 -10 0 2))
(maxProd lst)
;-> 180
Sublist: (6 -3 -10)

(setq lst '(-1 -3 -10 0 60))
(maxProd lst)
;-> 60
Sublist: (60)

(setq lst '(-2 -3 0 -2 -40))
(maxProd lst)
;-> 80
Sublist: (-2 -40)

(setq lst '(-1 -2 -3))
(maxProd lst)
;-> 6

(setq lst '(0 -1))
(maxProd lst)
;-> 0

(setq lst '(0 0 0 0))
(maxProd lst)
;-> 0

Please, post your version :-)

cameyo



p.s. The "Maximum Sum sublist" problem is solved with the Kadane algorithm
Title: Re: Maximum Product Sublist
Post by: rickyboy on May 30, 2019, 11:57:08 AM
Here's my version.


Code Select
(define (maxProd lst)
  ;; lst must contain integers; note use of integer op `*`.
  (apply max
         (map (fn (prods) (apply * prods))
              (remove '() (powerset lst)))))
You'll need these functions.


Code Select
(define (mappend) (apply append (apply map (args))))
(define (powerset s)
  (if s
      (mappend (fn (x) (list (cons (s 0) x) x))
               (powerset (1 s)))
      '(())))
However, my code gets different answers for your inputs, so maybe I don't understand the problem statement.


Code Select
> (maxProd '(6 -3 -10 0 2))
360   ; i.e., (* 6 -3 -10 2)
> (maxProd '(-1 -3 -10 0 60))
1800   ; i.e., (* -3 -10 60)
> (maxProd '(-2 -3 0 -2 -40))
480   ; i.e., (* -2 -3 -2 -40)
> (maxProd '(-1 -2 -3))
6
> (maxProd '(0 -1))
0
> (maxProd '(0 0 0 0))
0
Title: Re: Maximum Product Sublist
Post by: cameyo on May 30, 2019, 12:42:54 PM
Hi rickyboy,

the sublist must contains only contiguous elements.

But your functions are useful anyway :-)
Title: Re: Maximum Product Sublist
Post by: rickyboy on May 30, 2019, 02:18:03 PM
Quote from: "cameyo"Hi rickyboy

Hi cameyo! :)


Quote from: "cameyo"the sublist must contains only contiguous elements.

But your functions are useful anyway :-)

Ah, ok!  Then my updated maxProd function is still very similar to my original.


Code Select
(define (maxProd lst)
  ;; lst must contain integers; note use of integer op `*`.
  (apply max
         (map (fn (prods) (apply * prods))
              (sublists lst))))
The difference is that the expression (remove '() (powerset lst)) is now replaced by the expression (sublists lst), which generates a list of the sublists (contiguous) of lst.



And this indeed yields the same results as your function does.


Code Select
> (maxProd '(6 -3 -10 0 2))
180
> (maxProd '(-1 -3 -10 0 60))
60
> (maxProd '(-2 -3 0 -2 -40))
80
> (maxProd '(-1 -2 -3))
6
> (maxProd '(0 -1))
0
> (maxProd '(0 0 0 0))
0
I leave the definition of sublists is a reader exercise.  This is how I get to "leave fun on the table," as Ralph did earlier. :)
Title: Re: Maximum Product Sublist
Post by: rrq on May 30, 2019, 07:55:03 PM
Indeed, sublist was a quite fun exercise. Thanks :) I ended up with the following as my "best" candidate:
Code Select
(define (sublists s (i 0) (n (inc (length s))) (N n))
  (collect (if (> n 2) (i (dec n) s) (> (setf n (dec N)) 2) ((inc i) (dec n) s)))) That one performed best for me, and (more or less incidentally) it lets you choose a later start point and a max length of the sub lists.



Implicit slice seemed to be ~10% faster than explicit slice, and the iterative collation was ~5 times faster than the recursive variant. I didn't try any imperative "push within double loop" variant as I would expect that to be even slower.
Title: Re: Maximum Product Sublist
Post by: cameyo on May 30, 2019, 11:07:37 PM
Hi rickyboy and ralph.ronnquist,

you're very friendly and competent.

And yes, newLISP is fun.

Have a nice day.

cameyo
Text only | Text with Images