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

[Ben Clark]

It's late. I'm trying to perfect a task that's at the heart of what lisp does.

The task is to check two lists for whether or not they have the exact same elements but not necessarily in the same order.

It definitely sounds like something someone would have written before, but I haven't seen anyone's version yet.

I made a stab at it, and it works, but to me it's not very pretty. It could probably be done in a few lines with recursion or something, a level of lisp I have not dabbled in yet.


Here goes:

Code: [Select]

; Check if 2 lists have the exact same elements, even if out of order
(defun simlists (list1 list2 / i result len)
  (setq
i 0
result T
len (length list1)
)
(if (= len (length list2))
(while (and result (< i end))
  (if (not (member (nth i list1) list2))
(setq result nil)
)
(setq i (1+ i))
)
(setq result nil)
)
result
)
Any thoughts at a better way?

[gile]

Hi,

This sohuld work the same:

Code - Auto/Visual Lisp: [Select]

1. (defun simlists (l1 l2)
2.   (and
3.     (= (length l1) (length l2))
4.     (null
5.       (while (and l1 (member (car l1) l2))
6.         (setq l1 (cdr l1))
7.       )
8.     )
9.   )
10. )

[Ben Clark]

Wow, Gile. That is super clean. I knew someone with more experience could write that in a more succinct way.

Thanks.

[Lee Mac]

The task is to check two lists for whether or not they have the exact same elements but not necessarily in the same order.

Code: [Select]

_$ (simlists '(1 2 2) '(1 2 4))
T

[Lee Mac]

Here's another way:

Code: [Select]

