Find the closest matching elements in a list of lists

Question

I have 2 list of lists(namely list_1 and list_2) that I need to check for similarities. I want to track the highest number of matches and get the indexes of list_1 and list_2 with the highest matches.

Note: Highest matches can be more than 1 since the highest number of matches can occur again(duplicate).

I have tried to find the highest using max function, but it doesn't give me the other highest duplicate values.

list_of_similarities = []
def similarities():
    print("SIMILARITIES")
    for i in range(len(list_1)):
        for j in range(len(list_2)):
            if set(list_2[j]) & set(list_1[i]):
                matchingValues = set(list_2[j]) & set(list_1[i])
                print('list_1[{}], list_2[{}]'.format(i, j), 'matching value:',set(list_2[j]) & set(list_1[i]))
                list_of_similarities.append(matchingValues)
                print("")
        print("")
        print("The maximum matches found are:")
        print(max(list_of_similarities))
        list_of_similarities.clear()

list_1 = [['a','b','c'],['d','e','g'],['l','r'],['z']]

list_2 = [['b','c'], ['l','e','a'], ['f'], ['z','r'], ['x', 'b', 'c']]

CURRENT RESULT

# list_1[0], list_2[0] matching value: {'b', 'c'}
# list_1[0], list_2[1] matching value: {'a'}
# list_1[0], list_2[4] matching value: {'b', 'c'}
# The maximum matches found are:
# {'b', 'c'}

# list_1[1], list_2[1] matching value: {'e'}
# The maximum matches found are:
# {'e'}

# list_1[2], list_2[1] matching value: {'l'}
# The maximum matches found are:
# {'l'}

# list_1[2], list_2[3] matching value: {'r'}
# The maximum matches found are:
# {'r'}

# list_1[3], list_2[3] matching value: {'z'}
# The maximum matches found are:
# {'z'}

EXPECTED RESULT

# list_1[0], list_2[0] matching value: {'b', 'c'}
# list_1[0], list_2[1] matching value: {'a'}
# list_1[0], list_2[4] matching value: {'b', 'c'}
# The maximum matches found are:
# {'b', 'c'}
# The list_1 and list_2 indexes for highest matches are:
# [0,[0, 4]]

# list_1[1], list_2[1] matching value: {'e'}
# The maximum matches found are:
# {'e'}
# The list_1 and list_2 indexes for highest matches are:
# [1,[1]]

# list_1[2], list_2[1] matching value: {'l'}
# The maximum matches found are:
# {'l'}
# The list_1 and list_2 indexes for highest matches are:
# [2,[1]]

# list_1[2], list_2[3] matching value: {'r'}
# The maximum matches found are:
# {'r'}
# The list_1 and list_2 indexes for highest matches are:
# [2,[3]]

# list_1[3], list_2[3] matching value: {'z'}
# The maximum matches found are:
# {'z'}
# The list_1 and list_2 indexes for highest matches are:
# [3,[3]]

Answer 1

The Zen of Python asserts that 'Flat is better than nested', so this approach to the problem doesn't use an explicit nested loop. Having said that, there is a lot of looping in comprehensions, so it might well be slower than using nested for loops.

It uses itertools.product to create the pairs for matching.

>>> pairs = itertools.product(['a', 'b'], [1, 2])
>>> for p, q in pairs:print(p, q)
... 
a 1
a 2
b 1
b 2

and itertools.groupby to group the pairs by the element from the first list:

>>> pairs = itertools.product(['a', 'b'], [1, 2])
>>> for k, g in itertools.groupby(pairs, key=lambda x: x[0]):
...     print(k, list(g))
... 
a [('a', 1), ('a', 2)]
b [('b', 1), ('b', 2)]

When calling max on a list of (frozen) sets it specifies that max must use the length of the set. This is because by default, a set's greater than operation returns whether the set is a superset of another, not whether it is longer

>>> set([1, 2]) > set([3, 4, 5])
False
>>> max([set([1, 2]), set([1, 2, 3]), set([4, 5, 6, 7, 8, 9])])
{1, 2, 3}
>>> max([set([1, 2]), set([1, 2, 3]), set([4, 5, 6, 7, 8, 9])], key=len)
{4, 5, 6, 7, 8, 9}

This approach correctly reports all "longest" matches if there is more than one. Matches are stored as frozensets so that they may be easily deduplicated if a match occurs more than once.

import itertools

