CODEWITHSUNDEEP
python
Jaya_iitb
Jaya_iitb

Reputation: 41

I have a list of lists, how to extract index of sublists with common values?

I want the index of items from following list of lists which have overlapping elements. 

slist = [[1, 2, 3, 4, 5], [1, 2, 3, 4], [1, 2, 3, 4], [7, 8, 9, 10]]

Output should be like:

[0,1,2] and [3]

I tried the following but it gives me pairs of values from which it is difficult to segregate values as I expect

    for ((i,a),(j,b)) in itertools.combinations(enumerate(slist),2):
        if len(a.intersection(b)) > 0:
            print("overlapping",i,j)
        else:
            print("non overlapping",i,j)

Output:
('non overlapping', 0, 1)
('non overlapping', 0, 2)
('overlapping', 0, 3)
('overlapping', 1, 2)
('non overlapping', 1, 3)
('non overlapping', 2, 3)

Upvotes: 3

Views: 238

Answers (2)

Alexandre B.
Alexandre B.

Reputation: 5500

You can try the following:

  • Create a dictionary to keep for each sublist the potential other overlapping list
  • Define a overlapping function between two lists. You can use intersection between two set.
  • Then for each sublist combination, you look if they overlap. If they, you save the index of each other. To find the combination, I use the itertools.combinations as in the question.
  • Finally, to get the expected output, you need to remove the duplicates from the dictionary.

Here's the code:

import itertools

slist = [[1, 2, 3, 4, 5], [1, 2, 3, 4], [1, 2, 3, 4], [7, 8, 9, 10]]

# Dictionary to keep overlapping index
dict_ = {i: [i] for i in range(len(slist))}

# Iterate all combination
for combo in itertools.combinations([i for i in range(len(slist))], 2):
    sublist_1 = slist[combo[0]]
    sublist_2 = slist[combo[1]]
    # Check if they overlap
    if len(set(sublist_1).intersection(set(sublist_2))) > 0:
        # Save index
        dict_[combo[0]].append(combo[1])
        dict_[combo[1]].append(combo[0])

print(dict_)
# {0: [0, 1, 2], 1: [1, 0, 2], 2: [2, 0, 1], 3: [3]}

# Order each sublist in list of index to then remove duplicates
list_ = [set(sub) for sub in (list(dict_.values()))]

print([list(i) for i in set(map(tuple, list_))])
# [[0, 1, 2], [3]]

Upvotes: 1

Jab
Jab

Reputation: 27515

You can do this using a list comprehension:

>>> slist = [[1, 2, 3, 4, 5], [1, 2, 3, 4], [1, 2, 3, 4], [7, 8, 9, 10]]
>>> sets = tuple(map(set, slist))
>>> list(map(list, {tuple(i for i, _s in enumerate(sets) if s & _s) for s in sets}))
[[0, 1, 2], [3]]

If it makes it more readable/understandable I’m only using map to make the tuples into lists again. You need to use tuples as lists and sets are unhashable. If you don’t map list then it’s more readable but it results in a list of tuples.

list({tuple(i for i, _s in enumerate(sets) if s & _s) for s in sets}))

Upvotes: 4

Related Questions