SetAlgorithms

Overview

Functions which process unsorted sets do their thing in O(n2) time. But, if the list is sorted first the processing time drops to O(nlogn) including the time required to sort. This should be especially efficient on large sets. The effort is similar for many functions, this page's purpose is for discussion and documentation on implementing these functions.

References

(Third column should be a link to the anchor below)

Function	HyperSpec	Algorithm
INTERSECTION	intersection	--
SET-EXCLUSIVE-OR	set-xor	--
NSET-EXCLUSIVE-OR	nset-xor	--
SUBSETP	subsetp	--
UNION	union	--
NUNION	nunion	--

Details of Implementation

INTERSECTION Algorithms

INTERSECTION takes two lists (list1, list2) and returns a list of the intersection.

O(N^2) version

isFound = false
rtnlist = []
for(i=0, i<list1.length, i++)
  for(j=0, j<list2.length, j++)
    if(list1[i] == list2[j])
      isFound = true
      j = list2.length
  if(isFound == true)
    append(list1[i], rtnlist)
  isFound = false
return rtnlist

O(N*Log*N) Version

sort(list1)
sort(list2)
rtnlist = []
i,j = 0
while(i < list1.length AND j < list2.length)
  case1: list1[i] > list2[j]
    do: j++
  case2: list1[i] == list2[j]
    do: append(list1[i], rtnlist), i++
  case3: list1[i] < list2[j]
    do: i++
return rtnlist

-- ErikSvendsen - 27 Feb 2008

SUBSET Algorithms

SUBSET takes two lists (list1, list2) and returns TRUE if list1 is a subset of list2. O(N^2) version

isFound = false 
isSubset = true <br/>
for(i=0, i<list1.length, i++) 
  for(j=0, j<list2.length, j++) 
    if(list1[i] == list2[j])
      isFound = true 
      j = list2.length 
  if(isFound == false)
    isSubset = false 
    i = list1.length
  else 
    isFound = false
return isSubset 

O(N*Log*N) Version

sort(list1) 
sort(list2) 
isfinished = false 
isSubset = false
i,j = 0
while(isFinished == false) 
  case1: i >= list1.length 
    do: isSubset = true, isFinished = true 
  case2: list1[i] > list2[j] 
    do: j++ 
  case3: list1[i] == list2[j] 
    do: i++ 
  case4: list1[i] < list2[j] 
    do: isFinished = true 
return isSubset 

-- ErikSvendsen - 26 Feb 2008

UNION and NUNION Algorithms

UNION

O(N^2) version

The union function will accept two lists (list1, and list2)

(union list1 list2)

1. If list2 is empty then return list1 (end of algorithm).
2. If list1 is not empty then remove any elements in list2 that exist in list1.
3. Append list2 onto the front of list1.

Appending is O(n) while removing is O(n^2). We get O(n + n^2) which reduces to O(n^2).

O(N*Log*N) Version

N/A

NUNION

O(N^2) Version

1. If list2 is empty then return list1 (end of algorithm).
2. If list1 is not empty then remove any elements in list2 that exist in list1.
3. Append list2 onto the front of list1.

Appending is O(n) while removing is O(n^2). We get O(n + n^2) which reduces to O(n^2).

O(N*Log*N) Version

N/A

-- ErrolP - 26 Feb 2008

SET-DIFFERENCE Algorithm

SET-DIFFERENCE returns a list of elements of list1 that do not appear in list2.

O(N^2) version

rtnlist = []
for i 1 to a.length
   for j 1 to b.length
      if a[i]<>b[j]
         append a[i] to rtnlist
         j=b.length
return rtnlist

-- AldoDoronzo - 11 Mar 2008

Discussions

Forum Posts:

• http://clforjava.cs.cofc.edu/forum/index.php?topic=332.0

Current Status of SetAlgorithms

Status: Incomplete

Release Level:

Open bug count:

Test Suites

Links to Lisp Test results

-- JerryBoetje - 12 Jul 2003 -- AveryScott - 28 Feb 2008