How to compare elements of a list in a Python map's value, and check to see if at least n number of elements match?

Question

I want to iterate over a map's values and compare elements of a list to see if at least 3 elements match in the same order, and then have a list returned with the keys that match the condition.

prefs = {
        's1': ["a", "b", "c", "d", "e"],
        's2': ["c", "d", "e", "a", "b"],
        's3': ["a", "b", "c", "d", "e"],
        's4': ["c", "d", "e", "b", "e"],
        's5': ["c", "d", "e", "a", "b"]
    }

Here is a sample map. In this example keys s1, and s3 have at least three elements in the list value that match "a", "b", "c". So s1, and s3 should be returned like this s1 -- s3. Similarly s2 and s4 match so that should also be returned, but s2 has multiple matches because it matches with s5 as well so s2 -- s5 should be returned. I want to return all possible matches for each key-value pair in a list. The return output should be something like:

[[s1--s3], [s2--s4], [s2--s5], [s4--s5]]

I'm unable to figure out how I can iterate over each value in the map, but here is a snippet of element-wise comparison. I'm wondering if I can set a counter, and check to see if match_cnt > 3 and then return the keys in a list.

a = ["a", "b", "c", "d", "e"]
b = ["a", "c", "b", "d", "e"]
match_cnt = 0

if len(a) == len(b):
    for i in range(len(a)):
        if a[i] == b[i]:
            print(a[i], b[i])

Also, want some knowledge on the runtime of this algorithm. Complete code solution would be appreciated. I had been advised to open a new question here

