Consider the following divide and conquer algorithm to remove duplicates in a list. The text is in French.
What is the meaning of the variables $c1, c2, d1, d2$? Why are only the variables $c1, d1$ compared?
Consider the following divide and conquer algorithm to remove duplicates in a list. The text is in French.
What is the meaning of the variables $c1, c2, d1, d2$? Why are only the variables $c1, d1$ compared?
As wvxvw suggested, the dot notation is a shorthand way of separating the head and the tail of a list, as in LISP or ML. For example, if we have a list $L=\langle\,4,7,8\,\rangle$ then we can write $L$ as $c_1.c_2$ where $c_1=4$ and $c_2=\langle\,7,8\,\rangle$.
The function $\Delta$ takes two sorted lists, $c_1.c_2$ and $d_1.d_2$ and recursively produces a list without duplicates. For instance, we might have $$\begin{align} \Delta(\langle\,6\,\rangle,\langle\,3,5,6\,\rangle) &=\langle\,3,\Delta(\langle\,6\,\rangle,\langle\,5,6\,\rangle)\,\rangle&\text{by rule 3}\\ &=\langle\,3,5,\Delta(\langle\,6\,\rangle,\langle\,6\,\rangle)\,\rangle&\text{by rule 3}\\ &=\langle\,3,5,6,\Delta(\varnothing,\varnothing)\,\rangle&\text{by rule 2}\\ &=\langle\,3,5,6\,\rangle \end{align}$$ This is where the real work is done. The function $SD$ uses $\Delta$ by splitting the original sorted list $\langle\,s_1,s_2,\dotsc,s_n\,\rangle$ into two: the odd-indexed part, $\langle\,s_1,s_3,s_5,\dotsc\,\rangle$ and the even-indexed part, $\langle\,s_2,s_4,s_6,\dotsc\,\rangle$ and applies $\Delta$ to them, to remove duplicates. For instance, $$\begin{align} SD(\langle\,3,3,3,5,6,6\,\rangle&=\Delta(SD(\langle\,3,3,6\,\rangle),SD(\langle\,3,5,6\,\rangle))\\ &=\Delta(\langle\,3,6\,\rangle,\langle\,3,5,6\,\rangle)&\text{since $SD$ removes dups}\\ &=\langle\,3,5,6\,\rangle \end{align}$$ as we saw above. It's worth noting that the arguments to both functions must be in sorted order. To see why, trace the action on, say, $\langle\,3,4,2,3\,\rangle$.
In addition to the explanation by Rick Decker, here's an implementation of this algorithm in Python:
def merge(left, right):
result = []
while left and right:
small, big = min(left, right), max(left, right)
result.append(small[0])
left, right = ((left[1:], right[1:])
if small[0] == big[0]
else (small[1:], big))
return result + [x for x, y in zip(right, right[1:] + [None])
if x != y]
def remove_duplicates(candidates):
if not candidates or len(candidates) == 1:
return candidates
return merge(remove_duplicates(candidates[1::2]),
remove_duplicates(candidates[::2]))