Topic: Exercise in List Manipulation ~ Bring Element to Front of List

[Lee Mac]

This surfaced in a recent project of mine, and I thought I'd post it as a bit of fun for you all.

The "Challenge" is to bring a list element to the front of the list (i.e. position 0)

Hence:

Code: [Select]

(ToFront 3 '(1 2 3 4 5))

Returns:  (4 1 2 3 5)

I came up with a few versions of my own... but I leave it open for you to add your twists/varieties 

Code: [Select]

(defun ToFront1 (i lst / j)
  (setq j (nth i lst))
  (cond ((zerop i) lst)
        ((append (list j)
                 (reverse (cdr (member j (reverse lst))))
                 (cdr (member j lst))))))


Code: [Select]

(defun ToFront2 (i lst)
  (cond ((zerop i) lst)
        ((cons (nth i lst)
               (remove_nth i lst)))))

(defun remove_nth (i lst / j)
  (setq j -1)
  (vl-remove-if
    (function
      (lambda (x)
        (eq i (setq j (1+ j))))) lst))


Enjoy! 

[Lee Mac]

Just out of interest:

Code: [Select]

  (setq lst '(1 2 3 4 5 6 7 8 9 0))


Code: [Select]

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

    (TOFRONT1 5 LST).....1170 / 1.79 <fastest>
    (TOFRONT2 5 LST).....2090 / 1.00 <slowest>


[CAB]

Maybe this:

Code: [Select]

(defun ToFrontCAB(n lst / i nlst)
  (setq i (length lst))
  (while (> (setq i (1- i)) -1)
    (or (= i n) (setq nlst (cons (nth i lst) nlst))))
  (setq nlst (cons (nth n lst) nlst))
)

[CAB]

Code: [Select]

(defun ToFrontCAB2(n lst / i itm nlst target)
  (setq i -1)
  (while (setq itm (car lst))
    (setq lst (cdr lst))
    (if (= (setq i (1+ i)) n)
      (setq target itm)
      (setq nlst (cons itm nlst))
     ))
  (setq nlst (cons target (reverse nlst)))
)

Code: [Select]

(defun ToFrontCAB3 (n lst / i nlst target)
  (setq i -1)
  (mapcar (function (lambda (x)
                      (if (= (setq i (1+ i)) n)
                        (setq target x)
                        (setq nlst (cons x nlst))
                      ))) lst)
  (setq nlst (cons target (reverse nlst)))
)

[alanjt]

Code: [Select]

(defun MegaCuts1 (n lst / cnt)
  (setq cnt -1)
  (cons (nth n lst) (vl-remove-if
    '(lambda (x)
       (eq n (setq cnt (1+ cnt))))
    lst)))


(defun MegaCuts2 (n lst / cnt L)
  (setq cnt -1)
  (while (< cnt (1- (length lst)))
    (if (/= n (setq cnt (1+ cnt)))
      (setq L (cons (nth cnt lst) L))))
  (cons (nth n lst) (reverse L)))

[alanjt]

Code: [Select]

(defun MetaCuts3 (n lst / cnt L)
  (setq cnt -1)
  (repeat (length lst)
    (if (/= n (setq cnt (1+ cnt)))
      (setq L (cons (nth cnt lst) L))))
  (cons (nth n lst) (reverse L)))...and I'm off to bed.

[gile]

Hi,

Code: [Select]

(defun ToFrontGile (ind lst / RemoveAt result target)
  (defun RemoveAt (ind lst RemovedItem)
    (if (zerop ind)
      (progn
        (set RemovedItem (car lst))
        (cdr lst)
      )
      (cons (car lst) (RemoveAt (1- ind) (cdr lst) RemovedItem))
    )
  )
  (setq result (RemoveAt ind lst 'target))
  (cons target result)
)

[VovKa]

Code: [Select]

(defun ToFront_VovKa (n lst / rest)
  (if lst
    (if (zerop n)
      lst
      (cons (car (setq rest (ToFront_VovKa (1- n) (cdr lst))))
    (cons (car lst) (cdr rest))
      )
    )
  )
)


[gile]

Nice VovKa.

Lee, ToFront1 returns a false result if the target item appears twice in the list:

(ToFrontLee1 5 '(1 2 5 3 4 5 6 7))
returns (5 1 2 5 3 4 3 4 5 6 7) instead of (5 1 2 5 3 4 6 7)

Another one:

Code: [Select]

(defun ToFrontGile2 (ind lst / tmp)
  (while (/= 0 ind)
    (setq tmp (cons (car lst) tmp)
          lst (cdr lst)
          ind (1- ind)
    )
  )
  (cons (car lst) (append (reverse tmp) (cdr lst)))
)

_$ (setq lst '(1 2 3 4 5 6 7 8 9 0))
(benchmark '((ToFrontLee2 5 lst)
             (ToFrontCAB 5 lst)
             (ToFrontCAB2 5 lst)
             (ToFrontCAB3 5 lst)
             (MegaCuts1 5 lst)
             (MegaCuts2 5 lst)
             (Metacuts3 5 lst)
             (ToFrontGile 5 lst)
             (ToFrontGile2 5 lst)
             (ToFront_VovKa 5 lst)
            )
)
(1 2 3 4 5 6 7 8 9 0)
Benchmarking ..................Elapsed milliseconds / relative speed for 32768 iteration(s):

    (TOFRONTGILE2 5 LST)......1391 / 2.37 <fastest>
    (TOFRONT_VOVKA 5 LST).....1421 / 2.32
    (TOFRONTGILE 5 LST).......1422 / 2.32
    (TOFRONTLEE2 5 LST).......1516 / 2.17
    (TOFRONTCAB2 5 LST).......1594 / 2.07
    (TOFRONTCAB 5 LST)........1656 / 1.99
    (TOFRONTCAB3 5 LST).......1656 / 1.99
    (METACUTS3 5 LST).........1813 / 1.82
    (MEGACUTS2 5 LST).........1860 / 1.77
    (MEGACUTS1 5 LST).........3297 / 1.00 <slowest>

[Lee Mac]

Some fantastic responses guys - didn't think there would be this much variation...  :kewl:

I'm loving that last entry Gile - very elegant solution, and, evidently very fast too. Good point about the duplicate error in my first version - my excuse would be that the lists I am dealing with in the program this relates to will not contain duplicates... but that is a poor excuse, I know.. 

VovKa, still trying to get my head around yours... I'll come back later when my head has exploded.

And as for the two Alans... it looks like you both went down the same avenues of retrieving the first item and appending it to the rest of the list - a nice solution also.

[gile]

A mapcar statement

Code: [Select]

(defun ToFrontGile3 (ind lst / target result)
  (setq n -1)
  (if (zerop ind)
    lst
    (setq target (nth ind lst)
          result (mapcar
                   (function
                     (lambda (x1 x2)
                       (setq ind (1- ind))
                       (if (< -1 ind) x1 x2)
                     )
                   )
                   lst
                   (cdr lst)
                 )
    )
  )
  (cons target result)
)

[Lee Mac]

Nice code Gile - I wouldn't have thought to use two arguments in the lambda function like that - very clever. 

[alanjt]

Nice code Gile - I wouldn't have thought to use two arguments in the lambda function like that - very clever. 

I know! My first attempt was with mapcar, but it was returning a nil in place of the removed item, so I abandoned it.
Very nice Gile.

[Lee Mac]

Nice code Gile - I wouldn't have thought to use two arguments in the lambda function like that - very clever. 

I know! My first attempt was with mapcar, but it was returning a nil in place of the removed item, so I abandoned it.
Very nice Gile.

Yes, I also thought of mapcar - but I couldn't see how to go "backwards" with it when I reached the item I needed - to stop the nil occurring....

[ArgV]

I don't know if this is right, but something like this?

Code: [Select]

(defun toFrontArgV (num lst / temp)
  (if (member num lst)
    (progn
      (setq lst (vl-remove (setq temp (nth (vl-position num lst) lst)) lst)
    lst (append (list temp) lst)))
    )
    )

or like this:

Code: [Select]

(defun toFrontArgV (num lst / temp)
  (if (member (1+ num) lst)
    (progn
      (setq lst (vl-remove (setq temp (nth (vl-position (1+ num) lst) lst)) lst)
    lst (append (list temp) lst)))
    )
    )