All of these lists have at least 3 elements in common with each other. Or does it have to be the first 3? — user2390182, Dec 26 '18 at 17:27
Possible duplicate of [compare python dictionary values of type list to see if they match in that order](https://stackoverflow.com/questions/53926562/compare-python-dictionary-values-of-type-list-to-see-if-they-match-in-that-order) — sahasrara62, Dec 26 '18 at 17:28
Asking for a "complete code solution" is out of scope for Stack Overflow. — Prune, Dec 26 '18 at 17:28
https://stackoverflow.com/questions/3294889/iterating-over-dictionaries-using-for-loops shows how to loop over the keys and values of a dictionary. — Barmar, Dec 26 '18 at 17:29
is this modified version of this [question](https://stackoverflow.com/questions/53926562/compare-python-dictionary-values-of-type-list-to-see-if-they-match-in-that-order), which is asked earlier by you — sahasrara62, Dec 26 '18 at 17:29
It has to be in that order. So for instance if s1 has a,b,c,d,e and s2 has a,b,c,d,e then that is a match. But if s1 has a,b,c,d,e and s2 has a,c,b,d,e then that is not a match. The three matching elements should match thrice consecutively, so it does not matter if its the first three, last three, or middle three. — Sumanth M, Dec 26 '18 at 17:29
@prashant rana I was advised to open a new question instead of commenting on the old one — Sumanth M, Dec 26 '18 at 17:34
@SumanthM you should ask from the point where you have to procced further from that question . not full question again — sahasrara62, Dec 26 '18 at 17:36
@prashant rana there is a significant modification to this question from the previous one. This involves list element comparison and a counter value with a modified form of return values. But I will take your suggestion into mind. — Sumanth M, Dec 26 '18 at 17:39
@nixon : What do you mean by duplicates, there can be lists that are similar or the same. But becuase they are tied to a different key, it would not be duplicate. The keys just represent a user, and the values are their preferences for places to visit. — Sumanth M, Dec 26 '18 at 17:40
No, I mean if a list can have duplicate values, i.e `[ "a", "a", "c", "d", "e"]` — yatu, Dec 26 '18 at 17:42
@nixon: No the list cannot have duplicates. All elements are unique. — Sumanth M, Dec 26 '18 at 17:44

Maurice Meyer · Accepted Answer · 2018-12-31T12:17:57.450

You can make use .items() to iterate over the map, then it's just matching the first 3 list items using a slice:

prefs = {
    's1': ["a", "b", "c", "d", "e"],
    's2': ["c", "d", "e", "a", "b"],
    's3': ["a", "b", "c", "d", "e"],
    's4': ["c", "d", "e", "b", "e"],
    's5': ["c", "d", "e", "a", "b"]
}

results = []
for ki, vi in prefs.items():
    for kj, vj in prefs.items():
        if ki == kj:  # skip checking same values on same keys !
            continue

        if vi[:3] == vj[:3]:  # slice the lists to test first 3 characters
            match = tuple(sorted([ki, kj]))  # sort results to eliminate duplicates
            results.append(match)

print (set(results))  # print a unique set

Returns:

set([('s1', 's3'), ('s4', 's5'), ('s2', 's5'), ('s2', 's4')])

Edit:
To check all possible combinations, you can use combinations() from itertools. iCombinations/jCombinations are preserving order with a length of 3 list items:

from itertools import combinations

prefs = {
    's1': ["a", "b", "c", "d", "e"],
    's2': ["c", "d", "e", "a", "b"],
    's3': ["a", "b", "c", "d", "e"],
    's4': ["c", "d", "e", "b", "e"],
    's5': ["c", "d", "e", "a", "b"]
}

results = []
for ki, vi in prefs.items():
    for kj, vj in prefs.items():
        if ki == kj:  # skip checking same values on same keys !
            continue

        # match pairs from start
        iCombinations = [vi[n:n+3] for n in range(len(vi)-2)]
        jCombinations = [vj[n:n+3] for n in range(len(vj)-2)]

        # match all possible combinations
        import itertools
        iCombinations = itertools.combinations(vi, 3)
        jCombinations = itertools.combinations(vj, 3)

        if any([ic in jCombinations for ic in iCombinations]):  # checking all combinations
            match = tuple(sorted([ki, kj]))
            results.append(match)

print (set(results))  # print a unique set

This returns:

set([('s1', 's3'), ('s2', 's5'), ('s3', 's5'), ('s2', 's3'), ('s2', 's4'), ('s1', 's4'), ('s1', 's5'), ('s3', 's4'), ('s4', 's5'), ('s1', 's2')])

This solution is only checking to see if the first three elements match, and then returns the set, but I want to return the keys for anywhere I match the elements three consecutive times in the list. So, for instance, I can have a 's1': ["c", "d", "a", "b", "c"] and 's3': ["d", "c", "a", "b", "c"], this should be a match because I have three consecutive elements that match across both the lists. Is there a way to modify the list comprehension to check the entire list to see if 3 elements match consecutively. — Sumanth M, Dec 26 '18 at 18:56
@Sumanth M, added match3-pair combinations: ['a', 'b', 'c'], ['b', 'c', 'd'], ['c', 'd', 'e'] in case of s1. — Maurice Meyer, Dec 26 '18 at 21:27
Thanks for the easy to follow code. But Can the above code be modified such that it returns matches where at least three elements match, but the elements need not be in consecutive order. They can be in any given order. for ex: s1: [a,b,c,d,e] would match with s2: [e,a,f,b,q]. Because [b,a,e] are common in both keys. I'm looking at the jcombinations to see if that can be tweaked, can you chime in. — Sumanth M, Dec 30 '18 at 18:48
Sure you can do that, have a look at [itertools](https://docs.python.org/2/library/itertools.html#itertools.combinations). Especially `itertools.combinations()`, to create all possible combinations. `itertools.combinations(vi, 3)` ... — Maurice Meyer, Dec 30 '18 at 18:55
You might want zu ask a new question, comments are not the right place to modify code :) — Maurice Meyer, Dec 30 '18 at 19:07
Would you be willing to provide an additional edit to the current question, I'm afraid I'll be blocked or marked as a duplicate for asking a similar question. — Sumanth M, Dec 30 '18 at 20:01

score 1 · Answer 2 · answered Dec 26 '18 at 19:08

I've tried to be as detailed as possible. This should be an example how you can often work your way through such a problem by inserting a lot of print messages to create a log of what's going on.

prefs = {
    's1': ["a", "b", "c", "d", "e"],
    's2': ["c", "d", "e", "a", "b"],
    's3': ["a", "b", "c", "d", "e"],
    's4': ["c", "d", "e", "b", "e"],
    's5': ["c", "d", "e", "a", "b"]
}

# Get all items of prefs and sort them by key. (Sorting might not be
# necessary, that's something you'll have to decide.)
items_a = sorted(prefs.items(), key=lambda item: item[0])

# Make a copy of the items where we can delete the processed items.
items_b = items_a.copy()

# Set the length for each compared slice.
slice_length = 3

# Calculate how many comparisons will be necessary per item.
max_shift = len(items_a[0][1]) - slice_length

# Create an empty result list for all matches.
matches = []

# Loop all items
print("Comparisons:")
for key_a, value_a in items_a:
    # We don't want to check items against themselves, so we have to
    # delete the first item of items_b every loop pass (which would be
    # the same as key_a, value_a).
    del items_b[0]
    # Loop remaining other items
    for key_b, value_b in items_b:
        print("- Compare {} to {}".format(key_a, key_b))
        # We have to shift the compared slice
        for shift in range(max_shift + 1):
            # Start the slice at 0, then shift it
            start = 0 + shift
            # End the slice at slice_length, then shift it
            end = slice_length + shift
            # Create the slices
            slice_a = value_a[start:end]
            slice_b = value_b[start:end]
            print("  - Compare {} to {}".format(slice_a, slice_b), end="")
            if slice_a == slice_b:
                print(" -> Match!", end="")
                matches += [(key_a, key_b, shift)]
            print("")

print("Matches:")
for key_a, key_b, shift in matches:
    print("- At positions {} to {} ({} elements), {} matches with {}".format(
        shift + 1, shift + slice_length, slice_length, key_a, key_b))

Which prints:

Comparisons:
- Compare s1 to s2
  - Compare ['a', 'b', 'c'] to ['c', 'd', 'e']
  - Compare ['b', 'c', 'd'] to ['d', 'e', 'a']
  - Compare ['c', 'd', 'e'] to ['e', 'a', 'b']
- Compare s1 to s3
  - Compare ['a', 'b', 'c'] to ['a', 'b', 'c'] -> Match!
  - Compare ['b', 'c', 'd'] to ['b', 'c', 'd'] -> Match!
  - Compare ['c', 'd', 'e'] to ['c', 'd', 'e'] -> Match!
- Compare s1 to s4
  - Compare ['a', 'b', 'c'] to ['c', 'd', 'e']
  - Compare ['b', 'c', 'd'] to ['d', 'e', 'b']
  - Compare ['c', 'd', 'e'] to ['e', 'b', 'e']
- Compare s1 to s5
  - Compare ['a', 'b', 'c'] to ['c', 'd', 'e']
  - Compare ['b', 'c', 'd'] to ['d', 'e', 'a']
  - Compare ['c', 'd', 'e'] to ['e', 'a', 'b']
- Compare s2 to s3
  - Compare ['c', 'd', 'e'] to ['a', 'b', 'c']
  - Compare ['d', 'e', 'a'] to ['b', 'c', 'd']
  - Compare ['e', 'a', 'b'] to ['c', 'd', 'e']
- Compare s2 to s4
  - Compare ['c', 'd', 'e'] to ['c', 'd', 'e'] -> Match!
  - Compare ['d', 'e', 'a'] to ['d', 'e', 'b']
  - Compare ['e', 'a', 'b'] to ['e', 'b', 'e']
- Compare s2 to s5
  - Compare ['c', 'd', 'e'] to ['c', 'd', 'e'] -> Match!
  - Compare ['d', 'e', 'a'] to ['d', 'e', 'a'] -> Match!
  - Compare ['e', 'a', 'b'] to ['e', 'a', 'b'] -> Match!
- Compare s3 to s4
  - Compare ['a', 'b', 'c'] to ['c', 'd', 'e']
  - Compare ['b', 'c', 'd'] to ['d', 'e', 'b']
  - Compare ['c', 'd', 'e'] to ['e', 'b', 'e']
- Compare s3 to s5
  - Compare ['a', 'b', 'c'] to ['c', 'd', 'e']
  - Compare ['b', 'c', 'd'] to ['d', 'e', 'a']
  - Compare ['c', 'd', 'e'] to ['e', 'a', 'b']
- Compare s4 to s5
  - Compare ['c', 'd', 'e'] to ['c', 'd', 'e'] -> Match!
  - Compare ['d', 'e', 'b'] to ['d', 'e', 'a']
  - Compare ['e', 'b', 'e'] to ['e', 'a', 'b']
Matches:
- At positions 1 to 3 (3 elements), s1 matches with s3
- At positions 2 to 4 (3 elements), s1 matches with s3
- At positions 3 to 5 (3 elements), s1 matches with s3
- At positions 1 to 3 (3 elements), s2 matches with s4
- At positions 1 to 3 (3 elements), s2 matches with s5
- At positions 2 to 4 (3 elements), s2 matches with s5
- At positions 3 to 5 (3 elements), s2 matches with s5
- At positions 1 to 3 (3 elements), s4 matches with s5

It's still unclear, what your output really should be. However, I think you'll have no problems in converting the above code to your needs.

I've updated the question. Is it possible to iterate over the list types values for all given keys to check and see if at least one element of the first value exists in the second one. Lets assume that each value has at least one element, I just want to check to see if there is at least one element that is matching. I have tried the intersection function, but no luck — Sumanth M, Dec 26 '18 at 22:51

How to compare elements of a list in a Python map's value, and check to see if at least n number of elements match?

2 Answers2

Linked