CODEWITHSUNDEEP
pythonlistsetduplicatesmatch
d3pd
d3pd

Reputation: 8315

How can I form a list of matching elements in two lists, including duplicates?

I have two lists:

string1Elements = ['down', 'down', 'down', 'down']
string2Elements = ['down', 'down', 'right', 'down']

I want to form a list of elements that are common to the two lists, including duplicates. The result I want is as follows:

['down', 'down', 'down']

A way to think about the matching I have in mind is as follows:

0: The status is follows:

string1Elements = ['down', 'down', 'down', 'down']
string2Elements = ['down', 'down', 'right', 'down']

Both lists are the same size, so one is selected arbitrarily. If the lists were not the same size, the shorter one would be selected.

1: Get the first element of string1Elements (the selected list). Does this element exist in string2Elements? If it does, append it to the list of matches and remove it from string1Elements and string2Elements.

string1Elements = ['down', 'down', 'down']
string2Elements = ['down', 'right', 'down']
matches         = ['down']

2: Get the first element of string1Elements. Does this element exist in string2Elements? If it does, append it to the list of matches and remove it from string1Elements and string2Elements.

string1Elements = ['down', 'down']
string2Elements = ['right', 'down']
matches         = ['down', 'down']

3: Get the first element of string1Elements. Does this element exist in string2Elements? If it does, append it to the list of matches and remove it from string1Elements and string2Elements.

string1Elements = ['down']
string2Elements = ['right']
matches         = ['down', 'down', 'down']

4: Get the first element of string1Elements. Does this element exist in string2Elements? If it does, append it to the list of matches and remove it from string1Elements and string2Elements.

string1Elements = ['down']
string2Elements = ['right']
matches         = ['down', 'down', 'down']

5: All elements have been checked.

The above procedure is just to explain how I want to handle duplicate elements. I wouldn't actually want to change the lists string1Elements and string2Elements.

I don't think that sets can be used in an obvious way because of the duplicate elements:

matches = list(set(string2Elements).intersection(string1Elements))

I've tried a quick test using list comprehension:

matches = [element for element in string1Elements if element in string2Elements]

Neither of these approaches are sufficient. How could I implement the matching in the way I describe?

Upvotes: 1

Views: 728

Answers (1)

user4237459
user4237459

Reputation:

You can systematically pop from one list and append to a result list if they match. Because you have popped from the list, it won't match one element in list1 to five elements in list2, as it would've been popped out. An example function:

def intersect(a, b):
    if len(b) < len(a):  # iff b is shorter than a
        a, b = b, a      # swap the lists.
    b = b[:]  # To prevent modifying the lists
    return [b.pop(b.index(i)) for i in a if i in b]

Usage:

list1 = ['down', 'down', 'down', 'down']
list2 = ['down', 'down', 'right', 'down']
matches = intersect(list1, list2)
print(" ".join(matches))

# Prints:
down down down

This does exactly as the OP explains how it would be done in the question, except it only removes elements from the shorter list.
One that works on multiple lists could be achieved as follows

def multi_intersect(*args):
    if len(args) == 1:
        try:
            return multi_intersect(*args)
        except TypeError:
            pass
    inters = [item for sublist in args for item in sublist]
    for arg in args:
        inters = intersect(inters, arg)
    return inters

Upvotes: 1

Related Questions