Author Topic: List Functions  (Read 7371 times)

0 Members and 1 Guest are viewing this topic.

Lee Mac

  • Seagull
  • Posts: 12906
  • London, England
Re: List Functions
« Reply #15 on: December 29, 2013, 11:22:10 AM »
That'a a good 1 !

Thanks David  :-)

This version might be more efficient:
Code - Auto/Visual Lisp: [Select]
  1. (defun lcm ( l )
  2.     (if (cdr l)
  3.         (* (/ (car l) (gcd (car l) (cadr l))) (lcm (cdr l)))
  4.         (car l)
  5.     )
  6. )

Lee Mac

  • Seagull
  • Posts: 12906
  • London, England
Re: List Functions
« Reply #16 on: December 29, 2013, 11:52:26 AM »
On second look, I don't think this 1 works
Code: [Select]
  (setq lst '(2 5 5 5 6 7 10 10 10 12))
  (lcm lst)
  25200

Back to the drawing board on that one :-(

David Bethel

  • Swamp Rat
  • Posts: 656
Re: List Functions
« Reply #17 on: December 29, 2013, 12:02:12 PM »
I tried removing the duplicate atoms to no avail.  -David
R12 Dos - A2K

Lee Mac

  • Seagull
  • Posts: 12906
  • London, England
Re: List Functions
« Reply #18 on: December 29, 2013, 12:20:30 PM »
New method:
Code - Auto/Visual Lisp: [Select]
  1. (defun lcm ( l )
  2.     (if (cddr l)
  3.         (lcm (list (car l) (lcm (cdr l))))
  4.         (/ (apply '* l) (apply 'gcd l))
  5.     )
  6. )

Lee Mac

  • Seagull
  • Posts: 12906
  • London, England
Re: List Functions
« Reply #19 on: December 29, 2013, 12:24:51 PM »
Or perhaps more efficiently:
Code - Auto/Visual Lisp: [Select]
  1. (defun lcml ( l )
  2.     (if (cddr l)
  3.         (lcm (car l) (lcml (cdr l)))
  4.         (apply 'lcm l)
  5.     )
  6. )
  7. (defun lcm ( a b ) (* b (/ a (gcd a b))))
Code - Auto/Visual Lisp: [Select]
  1. _$ (lcml '(2 5 5 5 6 7 10 10 10 12))
  2. 420
« Last Edit: December 29, 2013, 12:28:11 PM by Lee Mac »

Lee Mac

  • Seagull
  • Posts: 12906
  • London, England
Re: List Functions
« Reply #20 on: December 29, 2013, 12:30:45 PM »
And an iterative version:
Code - Auto/Visual Lisp: [Select]
  1. (defun lcml ( l / r )
  2.     (setq r (lcm (car l) (cadr l)))
  3.     (foreach x (cddr  l) (setq r (lcm r x)))
  4.     r
  5. )
  6. (defun lcm ( a b ) (* b (/ a (gcd a b))))

gile

  • Gator
  • Posts: 2507
  • Marseille, France
Re: List Functions
« Reply #21 on: December 29, 2013, 06:13:09 PM »
Hi,

Inspired by the F# List.reduce function.

F# doesn't have an OOTB 'gcd' function, but it's easy to implement.

Code - F#: [Select]
  1. let rec gcd x y = if y = 0 then x else gcd y (x % y)
  2.    
  3. let lcm = List.reduce(fun a b -> a * b / gcd a b)

With AutoLISP, using a reusable 'gc:reduce' function:

Code - Auto/Visual Lisp: [Select]
  1. ;; gc:reduce
  2. ;; (gc:reduce 'f '(i0 i1 i2 ... in)) computes: (f ... (f (f i0 i1) i2) ... in)
  3. (defun gc:reduce (fun lst)
  4.   (setq fun (eval fun))
  5.   (while (cdr lst)
  6.     (setq lst (cons (fun (car lst) (cadr lst)) (cddr lst)))
  7.   )
  8.   (car lst)
  9. )
  10.  
  11. (defun lcm (lst) (gc:reduce '(lambda (a b) (/ (* a b) (gcd a b))) lst))

You can find some others List Functions here (sorry for the french comments)
« Last Edit: December 30, 2013, 05:25:39 AM by gile »
Speaking English as a French Frog

Lee Mac

  • Seagull
  • Posts: 12906
  • London, England
Re: List Functions
« Reply #22 on: December 29, 2013, 07:09:31 PM »
Prime Factors would be cool

Not quite as easy:

Code - Auto/Visual Lisp: [Select]
  1. (defun pf ( n / c i p r )
  2.     (setq p 2)
  3.     (while (< 1 n)
  4.         (if (< 0 (rem n p))
  5.             (progn
  6.                 (setq c (fix (1+ (sqrt n)))
  7.                       i 3
  8.                       p n
  9.                 )
  10.                 (while (< i c)
  11.                     (if (zerop (rem n i))
  12.                         (setq p i
  13.                               i c
  14.                         )
  15.                     )
  16.                     (setq i (+ i 2))
  17.                 )
  18.             )
  19.         )
  20.         (setq r (cons p r)
  21.               n (/ n p)
  22.         )
  23.     )
  24.     (reverse r)
  25. )

Or, recursively:
Code - Auto/Visual Lisp: [Select]
  1. (defun pf ( n / f )
  2.     (defun f ( n p / c i )
  3.         (if (< 1 n)
  4.             (if (zerop (rem n p))
  5.                 (cons p (f (/ n p) p))
  6.                 (progn
  7.                     (setq c (fix (1+ (sqrt n)))
  8.                           i 3
  9.                           p n
  10.                     )
  11.                     (while (< i c)
  12.                         (if (zerop (rem n i))
  13.                             (setq p i
  14.                                   i c
  15.                             )
  16.                         )
  17.                         (setq i (+ i 2))
  18.                     )
  19.                     (cons p (f (/ n p) p))
  20.                 )
  21.             )
  22.         )
  23.     )
  24.     (f n 2)
  25. )

Code - Auto/Visual Lisp: [Select]
  1. _$ (pf 360315)
  2. (3 3 3 5 17 157)

gile

  • Gator
  • Posts: 2507
  • Marseille, France
Re: List Functions
« Reply #23 on: December 30, 2013, 06:24:01 AM »
A more efficient implementation of gc:reduce (I forgot I posted this)

Code - Auto/Visual Lisp: [Select]
  1. ;; gc:reduce
  2. ;; (gc:reduce 'f '(i0 i1 i2 ... in)) computes: (f ... (f (f i0 i1) i2) ... in)
  3. (defun gc:reduce (fun lst / acc)
  4.   (setq fun (eval fun)
  5.         acc (car lst)
  6.   )
  7.   (foreach n (cdr lst) (setq acc (fun acc n)))
  8. )
Speaking English as a French Frog

Lee Mac

  • Seagull
  • Posts: 12906
  • London, England
Re: List Functions
« Reply #24 on: December 30, 2013, 06:31:43 AM »
Look back at our prime factorisation thread, this would be more efficient:

Code - Auto/Visual Lisp: [Select]
  1. (defun pf ( n / m p r )
  2.     (setq p 2)
  3.     (while (< 1 n)
  4.         (while (zerop (rem n p))
  5.             (setq r (cons p r)
  6.                   n (/ n p)
  7.             )
  8.         )
  9.         (if (< 1 (setq m (sqrt n)) (setq p (if (= p 2) 3 (+ 2 p))))
  10.             (setq r (cons n r)
  11.                   n 0
  12.             )
  13.             (while (and (<= p m) (< 0 (rem n p)))
  14.                 (setq p (+ 2 p))
  15.             )
  16.         )
  17.     )
  18.     (reverse r)
  19. )

David Bethel

  • Swamp Rat
  • Posts: 656
Re: List Functions
« Reply #25 on: December 30, 2013, 09:01:21 AM »
Maybe like thus ?

Least Common Multiple - Product of the prime factors


using Lee's pf prime_factor's:

Code: [Select]
(defun pf ( n / m p r ) ; LeeMac
  (setq p 2)
  (while (< 1 n)
         (while (zerop (rem n p))
                (setq r (cons p r)
                      n (/ n p)))
         (if (< 1 (setq m (sqrt n))
                  (setq p (if (= p 2) 3 (+ 2 p))))
             (setq r (cons n r)
                   n 0)
             (while (and (<= p m)
                         (< 0 (rem n p)))
                    (setq p (+ 2 p)))))
  (reverse r))

(defun ListLCM (l / pl fl)
  (foreach a l
    (setq pl (pf a))
    (foreach f pl
       (if (not (member f fl))
           (setq fl (cons f fl)))))
  (apply '* fl))


-David
« Last Edit: December 30, 2013, 09:05:58 AM by David Bethel »
R12 Dos - A2K

Lee Mac

  • Seagull
  • Posts: 12906
  • London, England
Re: List Functions
« Reply #26 on: December 30, 2013, 09:19:20 AM »
Maybe like thus ?

Least Common Multiple - Product of the prime factors

I could be wrong, but I thought:

LCM = product of distinct prime factors with the highest powers

So the function may need to be something like:
Code: [Select]
(defun listlcm ( l / a n p r x )
    (while l
        (setq x (car l)
              l (vl-remove x (cdr l))
              p (pf x)
        )
        (while p
            (setq x (car p)
                  n (length p)
                  p (vl-remove x (cdr p))
                  n (- n (length p))
                  a (assoc x r)
            )
            (if a
                (if (< (cadr a) n)
                    (setq r (subst (list x n) a r))
                )
                (setq r (cons (list x n) r))
            )
        )
    )
    (apply '* (mapcar '(lambda ( x ) (apply 'expt x)) r))
)
Code: [Select]
_$ (listlcm '(2 5 5 5 6 7 10 10 10 12))
420

roy_043

  • Water Moccasin
  • Posts: 1895
  • BricsCAD 18
Re: List Functions
« Reply #27 on: December 30, 2013, 10:08:19 AM »
Are negative integers allowed in the input list for the LCM function?
Code: [Select]
(listlcm '(-24  18  10)) =>  90
(listlcm '( 24 -18  10)) => 120
(listlcm '( 24  18 -10)) =>  72
(listlcm '(-24 -18  10)) =>  10
(listlcm '(-24  18 -10)) =>  18
(listlcm '( 24 -18 -10)) =>  24
(listlcm '(-24 -18 -10)) =>   0

David Bethel

  • Swamp Rat
  • Posts: 656
Re: List Functions
« Reply #28 on: December 30, 2013, 10:22:37 AM »
http://en.wikipedia.org/wiki/Least_common_multiple

Quote
The LCM of more than two integers is also well-defined: it is the smallest integer that is divisible by each of them

Looks like mine is it working properly.........  -David
R12 Dos - A2K

Lee Mac

  • Seagull
  • Posts: 12906
  • London, England
Re: List Functions
« Reply #29 on: December 30, 2013, 10:37:41 AM »
http://en.wikipedia.org/wiki/Least_common_multiple

Quote
The LCM of more than two integers is also well-defined: it is the smallest integer that is divisible by each of them

Looks like mine is it working properly.........  -David

Testing yours:
Code - Auto/Visual Lisp: [Select]
  1. _$ (ListLCM '(2 5 5 5 6 7 10 10 10 12))
  2. 210
  3. _$ (/ 210 12.)
  4. 17.5
Correct LCM is 420