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?
$\begingroup$
$\endgroup$
3
-
$\begingroup$ I'm guessing this is a strange way to write something like "head" and "tail" of the list being processed. I.e. the number following the letter is the position in the list, granted the numbering starts at 1 rather than 0. I'll try to write the code for this in a few to make sense of it. $\endgroup$– wvxvwMar 23, 2016 at 15:23
-
1$\begingroup$ This looks like merge sort in which you remove duplicates during the merge step. $\endgroup$– AuberonMar 23, 2016 at 15:41
-
4$\begingroup$ Don't use images as main content of your post. This makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and mathematics (note that you can use LaTeX) and don't forget to give proper attribution to your sources! Also, you should probably translate it to English. $\endgroup$– RaphaelMar 24, 2016 at 6:02
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
0
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$.
answered Mar 23, 2016 at 16:40
$\begingroup$
$\endgroup$
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]))
