List of lists, matching first item in a list to second element in the others lists

Question

Say i got this list

A = [['a','b'],
     ['b','c'],
     ['c','a'],
     ['d','a'],
     ['e',None]]

What's the best/efficient way to match the elements, so that you can find out which list that has a match between the first and second element in the lists.

Expected matches would be:

list 2 and 3 matches 0
list 1 matches list 2
list 0 matches list 1.

As seen, there can be more that match on one list, and there can be None values that doesn't match any. There will also be other items in the list in the list, but are not needed for this example. The first and second item in each list does not match. I want to run something each time there is a match, and needed an easy way to do that.

Does that makes sense and is doable?

Are the first elements unique? What should happen if they are not, e.g. `'a'` appears in two rows in the first position? — Martijn Pieters, Aug 17 '17 at 08:01

score 3 · Accepted Answer · answered Aug 17 '17 at 08:02

3

Create a mapping from first element to index. I'm presuming the first elements are unique to simplify this example:

indices = {t[0]: i for i, t in enumerate(A)}

Now you can trivially map each element to an index that matches it:

for index, (first, second) in enumerate(A):
    if second in indices:
        print(f'Row {index} matches row {indices[second]}')

Demo:

>>> A = [['a','b'],
...      ['b','c'],
...      ['c','a'],
...      ['d','a'],
...      ['e',None]]
>>> indices = {t[0]: i for i, t in enumerate(A)}
>>> for index, (first, second) in enumerate(A):
...     if second in indices:
...         print(f'Row {index} matches row {indices[second]}')
...
Row 0 matches row 1
Row 1 matches row 2
Row 2 matches row 0
Row 3 matches row 0

answered Aug 17 '17 at 08:02

Martijn Pieters

1,048,767
296
4,058
3,343

3

[But but... there appears to be no attempt from OP.](https://meta.stackoverflow.com/q/353940/846892) – Ashwini Chaudhary Aug 17 '17 at 08:06
Thanks. The first items are unique. So this is exactly what i was hoping for! – Thomasedv Aug 17 '17 at 08:09
@AshwiniChaudhary Sometimes... it's for the greater good of humanity that low effort questions be answered :p – cs95 Aug 17 '17 at 08:14
@AshwiniChaudhary I made this question mainly in hopes to discover a good way to do this. As my best attempt meant a double for loop and lots of checking, which i didn't like or feel to be a good solution at all. I'll take that criticism, and mention my tries next time i have a question. – Thomasedv Aug 17 '17 at 08:15
@Thomasedv If you have a working code then share it, it's okay if it's not good enough. Else you're asking us to write code for you and it was provided to you as well unfortunately. – Ashwini Chaudhary Aug 17 '17 at 08:17
@cᴏʟᴅsᴘᴇᴇᴅ That's really bad :-( On some other day or time this would have ended up in 5-6 downvotes easily but right now it has upvotes and answer from high rep user. – Ashwini Chaudhary Aug 17 '17 at 08:20
@AshwiniChaudhary When a question like [this](https://stackoverflow.com/q/45164645/4909087) becomes a hot network post, you know anything is possible :p – cs95 Aug 17 '17 at 08:21
@AshwiniChaudhary: if you feel the question needs closing, then vote so, but don't berate those that answer. This is more of an algorithm question, not 'my code is broken, debug it' question. The line is sometimes blurry, but I feel an algorithm question is answerable and useful for future visitors. – Martijn Pieters Aug 17 '17 at 08:24
@AshwiniChaudhary: besides, I'm sure you [have made the same call in the past](https://stackoverflow.com/questions/18713321/element-wise-addition-of-2-lists/18713344#18713344), right? – Martijn Pieters Aug 17 '17 at 08:25
@MartijnPieters I already [admitted that](https://meta.stackoverflow.com/questions/353940/why-would-a-question-thats-normally-too-broad-in-any-other-language-be-okay-i#comment497831_353940), but there's no need to keep repeating it. I am not targeting anyone. It's a general issue with Python tag and won't go away without effort from everyone. – Ashwini Chaudhary Aug 17 '17 at 08:33
@AshwiniChaudhary: this is not an issue with the Python tag. There will always be grey areas, in all tags, all over Stack Overflow. – Martijn Pieters Aug 17 '17 at 08:39

score 0 · Answer 2 · answered Aug 17 '17 at 09:50

What you have looks like a list of edges of a graph and what you're seeking to find out is whether they're connected (i.e. they have an edge in common).

You also have a directed graph and the order of the edges counts for your "match" (which is not symmetric as you have defined it).

edge = [['a','b'],
        ['b','c'],
        ['c','a'],
        ['d','a'],
        ['e',None]]

# order of edges doesn't count
def is_connected(e1, e2):
    return e1[0] == e2[1] or e1[1] == e2[0]

# order of edges counts
def is_child(e1, e2):
    return e1[1] == e2[0]

What you want is the second check is_child, I assume

print(is_connected(edge[0],edge[1]))
print(is_connected(edge[1],edge[2]))
print(is_connected(edge[0],edge[2]))

print(is_child(edge[0],edge[1]))
print(is_child(edge[1],edge[2]))
print(is_child(edge[0],edge[2])) # false
print(is_child(edge[2],edge[0]))

If you want to check this type of oriented connections for all edges in the graph you basically want to group by the second coordinates and there's a handy function groupby in pandas to do that:

import pandas as pd
df = pd.DataFrame(edge)

grouped = df.groupby(1)
grouped.groups
# Output:
{'a': [2L, 3L], 'c': [1L], 'b': [0L]}

grouped.groups['a']
# Output:
# [2L, 3L]

grouped[0].apply(lambda x: ','.join(x)).reset_index()
# Output:
#    1    0
# 0  a  c,d
# 1  b    a
# 2  c    b

List of lists, matching first item in a list to second element in the others lists

2 Answers2