List Symmetric Difference Functions

See also List Union, List Intersection & List Difference

Symmetric Difference of Two Lists

Function Syntax (LM:ListSymDifference <l1> <l2>)
Current Version 1.0
Arguments
Symbol Type Description
l1,l2 List Lists for which to return the Symmetric Difference
Returns
Type Description
List List of items appearing exclusively in each list and not in their intersection

Program Description

This subfunction will return a list expressing the symmetric difference of two lists, that is, a list of items appearing exclusively in each list and not in their intersection. In set notation, this may be expressed as (A∖B)∪(B∖A).

SymDifference.png

Recursive Version

Select all
;;--------------=={ List Symmetric Difference }==-------------;;
;;                                                            ;;
;;  Returns items appearing exclusively in each list and not  ;;
;;  in their intersection.                                    ;;
;;------------------------------------------------------------;;
;;  Author: Lee Mac, Copyright © 2011 - www.lee-mac.com       ;;
;;------------------------------------------------------------;;
;;  Arguments:                                                ;;
;;  l1,l2 - lists for which to return symmetric difference    ;;
;;------------------------------------------------------------;;
;;  Returns:  List of items in the set (l1\l2)U(l2\l1)        ;;
;;------------------------------------------------------------;;

(defun LM:ListSymDifference ( l1 l2 / sub )
  (defun sub ( a b )
    (if a
      (if (member (car a) b)
        (sub (cdr a) b)
        (cons (car a) (sub (cdr a) b))
      )
    )
  )
  (append (sub l1 l2) (sub l2 l1))
)

Iterative Version

Select all
;;--------------=={ List Symmetric Difference }==-------------;;
;;                                                            ;;
;;  Returns items appearing exclusively in each list and not  ;;
;;  in their intersection.                                    ;;
;;------------------------------------------------------------;;
;;  Author: Lee Mac, Copyright © 2011 - www.lee-mac.com       ;;
;;------------------------------------------------------------;;
;;  Arguments:                                                ;;
;;  l1,l2 - lists for which to return symmetric difference    ;;
;;------------------------------------------------------------;;
;;  Returns:  List of items in the set (l1\l2)U(l2\l1)        ;;
;;------------------------------------------------------------;;

(defun LM:ListSymDifference ( l1 l2 )
  (append
    (vl-remove-if '(lambda ( x ) (member x l2)) l1)
    (vl-remove-if '(lambda ( x ) (member x l1)) l2)
  )
)

Versions Derived from Set Operations

Requires List Union, List Difference & List Intersection subfunctions

(defun LM:ListSymDifference ( l1 l2 )
  (LM:ListDifference (LM:ListUnion l1 l2) (LM:ListIntersection l1 l2))
)
(defun LM:ListSymDifference ( l1 l2 )
  (LM:ListUnion (LM:ListDifference l1 l2) (LM:ListDifference l2 l1))
)

Example Function Call

_$ (LM:ListSymDifference '(1 2 3 4 5 6) '(1 2 3 5 8 13))
(4 6 8 13)

Symmetric Difference of a Set of Lists

Function Syntax (LM:ListsSymDifference <l>)
Current Version 1.0
Arguments
Symbol Type Description
l List List of lists for which to return the Symmetric Difference
Returns
Type Description
List List of items appearing exclusively in each list and not in the intersection of any pair of lists

Program Description

This subfunction will return a list expressing the symmetric difference of a set of lists, that is, a list of items appearing exclusively in each list and not in the intersection of any two lists. In set notation, this may be expressed as (S1∖(S2∪S3∪...∪SN))∪(S2∖(S1∪S3∪...∪SN))∪...∪(SN∖(S1∪S2∪...∪SN-1)).

SymDifferenceM.png

Recursive Version

Select all
;;--------------=={ Lists Symmetric Difference }==------------;;
;;                                                            ;;
;;  Returns items appearing exclusively in each list and not  ;;
;;  in the intersection of any pair of lists.                 ;;
;;------------------------------------------------------------;;
;;  Author: Lee Mac, Copyright © 2011 - www.lee-mac.com       ;;
;;------------------------------------------------------------;;
;;  Arguments:                                                ;;
;;  l - list of lists for which to return the sym difference  ;;
;;------------------------------------------------------------;;
;;  Returns: List of (l1\(l2Ul3U..UlN)U(l2\(l1Ul3..UlN)U...   ;;
;;------------------------------------------------------------;;

(defun LM:ListsSymDifference ( l / sub )
  (defun sub ( a b )
    (if a
      (if (vl-some '(lambda ( x ) (member (car a) x)) b)
        (sub (cdr a) b)
        (cons (car a) (sub (cdr a) b))
      )
    )
  )
  (apply 'append
    (mapcar
     '(lambda ( a / x )
        (setq x (sub a (cdr l)) l (append (cdr l) (list a))) x
      )
      l
    )
  )
)

Iterative Version

Select all
;;--------------=={ Lists Symmetric Difference }==------------;;
;;                                                            ;;
;;  Returns items appearing exclusively in each list and not  ;;
;;  in the intersection of any pair of lists.                 ;;
;;------------------------------------------------------------;;
;;  Author: Lee Mac, Copyright © 2011 - www.lee-mac.com       ;;
;;------------------------------------------------------------;;
;;  Arguments:                                                ;;
;;  l - list of lists for which to return the sym difference  ;;
;;------------------------------------------------------------;;
;;  Returns: List of (l1\(l2Ul3U..UlN)U(l2\(l1Ul3..UlN)U...   ;;
;;------------------------------------------------------------;;

(defun LM:ListsSymDifference ( l )
  (apply 'append
    (mapcar
     '(lambda ( a / x )
        (setq x
          (vl-remove-if
           '(lambda ( b ) (vl-some '(lambda ( c ) (member b c)) (cdr l))) a
          )
        )
        (setq l (append (cdr l) (list a))) x
      )
      l
    )
  )
)

Version Derived from Set Operations

Requires List Union, Lists Union, List Difference & List Intersection subfunctions

Select all
(defun LM:ListsSymDifference ( l )
  (LM:ListDifference (LM:ListsUnion l)
    (LM:ListsUnion
      (mapcar
       '(lambda ( a )
          (apply 'append
            (mapcar '(lambda ( b ) (LM:ListIntersection a b)) (setq l (cdr l)))
          )
        )
        l
      )
    )
  )
)

Example Function Call

_$ (LM:ListsSymDifference '((1 2 3 4 5 6) (1 2 3 5 8 13) (1 3 5 7 9 11)))
(4 6 8 13 7 9 11)

See also List Union, List Intersection & List Difference

textsize

increase · reset · decrease

Designed & Created by Lee Mac © 2010