Topic: Check 2 lists for exact same elements but not necessarily same order

[JohnK]

Where I learned recursion is "fairly good" (the book that taught many people to program).

https://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2

[Lee Mac]

Nice algorithm gile 

[kdub_nz]

Ben,
Care to share the circumstances under which you could use this logic. ?

I've had too much trifle during the holiday and I'm partly brain dead.

Regards,

[Ben Clark]

Ben,
Care to share the circumstances under which you could use this logic. ?

I've had too much trifle during the holiday and I'm partly brain dead.

Regards,

I've got a rather large (by my standards) application I'm writing that saves a bunch of data using vlax-ldata. Because the entries in vlax-ldata dictionaries are not ordered, i have another dictionary with a single entry (a list) that saves an intended order for all the entries in the main dictionary where the data is. So the only point of this second dictionary entry was to store an order that the user can manipulate.

Because I have so many functions doing various things. I wanted to run a check upon starting up the first dialog that ensured the entries in the main data dictionary matched up with the entries in this "auxiliary"  ordered list dictionary entry.

Therefore, I needed a function that would check if they had all the same elements but allow for them to be out of order.

[Ben Clark]

"Well now this problem is 'sorted-out'..."

I just can't sit back and watch this amazing pun fall through the cracks without anyone acknowledging it. It's not the way I function.

[gile]

This looks pretty nice. Although I don't understand recursion yet (somewhat new to FP). Anyone know of a ELI5-ish tutorial for recursion? Has Lee written anything? lol

Code - Auto/Visual Lisp: [Select]

1. (defun simlists (l1 l2)
2.   (and
3.     (= (length l1) (length l2))
4.     (or
5.       (equal l1 l2)
6.       (simlists (vl-remove (car l1) l1) (vl-remove (car l1) l2))
7.     )
8.   )
9. )

This code is a quite clear example of tail recursion using.
If first checks for list lengths equality:
  If lengths aren't equal: return nil (end).
  If length are equal, it checks for list equality:
    If lists are equal: return T (end).
    If lists are not equal: recursive call with both lists without all occurences of the first element of one list.

Here's an 'imperative' implementation:

Code - Auto/Visual Lisp: [Select]

1. (defun simlists (l1 l2 / val)
2.   (while
3.     (and
4.       (= (length l1) (length l2))
5.       (not (setq val (equal l1 l2)))
6.     )
7.     (setq l2 (vl-remove (car l1) l2)
8.           l1 (vl-remove (car l1) l1)
9.     )
10.   )
11.   val
12. )

[fools]

I meant to communicate that both lists should have the same length. Basically I want to test for the lists having exactly the same elements, and by that I mean if there are duplicate elements, that each list would have the same quantity of said duplicates.

Stated differently: Start with two identical lists and relax only the constraint of element order. Lists that meet this quality are the only ones that should return a non nil value.

Function vl-remove or vl-remove-if will delete duplicate parts, maybe not meet the requirements of BEN.
(simlists '("a" "a" "b") '("b" "b" "a")) return nil not T, is it?

[gile]

Function vl-remove or vl-remove-if will delete duplicate parts, maybe not meet the requirements of BEN.
(simlists '("a" "a" "b") '("b" "b" "a")) return nil not T, is it?

This is precisely the behavior you describe which is use in the upper functions.

If you trace the upper recursive simlists function:

(simlists '("a" "a" "b") '("b" "b" "a"))
=> (simlists '("b") '("b" "b"))    ; recursive call
=> nil                                       ; expected result, because list lengths are not equal

[fools]

(simlists '("a" "a" "b") '("b" "b" "a"))
=> (simlists '("b") '("b" "b"))    ; recursive call
=> nil                                       ; expected result, because list lengths are not equal

I see. I have learned another trick, thanks.

[Ben Clark]

This looks pretty nice. Although I don't understand recursion yet (somewhat new to FP). Anyone know of a ELI5-ish tutorial for recursion? Has Lee written anything? lol

Code - Auto/Visual Lisp: [Select]

1. (defun simlists (l1 l2)
2.   (and
3.     (= (length l1) (length l2))
4.     (or
5.       (equal l1 l2)
6.       (simlists (vl-remove (car l1) l1) (vl-remove (car l1) l2))
7.     )
8.   )
9. )

This code is a quite clear example of tail recursion using.
If first checks for list lengths equality:
  If lengths aren't equal: return nil (end).
  If length are equal, it checks for list equality:
    If lists are equal: return T (end).
    If lists are not equal: recursive call with both lists without all occurences of the first element of one list.

Here's an 'imperative' implementation:

Code - Auto/Visual Lisp: [Select]

1. (defun simlists (l1 l2 / val)
2.   (while
3.     (and
4.       (= (length l1) (length l2))
5.       (not (setq val (equal l1 l2)))
6.     )
7.     (setq l2 (vl-remove (car l1) l2)
8.           l1 (vl-remove (car l1) l1)
9.     )
10.   )
11.   val
12. )

Thanks so much for your clear explanation. I did some reading up on recursion and it makes total sense now. The joys of functional programming...