1

I had a task like this. The section in this chapter called Alice in Wonderland, again! started with the observation that the merge algorithm uses a pattern that can be reused in other situations. Adapt the merge algorithm to write each of these functions, as was suggested there:

I need to solve this: a. Return only those items that are present in both lists.

The merge algorithm is given like this:

def merge(xs, ys):
    """ merge sorted lists xs and ys. Return a sorted result """
    result = []
    xi = 0
    yi = 0

    while True:
        if xi >= len(xs):          # If xs list is finished,
            result.extend(ys[yi:]) # Add remaining items from ys
            return result          # And we're done.

        if yi >= len(ys):          # Same again, but swap roles
            result.extend(xs[xi:])
            return result

        # Both lists still have items, copy smaller item to result.
        if xs[xi] <= ys[yi]:
            result.append(xs[xi])
            xi += 1
        else:
            result.append(ys[yi])
            yi += 1

My way off solving this question is:

def merge(xs, ys):
    """ merge sorted lists xs and ys. Return a sorted result """
    result = []
    xi = 0
    yi = 0

    while True:
        if xi >= len(xs):          # If xs list is finished,
            return result         # And we're done.

        if yi >= len(ys):          # Same again, but swap roles
            return result


        for xi in xs:
            if xi in ys:
                result.append(xi)


xs = [1,3,4,5,7,9,11,13,15,17,19]
ys = [4,5,8,12,16,20,24]
zs = xs+ys
zs.sort()
print(merge(xs, ys))

If you are interested in more information about this question you can find here: http://openbookproject.net/thinkcs/python/english3e/list_algorithms.html

The most important question for me: is there a better way off doing it and if there is, can you guys point me to the right direction?

Starter
  • 21
  • 3
  • This doesn't resemble the "merge" algorithm because you just do the whole thing in one go by brute-force checking with a `for` loop and the `in` operation. Your code never increments the indices `xi` or `yi`. You've also reused the variable `xi` for a different purpose (making it a value from the list instead of an index), so your code will not work correctly most of the time. Try adapting that part of the code from the "merge" algorithm instead of deleting it. – kaya3 Jan 20 '20 at 16:54
  • 2
    A more important thing is to give your question a descriptive title - no one knows what you're asking about by looking at it. – iBug Jan 20 '20 at 17:10
  • The title is meaningless. – trincot Jan 20 '20 at 18:31

1 Answers1

2

You can simply check this condition during merging the lists. This will return the elements that are there in both lists in O(n) time complexity. 

xs = [1,3,4,5,7,9,11,13,15,17,19]
ys = [4,5,8,12,16,20,24]

index1 = 0
index2 = 0
result = []
while index1 < len(xs) and index2 < len(ys):
    if xs[index1] == ys[index2]:
        result.append(xs[index1])
        index1 += 1
        index2 += 1
    elif xs[index1] < ys[index2]:
        index1 += 1
    else:
        index2 += 1
print(result)

OUTPUT

➜  codebase git:(master) ✗ python temp.py
[4, 5]
Albin Paul
  • 3,330
  • 2
  • 14
  • 30