Author Topic: Get the position in the list  (Read 3603 times)

0 Members and 1 Guest are viewing this topic.

xiaxiang

  • Guest
Get the position in the list
« on: March 04, 2013, 10:20:43 PM »
Hi,all
    Is there any way to get the position in the list and return the list of the result?
I found that http://forums.autodesk.com/t5/Visual-LISP-AutoLISP-and-General/Position-in-a-list/td-p/845496
Code: [Select]
(defun atom_nth (l a / i tmp)
(setq i 0)
(while l
(if (equal a (car l) 1e-14)
(setq tmp (cons i tmp)))
(setq l (cdr l) i (1+ i)))
(reverse tmp))
Code: [Select]
(atom_nth '(1 2 3 4 5) 1)
(0)

 (atom_nth '(1 2 3 4 5 1) 1)
(0 5)
Are there more elegant code?
Any suggestion will be appreciated.
Regards Xia

Faster

  • Guest
Re: Get the position in the list
« Reply #1 on: March 04, 2013, 11:19:57 PM »
recursive method:
Code - Auto/Visual Lisp: [Select]
  1. (defun atom_nth (l a / f)
  2.   (defun f (l a b)
  3.     (if l
  4.       (if (= a (car l))
  5.         (cons b (f (cdr l) a (1+ b)))
  6.         (f (cdr l) a (1+ b))
  7.         )
  8.       )
  9.     )
  10.   (f l a 0)
  11.   )
  12. ;;test : (atom_nth '(1 2 3 4 5 1) 1) => '(0 5)
  13. (defun atom_nth1 (l a / f b)
  14.   (defun f (l a b / c)
  15.     (if l
  16.     (if (setq c (member a l))
  17.       (cons (setq d (+ b (- (length l) (length c))))
  18.             (f (cdr c) a (1+ d))
  19.             )
  20.       (f (cdr l) a (1+ b))
  21.       )
  22.     )
  23.     )
  24.   (f l a 0)
  25.   )
  26. ;;test : (atom_nth1 '(0 1 2 3 4 5 1 1 2 1) 1) => '(1 6 7 9)
  27.  
« Last Edit: March 05, 2013, 03:42:41 AM by Faster »

CAB

  • Global Moderator
  • Seagull
  • Posts: 10401
Re: Get the position in the list
« Reply #2 on: March 04, 2013, 11:38:51 PM »
Some oldies
Code: [Select]
;;  CAB  10/18/2005
;;  returns a list of pointers (base 0) of the
;;  item found in the list
(defun getpos (itm lst / idn nlst)
  (setq idx -1)
  (while (< (setq idx (1+ idx)) (length lst))
    (and (= itm (nth idx lst))
         (setq nlst (cons idx nlst))))
  (reverse nlst)
)

;; (print (GetPos 3 '(1 2 3 1 2 3 1 3 5)))
;;  returns (2 5 7)

   
;;  CAB  12/17/2009
;;  returns a list of pointers (base 0) of the
;;  item found in the list
(defun getpos (pat lst / i plst)
  (setq i 0)
  (mapcar
    (function
      (lambda (x)
        (and (wcmatch x pat) (setq plst (cons i plst)))
        (setq i (1+ i))))
    lst)
  (reverse plst))

(defun c:test()
  (princ (getpos "*25" '("0425" "123" "345" "625")))
  (princ)
  )
I've reached the age where the happy hour is a nap. (°¿°)
Windows 10 core i7 4790k 4Ghz 32GB GTX 970
Please support this web site.

xiaxiang

  • Guest
Re: Get the position in the list
« Reply #3 on: March 05, 2013, 01:12:19 AM »
Some oldies
Code: [Select]
;;  CAB  10/18/2005
;;  returns a list of pointers (base 0) of the
;;  item found in the list
(defun getpos (itm lst / idn nlst)
  (setq idx -1)
  (while (< (setq idx (1+ idx)) (length lst))
    (and (= itm (nth idx lst))
         (setq nlst (cons idx nlst))))
  (reverse nlst)
)

;; (print (GetPos 3 '(1 2 3 1 2 3 1 3 5)))
;;  returns (2 5 7)

   
;;  CAB  12/17/2009
;;  returns a list of pointers (base 0) of the
;;  item found in the list
(defun getpos (pat lst / i plst)
  (setq i 0)
  (mapcar
    (function
      (lambda (x)
        (and (wcmatch x pat) (setq plst (cons i plst)))
        (setq i (1+ i))))
    lst)
  (reverse plst))

(defun c:test()
  (princ (getpos "*25" '("0425" "123" "345" "625")))
  (princ)
  )
Got it!Thankkk you Alan!
Now I think that we could use vl-position + nth remove.
My 2 cents
Code: [Select]
  (defun nth_ps (lst itm / i llst)
  (setq i -1)
  (mapcar '(lambda (x) (setq i (1+ i))(if (= itm(nth i lst))(setq llst(cons i llst)))) lst)
  (reverse llst)
  )
Regards
« Last Edit: March 05, 2013, 02:10:36 AM by xiaxiang »

gile

  • Gator
  • Posts: 2507
  • Marseille, France
Re: Get the position in the list
« Reply #4 on: March 05, 2013, 01:27:36 AM »
Hi,

Going a little further with functional programming features.
Rather than checking only the equality (using = or equals), the positions function requires a prédicate function as argument.

Code - Auto/Visual Lisp: [Select]
  1. (defun positions (pred lst / loop)
  2.   (defun loop (f l n a)
  3.     (if l
  4.       (loop f
  5.             (cdr l)
  6.             (1+ n)
  7.             (if (f (car l))
  8.               (cons n a)
  9.               a
  10.             )
  11.       )
  12.       (reverse a)
  13.     )
  14.   )
  15.   (loop (eval pred) lst 0 ())
  16. )

(positions  'zerop '(0 1 2 0 3 4 0)) -> (0 3 6)
(positions '(lambda (x) (= (rem x 3) 0)) '(3 5 2 6 8 7 1 0 4 9)) -> (0 3 7 9)

NOTA: the loop tail recursive function can easily be replaced with an imperative while statement.
Speaking English as a French Frog

xiaxiang

  • Guest
Re: Get the position in the list
« Reply #5 on: March 05, 2013, 02:26:26 AM »
Hi,

Going a little further with functional programming features.
Rather than checking only the equality (using = or equals), the positions function requires a prédicate function as argument.

NOTA: the loop tail recursive function can easily be replaced with an imperative while statement.
Thanks Gile!
It's surely more useful when we were adding a predicate function as argument to the "position" function.
BTW:I've never learn the method of using  recursive function.Always bypassing it when I saw
something about "recursive". :oops:

irneb

  • Water Moccasin
  • Posts: 1794
  • ACad R9-2016, Revit Arch 6-2016
Re: Get the position in the list
« Reply #6 on: March 05, 2013, 03:20:59 AM »
My take on it:
Code - Auto/Visual Lisp: [Select]
  1. (defun positions (key source compare / n)
  2.   (setq n -1)
  3.   (vl-remove nil (mapcar (function (lambda (item) (setq n (1+ n)) (cond ((compare key item) n)))) source)))
  4.  
  5. (defun positions= (key source)
  6.   (positions key source =))
  7.  
  8. (defun positions-eq (key source)
  9.   (positions key source eq))
  10.  
  11. (defun positions-equal (key source)
  12.   (positions key source equal))
Common sense - the curse in disguise. Because if you have it, you have to live with those that don't.

irneb

  • Water Moccasin
  • Posts: 1794
  • ACad R9-2016, Revit Arch 6-2016
Re: Get the position in the list
« Reply #7 on: March 05, 2013, 03:53:45 AM »
Or even more comprehensive:
Code - Auto/Visual Lisp: [Select]
  1. (defun positions  (key source compare / n)
  2.   (setq n -1)
  3.   (vl-remove nil
  4.     (mapcar (cond ((= (type compare) 'SYM) (function (lambda (item) (setq n (1+ n)) (cond ((apply compare (list item key)) n)))))
  5.                   (t (function (lambda (item) (setq n (1+ n)) (cond ((compare item key) n))))))
  6.             source)))
Can then use even such things as less-than (either quoted or direct):
Code: [Select]
_$ (positions 2 '(1 2 3 4 5 1) '<=)
(0 1 5)
_$ (positions 2 '(1 2 3 4 5 1) <=)
(0 1 5)
Common sense - the curse in disguise. Because if you have it, you have to live with those that don't.

Marc'Antonio Alessi

  • Swamp Rat
  • Posts: 1451
  • Marco
Re: Get the position in the list
« Reply #8 on: March 05, 2013, 04:21:53 AM »
Code: [Select]
; Marc'Antonio Alessi - http://xoomer.virgilio.it/alessi
; Function: ALE_Position - 11/03/2006
;
; Version 1.00
;
; Description:
;   returns the position of the first TstItm found
;   in a list (nth based) - Lisp version
;   > in Visual Lisp use: vl-position
;
; Arguments:
;   TstItm = Any AutoLISP symbol
;   In_Lst = A true list
;
; Return Values:
;   Integer or nil if TstItm is not member of the list
;
(defun ALE_Position (TstItm In_Lst / TmpLst)
  (if (setq TmpLst (member TstItm In_Lst))
    (- (length In_Lst) (length TmpLst))
  )
)
; Function: ALE_PositionS - 01/09/2005
;
; Version 1.00
;
; Description:
;   returns the positions of a item in a list (nth based)
;
; Arguments:
;   TstItm = Any AutoLISP symbol
;   In_Lst = A true list
;
; Return Values:
;   List or nil if TstItm is not member of the list
;
; Examples:
;   (setq alist '(0 1 2 3 4 3 5 3 6 3 3 7))
;
;   (ALE_PositionS 3 alist)
;   Returns: (3 5 7 9 10)
;
;
(defun ALE_PositionS (TstItm In_Lst / LstLen OutLst)
  (setq LstLen (1- (length In_Lst)))
  (while (vl-position TstItm In_Lst)
    (setq
      In_Lst (cdr (member TstItm In_Lst))
      OutLst (cons (- LstLen (length In_Lst)) OutLst)
    )
  )
  (reverse OutLst)
)
; slower
(defun ALE_PositionS2 (TstItm In_Lst / LstLen OutLst)
  (setq LstLen (1- (length In_Lst)))
  (while (setq In_Lst (member TstItm In_Lst))
    (setq
      In_Lst (cdr In_Lst)
      OutLst (cons (- LstLen (length In_Lst)) OutLst)
    )
  )
  (reverse OutLst)
)
; recursive
(defun ALE_PositionS_Rec (TstItm In_Lst / LstLng)
  (setq LstLng (1- (length In_Lst)))
  (ALE_PositionS_Rec_Aux
    TstItm (cdr (member TstItm In_Lst)) NthPos LstLng
  )
)
(defun ALE_PositionS_Rec_Aux (TstItm In_Lst NthPos LstLng)
  (if (vl-position TstItm In_Lst)
    (setq
      NthPos
        (ALE_PositionS_Rec_Aux
          TstItm (cdr (member TstItm In_Lst)) NthPos LstLng
        )
      NthPos (cons (- LstLng (length In_Lst)) NthPos)
    )
    (setq NthPos (cons (- LstLng (length In_Lst)) NthPos))
  )
)

Command: (ALE_PositionS 1 '(1 2 3 4 5 1))
(0 5)

irneb

  • Water Moccasin
  • Posts: 1794
  • ACad R9-2016, Revit Arch 6-2016
Re: Get the position in the list
« Reply #9 on: March 05, 2013, 06:25:06 AM »
With the alist variable as per your code's comment (length = 12)
Code: [Select]
Benchmarking ..... done for 32768 iterations. Sorted from fastest.
Statement                                Increment  Time(ms) Normalize  Relative
--------------------------------------------------------------------------------
(ALE_POSITIONS2 3 ALIST)                     32768      1404      1404      1.47
(ALE_POSITIONS 3 ALIST)                      32768      1482      1482      1.39
(ALE_POSITIONS_REC 3 ALIST)                  32768      1529      1529      1.35
(IB:POSITIONS= 3 ALIST)                      32768      1701      1701      1.21
(GILE:POSITIONS= 3 ALIST)                    16384      1029      2058      1.00
--------------------------------------------------------------------------------

Modified Gile's to work in a similar way:
Code - Auto/Visual Lisp: [Select]
  1. (defun Gile:positions= (key lst)
  2.   (Gile:positions (function (lambda (item) (= item key))) lst))

As the list length gets longer, mine seems to start out performing:
Code: [Select]
_$ (setq alist (apply 'append (list alist alist alist alist alist alist)))
(0 1 2 3 4 3 5 3 6 3 3 7 0 1 2 3 4 3 5 3 6 3 3 7 0 1 2 3 4 3 5 3 6 3 3 7 0 1 2 3 4 3 5 3 6 3 3 7 0 1 2 3 4 3 5 3 6 3 3 7 0 1 2 3 4 3 5 3 6 3 3 7)
_$ (QuickBench '((IB:Positions= 3 alist) (ALE_PositionS 3 alist) (ALE_PositionS2 3 alist) (ALE_PositionS_Rec 3 alist) (Gile:positions= 3 alist)))
Benchmarking ..... done for 16384 iterations. Sorted from fastest.
Statement                                Increment  Time(ms) Normalize  Relative
--------------------------------------------------------------------------------
(ALE_POSITIONS2 3 ALIST)                     16384      1762      1762      1.68
(ALE_POSITIONS 3 ALIST)                      16384      1934      1934      1.53
(IB:POSITIONS= 3 ALIST)                       8192      1031      2062      1.44
(ALE_POSITIONS_REC 3 ALIST)                   8192      1046      2092      1.42
(GILE:POSITIONS= 3 ALIST)                     8192      1481      2962      1.00
--------------------------------------------------------------------------------
Code: [Select]
_$ (setq alist (apply 'append (list alist alist alist alist alist alist)))
(0 1 2 3 4 3 5 3 6 3 3 7 0 1 2 3 4 3 5 3 6 3 3 7 0 1 2 3 4 3 5 3 6 3 3 7 0 1 2 3 4 3 5 3 6 3 3 7 0 1 2 3 4 3 5 3 6 3 3 7 0 1 2 3 4 3 5 3 6 3 3 7 0 1 2 3 4 3 5 3 6 3 3 7 0 1 2 3 4 3 5 3 6 3 3 7 0 1 2 3 4 3 5 3 6 3 3 7 0 1 2 3 4 3 5 3 6 3 3 7 0 1 2 3 4 3 5 3 6 3 3 7 0 1 2 3 4 3 5 3 6 3 3 7 0 1 2 3 4 3 5 3 6 3 3 7 0 1 2 3 4 3 5 3 6 3 3 7 0 1 2 3 4 3 5 3 6 3 3 7 0 1 2 3 4 3 5 3 6 3 3 7 0 1 2 3 4 3 5 3 6 3 3 7 0 1 2 3 4 3 5 3 6 3 3 7 0 1 2 3 4 3 5 3 6 3 3 7 0 1 2 3 4 3 5 3 6 3 3 7 0 1 2 3 4 3 5 3 6 3 3 7 0 1 2 3 4 3 5 3 6 3 3 7 0 1 2 3 4 3 5 3 6 3 3 7 0 1 2 3 4 3 5 3 6 3 3 7 0 1 2 3 4 3 5 3 6 3 3 7 0 1 2 3 4 3 5 3 6 3 3 7 0 1 2 3 4 3 5 3 6 3 3 7 0 1 2 3 4 3 5 3 6 3 3 7 0 1 2 3 4 3 5 3 6 3 3 7 0 1 2 3 4 3 5 3 6 3 3 7 0 1 2 3 4 3 5 3 6 3 3 7 0 1 2 3 4 3 5 3 6 3 3 7 0 1 2 3 4 3 5 3 6 3 3 7 0 1 2 3 4 3 5 3 6 3 3 7 0 1 2 3 4 3 5 3 6 3 3 7 0 1 2 3 4 3 5 3 6 3 3 7)
_$ (QuickBench '((IB:Positions= 3 alist) (ALE_PositionS 3 alist) (ALE_PositionS2 3 alist) (ALE_PositionS_Rec 3 alist) (Gile:positions= 3 alist)))
Benchmarking ..... done for 2048 iterations. Sorted from fastest.
Statement                                Increment  Time(ms) Normalize  Relative
--------------------------------------------------------------------------------
(IB:POSITIONS= 3 ALIST)                       2048      1154      1154      1.68
(ALE_POSITIONS2 3 ALIST)                      2048      1311      1311      1.48
(ALE_POSITIONS 3 ALIST)                       2048      1451      1451      1.33
(ALE_POSITIONS_REC 3 ALIST)                   2048      1530      1530      1.26
(GILE:POSITIONS= 3 ALIST)                     2048      1935      1935      1.00
--------------------------------------------------------------------------------
Common sense - the curse in disguise. Because if you have it, you have to live with those that don't.

Lee Mac

  • Seagull
  • Posts: 12905
  • London, England
Re: Get the position in the list
« Reply #10 on: March 05, 2013, 07:38:09 AM »
Two more simple ones:

Code - Auto/Visual Lisp: [Select]
  1. (defun positions1 ( p l / n r )
  2.     (setq n (length l))
  3.     (while (setq l (vl-member-if p l))
  4.         (setq r (cons (- n (length l)) r)
  5.               l (cdr l)
  6.         )
  7.     )
  8.     (reverse r)
  9. )

Code - Auto/Visual Lisp: [Select]
  1. (defun positions2 ( p l / i r )
  2.     (setq i 0 p (eval p))
  3.     (foreach x l
  4.         (if (p x) (setq r (cons i r)))
  5.         (setq i (1+ i))
  6.     )
  7.     (reverse r)
  8. )

Code - Auto/Visual Lisp: [Select]
  1. _$ (positions1 'zerop '(0 1 2 4 0 1 2))
  2. (0 4)
  3. _$ (positions2 '(lambda ( x ) (= 2 x)) '(0 1 2 4 0 1 2))
  4. (2 6)

Marc'Antonio Alessi

  • Swamp Rat
  • Posts: 1451
  • Marco
Re: Get the position in the list
« Reply #11 on: March 05, 2013, 10:13:14 AM »
Code: [Select]
Benchmark.lsp | © 2005 Michael Puckett | All Rights Reserved

(setq alist nil) (setq alist2 '(1 2 3 4 4 5 5 5 6 7 8 9 9 9 9))
(setq alist (repeat 500 (setq alist (append alist alist2))))

Elapsed milliseconds / relative speed for 8192 iteration(s):

    (ALE_POSITIONS "ATOI" ALIST)........2044 / 36.15 <fastest>
    (IB:POSITIONS "ATOI" ALIST =)......51668 / 1.43
    (GILE:POSITIONS= "ATOI" ALIST).....73898 / 1 <slowest>

;----------------------------------------------------------------

(setq alist (atoms-family 1))
(setq alist (append alist alist alist alist))

Elapsed milliseconds / relative speed for 256 iteration(s):

    (ALE_POSITIONS "ATOI" ALIST).......1779 / 4.31 <fastest>
    (IB:POSITIONS "ATOI" ALIST =)......7223 / 1.06
    (GILE:POSITIONS= "ATOI" ALIST).....7659 / 1 <slowest>

xiaxiang

  • Guest
Re: Get the position in the list
« Reply #12 on: March 05, 2013, 07:24:40 PM »
Thanks all :-)

gile

  • Gator
  • Posts: 2507
  • Marseille, France
Re: Get the position in the list
« Reply #13 on: March 06, 2013, 01:02:31 AM »
Hi,

I wasn't looking for speed performance, I only wanted to show how to build a generic higher order function which accepts as argument any predicate function (not only an equality or a comparison function).

I wrote it recursively because it's the way it came in my mind. Lee's positions1 shows a way to replace the auxiliary recursive function (loop) with a while statement.

If I really wanted to win some milliseconds and/or deal with very large collection, I won't use AutoLISP...

Speaking English as a French Frog

gile

  • Gator
  • Posts: 2507
  • Marseille, France
Re: Get the position in the list
« Reply #14 on: March 06, 2013, 01:28:16 AM »
For those who're interested, the same thing using F# with almost as concision as LISP plus the performances of .NET environnment.

The same as I posted upper (F# runtime does optimize the tail recursion) which works with F# lists (linked lists as LISP ones)
Code - F#: [Select]
  1. let positions predicate lst =
  2.     let rec loop n a = function
  3.         | []   -> a |> List.rev
  4.         | h::t -> loop (n + 1) (if predicate h then n::a else a) t
  5.     loop 0 [] lst

Another way using function composition, which works with F# sequences, that's to say any enumerable .NET collection (linked list, fixed size or resizable arrays, dictionaries, ...)
Code - F#: [Select]
  1. let positions predicate =
  2.     Seq.mapi (fun i x -> if predicate x then Some(i) else None)
  3.     >> Seq.choose (fun x -> x)
Speaking English as a French Frog