def similarities():
    # Create format strings.
    matched_fmt = 'list_1[{}], list_2[{}] matching value: {}'
    index_fmt = '[{}, {}]'
    print("SIMILARITIES")

    # Get the cartesian product of the two lists.
    product = itertools.product(list_1, list_2)
    # Iterate over the product, grouping by the element in the first list.
    # Enumerate the iteration so that we know the index of the item in the first list.
    for i, (_, g) in enumerate(itertools.groupby(product, key=lambda x: x[0])):
        # List all matches and the index of the second list element.
        matches = [(j, frozenset(p) & frozenset(q)) for (j, (p, q)) in enumerate(g)]

        # Find the longest matches.
        longest = len(max(matches, key=lambda x: len(x[1]))[1])
        longest_matches = [(idx, match) for (idx, match) in matches 
                           if len(match) == longest]

        found_matches = [(idx, match) for (idx, match) in matches if match]
        unique_matches = {match for (_, match) in longest_matches}

        # Report.
        found_lines = [matched_fmt.format(i, index, match) 
                       for index, match in found_matches]
        print('\n'.join(found_lines))
        print("The maximum matches found are:")
        print(' '.join(str(match) for match in unique_matches))
        print('The list_1 and list_2 indexes for the highest matches are:')
        print(index_fmt.format(i, [index for (index, _) in longest_matches]))
        print()

The function produces this output:

SIMILARITIES
list_1[0], list_2[0] matching value: frozenset({'c', 'b'})
list_1[0], list_2[1] matching value: frozenset({'a'})
list_1[0], list_2[4] matching value: frozenset({'c', 'b'})
The maximum matches found are:
frozenset({'c', 'b'})
The list_1 and list_2 indexes for the highest matches are:
[0, [0, 4]]

list_1[1], list_2[1] matching value: frozenset({'e'})
The maximum matches found are:
frozenset({'e'})
The list_1 and list_2 indexes for the highest matches are:
[1, [1]]

list_1[2], list_2[1] matching value: frozenset({'l'})
list_1[2], list_2[3] matching value: frozenset({'r'})
The maximum matches found are:
frozenset({'r'}) frozenset({'l'})
The list_1 and list_2 indexes for the highest matches are:
[2, [1, 3]]

list_1[3], list_2[3] matching value: frozenset({'z'})
The maximum matches found are:
frozenset({'z'})
The list_1 and list_2 indexes for the highest matches are:
[3, [3]]

Answer 2

list_of_similarities = []
def similarities():
    print("SIMILARITIES")
    for i in range(len(list_1)):
        idx_list2 = []
        for j in range(len(list_2)):
            if set(list_2[j]) & set(list_1[i]):
                matchingValues = set(list_2[j]) & set(list_1[i])
                print('list_1[{}], list_2[{}]'.format(i, j), 'matching value:',set(list_2[j]) & set(list_1[i]))
                list_of_similarities.append(matchingValues)

        print("The maximum matches found are:")
        print(max(list_of_similarities))

        val = max(list_of_similarities)
        for idx, item in enumerate(list_2):
            # check if item contains all elements in val
            result = all(elem in item for elem in list(val))
            if result:
                idx_list2.append(idx)

        print ("The list_1 and list_2 indexes for highest matches are:")
        print ([i,idx_list2])
        print ("")
        list_of_similarities.clear()

list_1 = [['a','b','c'],['d','e','g'],['l','r'],['z']]
list_2 = [['b','c'], ['l','e','a'], ['f'], ['z','r'], ['x', 'b', 'c']]
similarities()

output:

SIMILARITIES
list_1[0], list_2[0] matching value: {'c', 'b'}
list_1[0], list_2[1] matching value: {'a'}
list_1[0], list_2[4] matching value: {'c', 'b'}
The maximum matches found are:
{'c', 'b'}
The list_1 and list_2 indexes for highest matches are:
[0, [0, 4]]

list_1[1], list_2[1] matching value: {'e'}
The maximum matches found are:
{'e'}
The list_1 and list_2 indexes for highest matches are:
[1, [1]]

list_1[2], list_2[1] matching value: {'l'}
list_1[2], list_2[3] matching value: {'r'}
The maximum matches found are:
{'l'}
The list_1 and list_2 indexes for highest matches are:
[2, [1]]

list_1[3], list_2[3] matching value: {'z'}
The maximum matches found are:
{'z'}
The list_1 and list_2 indexes for highest matches are:
[3, [3]]