1
$\begingroup$

Consider the following divide and conquer algorithm to remove duplicates in a list. The text is in French.

enter image description here

What is the meaning of the variables $c1, c2, d1, d2$? Why are only the variables $c1, d1$ compared?

$\endgroup$
  • $\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$ – wvxvw Mar 23 '16 at 15:23
  • 1
    $\begingroup$ This looks like merge sort in which you remove duplicates during the merge step. $\endgroup$ – Auberon Mar 23 '16 at 15:41
  • 3
    $\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$ – Raphael Mar 24 '16 at 6:02
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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]))
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.