(defun simlists ( l1 l2 )
    (not
        (or (vl-remove-if '(lambda ( x ) (member x l2)) l1)
            (vl-remove-if '(lambda ( x ) (member x l1)) l2)
        )
    )
)
Which may also be written:

Code: [Select]

(defun simlists ( l1 l2 / f )
    (defun f ( a b ) (cond ((null a)) ((member (car a) b) (f (cdr a) b))))
    (and (f l1 l2) (f l2 l1))
)

Code: [Select]

(defun simlists ( l1 l2 / f )
    (defun f ( a b ) (null (vl-remove-if '(lambda ( x ) (member x b)) a)))
    (and (f l1 l2) (f l2 l1))
)

Code: [Select]

(defun simlists ( l1 l2 )
    (vl-every '(lambda ( a b ) (null (vl-remove-if '(lambda ( x ) (member x b)) a))) (list l1 l2) (list l2 l1))
)

[Grrr1337]

Using from the sudoku thread the validrowcolp subfunction - it had a similar purpose:

Code: [Select]

(defun simlists ( lst1 lst2 )
  (equal (vl-sort lst1 '<) (vl-sort lst2 '<))
)
 

[Lee Mac]

Using from the sudoku thread the validrowcolp subfunction - it had a similar purpose:

Code: [Select]

(defun simlists ( lst1 lst2 )
  (equal (vl-sort lst1 '<) (vl-sort lst2 '<))
)
 

The use of vl-sort will unfortunately yield inconsistent behaviour, e.g.:

Code: [Select]

_$ (simlists '("a" "a" "b" "c") '("a" "b" "c"))
nil
_$ (simlists '(1 1 2 3) '(1 2 3))
T
From the statement given by the OP, I would say the function should return T for both lists, though I may have misunderstood the requirements.

[Grrr1337]

The use of vl-sort will unfortunately yield inconsistent behaviour, e.g.:

Code: [Select]

_$ (simlists '("a" "a" "b" "c") '("a" "b" "c"))
nil
_$ (simlists '(1 1 2 3) '(1 2 3))
T

Aah, right - I've forgot that vl-sort trims out the duplicates.
Perhaps this would be a quick fix (without using vl-sort-i):

Code: [Select]

(defun shifted-p ( lst1 lst2 / f)
  (setq f (lambda (L) (vl-sort (mapcar 'vl-prin1-to-string L) '<)))
  (equal (f lst1) (f lst2))
)

Code: [Select]

_$ (shifted-p '(5 3 4 1) '(1 5 4 3)) -> T
_$ (shifted-p '(5 3 4 1) '(1 1 5 4 3)) -> nil


From the statement given by the OP, I would say the function should return T for both lists, though I may have misunderstood the requirements.

Yeah, its not mentioned if both lists should have the same length to consider the duplicate items, so I renamed that subfoo accordingly.

[Ben Clark]

Thanks to all for your feedback.

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.



It appears the shifted-p function that Grrr1337 posted meets that criteria. I'll have to study it to determine exactly what it's doing. Some questions:

    1. What is the advantage of using lambda but naming it with setq? Is this the same as using defun and localizing the symbol? just a cleaner way?
    2. Why us vl-prin1-to-string here? I guess it's a way to convert all elements to the same data type and sort them? but how are strings sorted? by ascii values?

Lee, your functions taught me a lot also, as usual. They fulfill a slightly different criteria than I needed (I should have communicated clearer).

[gile]

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. )

[Grrr1337]

It appears the shifted-p function that Grrr1337 posted meets that criteria.

Well now this problem is 'sorted-out', everyone could post their further attempts.
Theres might be another question for dealing with nested lists(which would involve recursion):

Code: [Select]

(foo '((1 2 3)((3 2 1)) 2) '((3 1 2) 2 (1 3 2)) )

    1. What is the advantage of using lambda but naming it with setq? Is this the same as using defun and localizing the symbol? just a cleaner way?

lambda's purpose is to define an annonymous function on-the-fly. That said you have two options:

• Provide arguments and evaluate it instantly
• Make it named function and evaluate it later

So in that example its the same as defun, but I'm used to define like that functions on-the-fly, that are going to be used only inside the main code (aswell localising them in there).
Same can be done with defun ofcourse, I'm just writing under my own(made-up) rules.

    2. Why us vl-prin1-to-string here? I guess it's a way to convert all elements to the same data type and sort them? but how are strings sorted? by ascii values?

Yes, since Lee pointed out the vl-sort issue (that it removes duplicate elements after sorting - more specifically: numbers),
vl-prin1-to-string is required to just print them as strings and the vl-sort then sorts by ascii values.
ofcourse acad_strlsort is also an option.

[MP]

(Test '(1 1 2) '(1 2 2))

(Test '((1 2)(1 2)(2 1)) '((1 2)(2 1)(2 1)))

[JohnK]

I found these (quick search on my files). Recursion will work better if there is nested lists.

Code - Auto/Visual Lisp: [Select]

1. (defun in-both ( ls1 ls2 )
2.   ;; in-both
3.   ;;
4.   ;; check two lists for duplicate entries. This will stop
5.   ;; on first occurance
6.   ;;
7.   ;; By: Nesterovsky, Vladimir
8.   ;; Adjusted by: John K
9.   ;;         7/10/2007 8:24:17 AM  
10.   ;;   - There was a small mistake with the final
11.   ;;     process in the cond statment.
12.   ;;   - I have also modified the proced to return
13.   ;;     the item found instead of true; this is because
14.   ;;     a logical stament can work with objects as well
15.   ;;     as a `T'.
16.   ;;
17.   ;; EX:
18.   ;;    (in-both
19.   ;;      '("LEFTSIDE" 8.0 12.0 "ONE" 24.0 8.0 96.0)
20.   ;;      '("RIGHTSIDE" 7.0 48.0 "ONE" 120.0)
21.   ;;      )
22.   ;;  > "ONE"
23.   ;;
24.   (cond
25.     ((null ls1) nil)
26.     ((member (car ls1) ls2) (car ls1))
27.     (T (in-both (cdr ls1) ls2))) )

Code - Auto/Visual Lisp: [Select]

1. (defun rem-dups ( item lst )
2.   ;; remove duplicates from a list the ``natural'' way.
3.   (cond
4.     ((null lst) nil)
5.     ;; are we done yet?
6.     ((null item) nil)
7.     ;; Dont give me anything to work with huh?
8.     ((eq (car lst) item)
9.     ;; Da boss sayz you gotta go.
10.      (rem-dups item (cdr lst)))
11.     (T (cons (car lst)
12.     ;; okay, yuz alright.
13.              (rem-dups item (cdr lst))))) )

I also found this snip of a conversation I had with MP about some trickery I was employing at one time with lambda/set/defun (I was probably being obtuse or producing obscure code for little reason).

Two things --

(set 'a (lambda (n) (if (>= n 5) n (a (1+ n)))))

Isn't any different than --

(setq a (lambda (n) (if (>= n 5) n (a (1+ n)))))

Also, the purpose of lambda is to create an anonymous function (read unnamed) on the fly; usually right where you need it, and abandoned once you're done with it. Using lambda like the above, while interesting, is really abusing its intent (IMO) because it now is performing the same role as defun (a named function) --

(defun a (n) (if (>= n 5) n (a (1+ n))))

Finally, try this --

(setq a '((n) (if (>= n 5) n (a (1+ n)))))

Now --

(a 1)

Hint -- redefine functions on the fly.



Thanks Se7en, this was a fun conversation!

[Grrr1337]

I also found this snip of a conversation I had with MP about some trickery I was employing at one time with lambda/set/defun (I was probably being obtuse or producing obscure code for little reason).

Two things --

...

I remember checking that out, when I was learning about lambda !
I was about to say that recursion will fail when defining with: (setq sym (lambda ..))
But now I'm testing again and seems to work:

Code: [Select]

(setq f (lambda (L) (if L (progn (print (strcase (car L))) (f (cdr L))))))
(f '("a" "b" "c"))

((setq f (lambda (L) (if L (progn (print (strcase (car L))) (f (cdr L)))))) '("a" "b" "c"))

No idea what happened back then in my code.. 

Sorry for the offtopic.

[Ben Clark]

Also, the purpose of lambda is to create an anonymous function (read unnamed) on the fly; usually right where you need it, and abandoned once you're done with it. Using lambda like the above, while interesting, is really abusing its intent (IMO) because it now is performing the same role as defun (a named function) --

I was wondering about that! I seems it doesn't hurt anything to use it that way though.



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. )