Author Topic: Sorting a list according another list  (Read 5432 times)

0 Members and 1 Guest are viewing this topic.

Woabow

  • Newt
  • Posts: 56
Sorting a list according another list
« on: August 30, 2012, 01:19:44 PM »
After searching this forum I often thought I had found the solution, but after all I didn't find how to solve my little problem.

I have two lists, the first looks like:
("ONE" "TWO" THREE" "FOUR" FIVE" "SIX")

The second is a list of lists:
(("item1a"  "item2a"  "item3a"  "item4a"  "item5a"  "item6a")("item1b"  "item2b"  "item3b"  "item4b"  "item5b"  "item6b"))and so on

Now I edit the first list and the result is:
("TWO" "ONE" "THREE" "FOUR" SIX" "FIVE")

And now I want to sort the second list according the first one:
(("item2a"  "item1a"  "item3a"  "item4a"  "item6a"  "item5a")("item2b"  "item1b"  "item3b"  "item4b"  "item6b"  "item5b"))

Can someone please point me in the right direction?


Lee Mac

  • Seagull
  • Posts: 12905
  • London, England
Re: Sorting a list according another list
« Reply #1 on: August 30, 2012, 01:54:59 PM »
Maybe:

Code: [Select]
(defun sort ( l1 l2 )
    (
        (lambda ( l3 )
            (mapcar
                (function
                    (lambda ( a )
                        (mapcar
                            (function
                                (lambda ( b ) (nth b a))
                            )
                            l3
                        )
                    )
                )
                l2
            )
        )               
        (mapcar
            (function
                (lambda ( x )
                    (vl-position x '("ONE" "TWO" "THREE" "FOUR" "FIVE" "SIX"))
                )
            )
            l1
        )
    )
)


Code: [Select]
(sort
   '("TWO" "ONE" "THREE" "FOUR" "SIX" "FIVE")
   '(
        ("item1a"  "item2a"  "item3a"  "item4a"  "item5a"  "item6a")
        ("item1b"  "item2b"  "item3b"  "item4b"  "item5b"  "item6b")
    )
)

Returns:
(
    ("item2a" "item1a" "item3a" "item4a" "item6a" "item5a")
    ("item2b" "item1b" "item3b" "item4b" "item6b" "item5b")
)

PS: Formatting code in your posts...

Woabow

  • Newt
  • Posts: 56
Re: Sorting a list according another list
« Reply #2 on: August 30, 2012, 04:54:52 PM »
Thanks Lee! I just can't believe you can create something like this so fast.

I haven't it working stable yet because in my data the length of the lists seems to differ and also the content of the reference list is not always the same as l1. Right now the code will crash on that but I'll try to find out how to make it handle inconsistent data.

What is the purpose of "function" in your code? Does it make it run faster?

Lee Mac

  • Seagull
  • Posts: 12905
  • London, England
Re: Sorting a list according another list
« Reply #3 on: August 30, 2012, 05:38:54 PM »
Thanks Lee! I just can't believe you can create something like this so fast.

I've had a lot of practice  8-)

I haven't it working stable yet because in my data the length of the lists seems to differ and also the content of the reference list is not always the same as l1. Right now the code will crash on that but I'll try to find out how to make it handle inconsistent data.

You may need to use a different method in that case - my function simply compares the positions of items in the new list 'l1' against those in the 'reference list', and moves the items in each of the sublists of 'l2' to the new positions.

What is the purpose of "function" in your code? Does it make it run faster?

Have a read of this thread  :-)

ribarm

  • Gator
  • Posts: 3225
  • Marko Ribar, architect
Re: Sorting a list according another list
« Reply #4 on: August 30, 2012, 10:25:09 PM »
It works for OP's case, but I want to make it work with commented lines as we don't know number of sublists in list2...

