# nth-replace (mergesort's achilles heel)

## Recommended Posts

I've completed MergeSort algorithm implementation in Autolisp based on Ellis Dee's vb6 version here: http://www.vbforums.com/showpost.php?p=2909257&postcount=12

The problem is that I need to replace nth atom in the lisp array, and the only way I can currently accomplish this, is by iterating the entire list. This takes, what would be a spectacular sorting algorithm, and destroys it's efficiency by iterating the list nth(log) times. I'm going to try not to muddy the water too much, but here is my nth-replace function based on Michels nth-remove function...

```  (defun nth-replace (n_atom f_list f_n / ) ;replaced the nth element of a list
;n_atom is new atom
;f_list is list to be operated on
;f_n is the index that will be replaced
(if (and (numberp f_n) (listp f_list))
(if (and (>= f_n 0) (< f_n (length f_list)) n_atom)
(progn
(repeat f_n
(setq f_list (append (cdr f_list) (list (car f_list))))
)
(setq f_list (append (cdr f_list) (list n_atom)))
(repeat (- (length f_list) f_n 1)
(setq f_list (append (cdr f_list) (list (car f_list))))
)
)
)
)
f_list
);defun
```

I'm not completely new to autolisp, but I'm hoping there's a fundamental function I'm overlooking that can either replace an atom at a certain level, or can return a list up to a certain atom (nth instance), and then I can append my change, and then the latter half of the list.

##### Share on other sites

Consider this example:

```(defun replace3 ( alist position newitem / i )
(setq i -1)
(mapcar '(lambda ( x ) (if (= position (setq i (1+ i))) newitem x)) alist)
)
```

** Edit - Sample from VLIDE Console:

```REPLACE3
_\$ (replace3 '(1 2 3 3 2 1) 3 4)
(1 2 3 4 2 1)
_\$
```

##### Share on other sites

First thought..

```(defun nth-rep (x l n / i)
(setq i -1)
(mapcar '(lambda (a) (cond ((= (setq i (1+ i)) n) x) (a))) l)
)
```

EDIT: Oops... too late

##### Share on other sites

quickie, but should work...

```(defun _nthReplace (item index lst)
(if (and lst (> index 0))
(cons (car lst) (_nthReplace item (1- index) (cddr lst)))
(cons item (cdr lst))
)
)```

##### Share on other sites

Renderman / Stefan BMR

Spectacular Gentlemen. Freaking spectacular.

If I could express my elation, I would have to type that about 5000 times.

It makes so much sense, I'm embarassed. Optimized without a recreated var.

So after testing both the IF and the COND method, the IF won by 3 seconds when processing 1000 random numbers. Keeping in mind that either were lightyears from what I had, which I stopped processing after a couple of hours.

IF Results:

```Time:
15.19 seconds
; 10 forms loaded from #<editor ".../mergesort2.LSP">
_1_\$
```

COND Results:

```Time:
18.02 seconds
; 10 forms loaded from #<editor ".../mergesort2.LSP">
_1_\$
```

Posting MergeSort in a seperate thread.

##### Share on other sites
Renderman / Stefan BMR

Spectacular Gentlemen. Freaking spectacular.

If I could express my elation, I would have to type that about 5000 times.

Lee deserves credit for the code that I posted above, as he presented that offering as an enhanced version of my own (earlier in the same thread, linked above). LoL

... I am glad it helped you, though.

##### Share on other sites

Just a question I have after reading this thread. In AutoLisp why wouldn't subst work?

`(subst ITEM (nth INDEX LST) LST)`

##### Share on other sites

Try

`(subst 1 0 '(0 1 0 2 0))`

subst

Searches a list for an old item and returns a copy of the list with a new item substituted in place of every occurrence of the old item

##### Share on other sites

Stefan is correct - Lee also makes this point to me, in the linked thread above.

##### Share on other sites

i thought the point was the replace the nth item, not every matching item.

##### Share on other sites
i thought the point was the replace the nth item, not every matching item.

*Touches finger to nose*

... That's why Stefan (here), and Lee (in the linked thread) advise against using SUBST.

##### Share on other sites
*Touches finger to nose*

... That's why Stefan (here), and Lee (in the linked thread) advise against using SUBST.

Oops, his and liberty's post as one.

##### Share on other sites

OK - I see the point in not using subst.

I would like to tinker around with this myself a bit but don't have an AutoLisp interpreter handy at the moment and my fingers are really itching!

Could someone copy the following code and tell me what is returned? Thanks!

```(setq mylist '(a b c d e f))
(setq flist (cons (nth 3 mylist) nil))
```

##### Share on other sites

I would like to tinker around with this myself a bit but don't have an AutoLisp interpreter handy at the moment and my fingers are really itching!

Could someone copy the following code and tell me what is returned?

##### Share on other sites

ok - no answer is also an answer...

##### Share on other sites
ok - no answer is also an answer...

I read your request; the "Implied Facepalm" image IS what was returned on my end...

Okay, I'll stop... Since you were a good sport about it, here you go :

```_\$ (setq mylist '(a b c d e f))
(A B C D E F)
_\$ (setq flist (cons (nth 3 mylist) nil))
(D)
_\$
```

##### Share on other sites

Thanks for the reply, RenderMan. I really have to complain a bit now that I have no access to an AutoCAD command line. Being able to write code the last 13 years and then having no AutoCAD is like going cold-turkey!

I was assuming that (D) was going to be returned but wasn't 100% sure. (About 2% was thinking (A B C D)) I've been reading about cons cells lately, and wanred to practice...

##### Share on other sites
Thanks for the reply, RenderMan.

You're welcome.

I really have to complain a bit now that I have no access to an AutoCAD command line. Being able to write code the last 13 years and then having no AutoCAD is like going cold-turkey!

I have nowhere near your experience, but if things do not improve at my place of work in the very immediate future, I too may be able to relate to your dilemma.

##### Share on other sites

Thanks for the nod Renderman, appreciated

FYI, here is the related function on my site:

http://lee-mac.com/substn.html

## Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.
Note: Your post will require moderator approval before it will be visible.

Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

Only 75 emoji are allowed.