Code - Auto/Visual Lisp: [Select]
  1. ;(defun free ( lst / x )
  2. ;  (if (car lst) (progn (setq x (car lst)) (free (cdr lst)) (eval x)))
  3. ;)
  4. (defun sort ( l1 l2 l1m / l2n l2nss l2ns l2n+1 argss args l3 l3m l2m )
  5.   (setq l2n (length l2))
  6.   (while (<= 0 (setq l2n (1- l2n)))
  7.     (set (read (strcat "l2" (itoa l2n))) (nth l2n l2))
  8.     (setq l2nss (cons (strcat "l2" (itoa l2n)) l2nss))
  9.   )
  10.   (foreach l2ne l2nss
  11.     (setq l2ns (cons (read l2ne) l2ns))
  12.   )
  13.   (setq l2ns (reverse l2ns))
  14.   (setq l2n+1 (1+ (length l2)))
  15.   (while (<= 0 (setq l2n+1 (1- l2n+1)))
  16.     (setq argss (cons (strcat "arg" (itoa l2n+1)) argss))
  17.   )
  18.   (foreach arg argss
  19.     (setq args (cons (read arg) args))
  20.   )
  21.   (setq args (reverse args))
  22. ;  (setq l3 (mapcar '(lambda (args) (list (car args) (cdr args))) l1 (free l2ns)))
  23.   (setq l3 (mapcar '(lambda ( a b c ) (list a (list b c))) l1 l20 l21))
  24.   (foreach l1me l1m
  25.     (setq l3m (cons (assoc l1me l3) l3m))
  26.   )
  27.   (setq l3m (reverse l3m))
  28.   (setq l2n -1)
  29.   (foreach l2e l2
  30.     (set (read (strcat "l2m" (itoa (setq l2n (1+ l2n))))) (mapcar '(lambda ( a ) (nth l2n (cadr a))) l3m))
  31.   )
  32.   (setq l2n (length l2))
  33.   (foreach l2e l2
  34.     (setq l2m (cons (eval (read (strcat "l2m" (itoa (setq l2n (1- l2n)))))) l2m))
  35.   )
  36.   (setq l2n (length l2))
  37.   (foreach l2e l2
  38.     (set (read (strcat "l2" (itoa (setq l2n (1- l2n))))) nil)
  39.     (set (read (strcat "l2m" (itoa l2n))) nil)
  40.   )
  41.   l2m
  42. )
  43.  

Code: [Select]
Command: !ll1m
("two" "three" "one")

Command: !ll1
("one" "two" "three")

Command: !ll2
(("a1" "a2" "a3") ("b1" "b2" "b3"))

Command: (sort ll1 ll2 ll1m)
(("a2" "a3" "a1") ("b2" "b3" "b1"))

M.R.
Marko Ribar, d.i.a. (graduated engineer of architecture)

:)

M.R. on Youtube

ElpanovEvgeniy

  • Water Moccasin
  • Posts: 1569
  • Moscow (Russia)
Re: Sorting a list according another list
« Reply #5 on: August 31, 2012, 03:53:12 AM »
recursion way:
Code - Auto/Visual Lisp: [Select]
  1. (defun sort (a b c)
  2.     (defun f (c d)
  3.       (apply (function mapcar)
  4.              (cons (function list) (mapcar (function (lambda (a) (cdr (assoc a d)))) c))
  5.       )
  6.     )
  7.     (f c (apply (function mapcar) (cons (function list) (cons a b))))
  8.   )
Code - Auto/Visual Lisp: [Select]
  1. (sort '("one" "two" "three") '(("a1" "a2" "a3") ("b1" "b2" "b3")) '("two" "three" "one"))
« Last Edit: August 31, 2012, 06:01:51 AM by ElpanovEvgeniy »

ElpanovEvgeniy

  • Water Moccasin
  • Posts: 1569
  • Moscow (Russia)
Re: Sorting a list according another list
« Reply #6 on: August 31, 2012, 04:26:53 AM »
without assoc:

Code - Auto/Visual Lisp: [Select]
  1. (defun sort (a b c)
  2.     (defun f (a b c)
  3.       (cond ((= a (car c)) (mapcar (function car) b))
  4.             ((f a (mapcar (function cdr) b) (cdr c)))
  5.       )
  6.     )
  7.            (cons (function list) (mapcar (function (lambda (c) (f c b a))) c))
  8.     )
  9.   )
  10.  
  11. (sort '("one" "two" "three") '(("a1" "a2" "a3") ("b1" "b2" "b3")) '("two" "three" "one"))
  12.  

Woabow

  • Newt
  • Posts: 56
Re: Sorting a list according another list
« Reply #7 on: August 31, 2012, 04:37:56 AM »
Amazing code.

What if the reference list can be

Code: [Select]
("one" "two" "three" "four")
And the sortlist

Code: [Select]
("two" "one" "four")
?

And am I right that
Code: [Select]
(f c (setq d (apply (function mapcar) (cons (function list) (cons a b))))
Can also be
Code: [Select]
(f c (apply (function mapcar) (cons (function list) (cons a b))))
in the recursive one? (I cannot find the recursion though, must be me)



ribarm

  • Gator
  • Posts: 3225
  • Marko Ribar, architect
Re: Sorting a list according another list
« Reply #8 on: August 31, 2012, 05:09:46 AM »
I did what I wanted...

Code - Auto/Visual Lisp: [Select]
  1. (defun sort ( l1 l2 l1m / l2n l2nss l2ns l2n+1 argss args l3 l3m l2m )
  2.   (setq l2n (length l2))
  3.   (while (<= 0 (setq l2n (1- l2n)))
  4.     (set (read (strcat "l2" (itoa l2n))) (nth l2n l2))
  5.     (setq l2nss (cons (strcat "l2" (itoa l2n)) l2nss))
  6.   )
  7.   (foreach l2ne l2nss
  8.     (setq l2ns (cons (read l2ne) l2ns))
  9.   )
  10.   (setq l2ns (reverse l2ns))
  11.   (setq l2n+1 (1+ (length l2)))
  12.   (while (<= 0 (setq l2n+1 (1- l2n+1)))
  13.     (setq argss (cons (strcat "ar" (itoa l2n+1)) argss))
  14.   )
  15.   (foreach arg argss
  16.     (setq args (cons (read arg) args))
  17.   )
  18.   (setq args (reverse args))
  19.   (setq l3 (eval (append (list 'mapcar) (list (list 'function (list 'lambda args (list 'list (car args) (cons 'list (cdr args)))))) (cons 'l1 l2ns))))
  20.   (foreach l1me l1m
  21.     (setq l3m (cons (assoc l1me l3) l3m))
  22.   )
  23.   (setq l3m (reverse l3m))
  24.   (setq l2n -1)
  25.   (foreach l2e l2
  26.     (set (read (strcat "l2m" (itoa (setq l2n (1+ l2n))))) (mapcar '(lambda ( a ) (nth l2n (cadr a))) l3m))
  27.   )
  28.   (setq l2n (length l2))
  29.   (foreach l2e l2
  30.     (setq l2m (cons (eval (read (strcat "l2m" (itoa (setq l2n (1- l2n)))))) l2m))
  31.   )
  32.   (setq l2n (length l2))
  33.   (foreach l2e l2
  34.     (set (read (strcat "l2" (itoa (setq l2n (1- l2n))))) nil)
  35.     (set (read (strcat "l2m" (itoa l2n))) nil)
  36.   )
  37.   l2m
  38. )
  39.  

Code: [Select]
Command: (sort '("one" "two" "three")
(_> '(
('(_> ("a1" "a2" "a3")
('(_> ("b1" "b2" "b3")
('(_> ("c1" "c2" "c3")
('(_> ("d1" "d2" "d3")
('(_> )
(_> '("three" "one" "two")
(_> )
(("a3" "a1" "a2") ("b3" "b1" "b2") ("c3" "c1" "c2") ("d3" "d1" "d2"))

Regards, M.R.
Marko Ribar, d.i.a. (graduated engineer of architecture)

:)

M.R. on Youtube

ElpanovEvgeniy

  • Water Moccasin
  • Posts: 1569
  • Moscow (Russia)
Re: Sorting a list according another list
« Reply #9 on: August 31, 2012, 06:00:54 AM »
Amazing code.

What if the reference list can be

Code: [Select]
("one" "two" "three" "four")
And the sortlist

Code: [Select]
("two" "one" "four")
?

And am I right that
Code: [Select]
(f c (setq d (apply (function mapcar) (cons (function list) (cons a b))))
Can also be
Code: [Select]
(f c (apply (function mapcar) (cons (function list) (cons a b))))
in the recursive one? (I cannot find the recursion though, must be me)

Yes!

Woabow

  • Newt
  • Posts: 56
Re: Sorting a list according another list
« Reply #10 on: August 31, 2012, 11:02:08 AM »
Thank you all, it's all working now. I would be still struggling without your help. You are awesome programmers with unique talents.

Have a good weekend.


irneb

  • Water Moccasin
  • Posts: 1794
  • ACad R9-2016, Revit Arch 6-2016
Re: Sorting a list according another list
« Reply #11 on: September 01, 2012, 04:33:33 AM »
Just for fun: Nested iterative using nth & vl-position:
Code - Auto/Visual Lisp: [Select]
  1. (defun Rearrange (base data order / index result)
  2.   (foreach item order
  3.     (if (setq index (vl-position item base))
  4.       (setq result (cons (nth index data) result))))
  5.   (reverse result))
  6.  
  7. (defun Rearrange-Nested (base datalist order / )
  8.   (mapcar '(lambda (data) (Rearrange base data order)) datalist))
Seems to work:
Code: [Select]
_$ (Rearrange-Nested '("One" "Two" "Three") '(("a1" "a2" "a3") ("b1" "b2" "b3")) '("Three" "One" "Two"))
(("a3" "a1" "a2") ("b3" "b1" "b2"))
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: Sorting a list according another list
« Reply #12 on: September 01, 2012, 10:06:47 AM »
recursion way:
Code - Auto/Visual Lisp: [Select]
  1. (defun sort (a b c)
  2.     (defun f (c d)
  3.       (apply (function mapcar)
  4.              (cons (function list) (mapcar (function (lambda (a) (cdr (assoc a d)))) c))
  5.       )
  6.     )
  7.     (f c (apply (function mapcar) (cons (function list) (cons a b))))
  8.   )
Code - Auto/Visual Lisp: [Select]
  1. (sort '("one" "two" "three") '(("a1" "a2" "a3") ("b1" "b2" "b3")) '("two" "three" "one"))

Fantastic solution Evgeniy (as always ;) )

Two comments if I may:

Since the in-built AutoLISP functions are already compiled and optimised, there is no performance benefit to using the function function over the quote when the code is compiled to a vlx/fas, and since the quote is perhaps more readable, I would be inclined to reserve function for lambda functions.

Minor suggestion for extra concision:

Code - Auto/Visual Lisp: [Select]

Could become:

Code - Auto/Visual Lisp: [Select]
  1. (vl-list* 'list a b)

Finally, here is my simple variation:

Code - Auto/Visual Lisp: [Select]
  1. (defun lm:sort ( a b c / n l )
  2.     (foreach x (reverse c)
  3.         (if (setq n (vl-position x a))
  4.             (setq l (cons n l))
  5.         )
  6.     )
  7.     (mapcar (function (lambda ( x ) (mapcar (function (lambda ( y ) (nth y x))) l))) b)
  8. )

Lee Mac

  • Seagull
  • Posts: 12905
  • London, England
Re: Sorting a list according another list
« Reply #13 on: September 01, 2012, 11:10:56 AM »
Here is a quick performance test:


Functions:
Code - Auto/Visual Lisp: [Select]
  1. (defun ee:sort1 ( a b c )
  2.     (defun f ( c d )
  3.         (apply (function mapcar)
  4.             (cons (function list)
  5.                 (mapcar (function (lambda ( a ) (cdr (assoc a d)))) c)
  6.             )
  7.         )
  8.     )
  9.     (f c (apply (function mapcar) (cons (function list) (cons a b))))
  10. )
  11.  
  12. (defun ee:sort2 ( a b c )
  13.     (defun f ( a b c )
  14.         (cond
  15.             ((= a (car c)) (mapcar (function car) b))
  16.             ((f a (mapcar (function cdr) b) (cdr c)))
  17.         )
  18.     )
  19.         (cons (function list) (mapcar (function (lambda ( c ) (f c b a))) c))
  20.     )
  21. )
  22.  
  23. (defun rearrange ( base data order / index result )
  24.     (foreach item order
  25.         (if (setq index (vl-position item base))
  26.             (setq result (cons (nth index data) result))
  27.         )
  28.     )
  29.     (reverse result)
  30. )    
  31. (defun ib:rearrange-nested ( base datalist order )
  32.     (mapcar '(lambda (data) (rearrange base data order)) datalist)
  33. )
  34.  
  35. (defun lm:sort ( a b c / n l )
  36.     (foreach x (reverse c)
  37.         (if (setq n (vl-position x a))
  38.             (setq l (cons n l))
  39.         )
  40.     )
  41.     (mapcar (function (lambda ( x ) (mapcar (function (lambda ( y ) (nth y x))) l))) b)
  42. )

List Construction:
Code - Auto/Visual Lisp: [Select]
  1. _$ (setq i 0)
  2. 0
  3. _$ (repeat 20 (setq a (cons (setq i (1+ i)) a)))
  4. (20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1)
  5. _$ (setq a (reverse a))
  6. (1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20)
  7. _$ (repeat 20 (setq b (cons a b)))
  8. ((1 2 3 4 5 6 7 8 9 10 ... 15 16 17 18 19 20) ... (1 2 3 4 5 6 7 8 9 10 ... 15 16 17 18 19 20))
  9. _$ (setq c (LM:shuffle a))
  10. (20 7 11 13 1 5 12 15 2 16 8 17 18 4 10 6 14 3 19 9)

[ LM:shuffle function from here ]


Results:

List Length: 10x10 [100 items]
Code - Auto/Visual Lisp: [Select]
  1. Benchmarking .................Elapsed milliseconds / relative speed for 16384 iteration(s):
  2.  
  3.     (EE:SORT1 A B C)................1669 / 5.06 <fastest>
  4.     (LM:SORT A B C).................4290 / 1.97
  5.     (IB:REARRANGE-NESTED A B C).....7238 / 1.17
  6.     (EE:SORT2 A B C)................8440 / 1.00 <slowest>

List Length: 20x20 [400 items]
Code - Auto/Visual Lisp: [Select]
  1. Benchmarking ................Elapsed milliseconds / relative speed for 8192 iteration(s):
  2.  
  3.     (EE:SORT1 A B C).................1092 / 12.53 <fastest>
  4.     (LM:SORT A B C)..................2980 / 4.59
  5.     (IB:REARRANGE-NESTED A B C)......6100 / 2.24
  6.     (EE:SORT2 A B C)................13681 / 1.00 <slowest>

List Length: 50x50 [2500 items]
Code - Auto/Visual Lisp: [Select]
  1. Benchmarking ..............Elapsed milliseconds / relative speed for 2048 iteration(s):
  2.  
  3.     (EE:SORT1 A B C).................1014 / 31.49 <fastest>
  4.     (LM:SORT A B C)..................3822 / 8.36
  5.     (IB:REARRANGE-NESTED A B C)......9750 / 3.28
  6.     (EE:SORT2 A B C)................31933 / 1.00 <slowest>


Hats off to Evgeniy! :kewl:

ElpanovEvgeniy

  • Water Moccasin
  • Posts: 1569
  • Moscow (Russia)
Re: Sorting a list according another list
« Reply #14 on: September 01, 2012, 01:55:17 PM »
... the first and last ...

So I'm in the middle!  :lol: