CODEWITHSUNDEEP
python
Ejaz
Ejaz

Reputation: 1632

How to filter list of tuples with an item of a tuple?

I have this list - 

d = [('A', 'B', 1), ('C', 'D', 1), 
     ('B', 'D', 2), ('A', 'B', 3), 
     ('A', 'D', 3), ('B', 'C', 4), 
     ('A', 'C', 5), ('B', 'C', 8)]

Here first two items in the tuple are nodes, and the third item is the weight. I want to remove the tuple with same 1st and 2nd nodes (same 1st and 2nd node between two tuples) but higher weight.

Final List:

d = [('A', 'B', 1), ('C', 'D', 1), 
     ('B', 'D', 2), ('A', 'D', 3), 
     ('B', 'C', 4), ('A', 'C', 5)]

I have tried something like this, but looks like not a very clean solution.

edge_dict = {}

for x in d:
    key = '%s%s' % (x[0], x[1])
    if not edge_dict.get(key):
        edge_dict[key] = x[2]
    else:
        if edge_dict[key] > x[2]:
            edge_dict[key] = x[2]       

final_list = []
for k, v in edge_dict.items():
    t = list(k)
    t.append(v)
    final_list.append(tuple(t))


final_list.sort(key=lambda x: x[2])
print final_list

Upvotes: 2

Views: 1139

Answers (4)

Taohidul Islam
Taohidul Islam

Reputation: 5414

Slightly different of your code but idea is almost same.

  1. Check whether the Node pair is previously found, if not found then store it without any comparison.
  2. If the node pair previously found then compare the values and store the minimum value
  3. Use sorted form of node pair as dictionary key to treat ('B','A') as ('A','B').

Also read the comments for better clarification:

check_dict={} #This will store the minimum valued nodes

for i in d:
    if check_dict.get((i[0],i[1])) ==None: #if the node is absent then add it to the check_dict
        check_dict[tuple(sorted((i[0],i[1])))] = i[2]
    else: #if the node is present then compare with the previous value and store the minimum one
        check_dict[tuple(sorted((i[0],i[1])))] = min(check_dict[(i[0],i[1])],i[2]) #used sorted to treat ('A','B') as same as ('B',A')
expected_list = [tuple(key+(value,)) for key,value in check_dict.items()] #create your list of tuples
print(expected_list)

Output : 

[('A', 'B', 1), ('C', 'D', 1), ('B', 'D', 2), ('A', 'D', 3), ('B', 'C', 4), ('A', 'C', 5)]

Upvotes: 1

wwii
wwii

Reputation: 23783

Just a little refactoring.

edge_dict = {}

for t in d:
    key = t[:2]
    value = t[-1]
    if key in edge_dict:
        edge_dict[key] = min(value, edge_dict[key]) 
    else:
        edge_dict[key] = value

final_list = [(q,r,t) for (q,r),t in edge_dict.items()]
final_list.sort(key=lambda x: x[2])

Upvotes: 2

niraj
niraj

Reputation: 18218

One other way may be to first sorting the list of tuples on first two elements of each tuple and descending order for last element:

sorted_res = sorted(d, key = lambda x:((x[0], x[1]), x[2]),reverse=True)
print(sorted_res)

Result:

[('C', 'D', 1),
 ('B', 'D', 2),
 ('B', 'C', 8),
 ('B', 'C', 4),
 ('A', 'D', 3),
 ('A', 'C', 5),
 ('A', 'B', 3),
 ('A', 'B', 1)]

Now creating dictionary with key of first two element and value will be the latest one which is small:

my_dict = {(i[0], i[1]):i for i in sorted_res}
print(my_dict)

Result:

{('A', 'B'): ('A', 'B', 1),
 ('A', 'C'): ('A', 'C', 5),
 ('A', 'D'): ('A', 'D', 3),
 ('B', 'C'): ('B', 'C', 4),
 ('B', 'D'): ('B', 'D', 2),
 ('C', 'D'): ('C', 'D', 1)}

Final result is values of dictionary:

list(my_dict.values())

Result:

[('A', 'C', 5),
 ('A', 'B', 1),
 ('A', 'D', 3),
 ('B', 'D', 2),
 ('C', 'D', 1),
 ('B', 'C', 4)]

Above steps can be done by combining sorted and dictionary comprehension:

result = list({(i[0], i[1]):i 
             for i in sorted(d, key = lambda x:((x[0], x[1]), x[2]),reverse=True)}.values())

Upvotes: 2

Ajax1234
Ajax1234

Reputation: 71471

You can use itertools.groupby, and select the minimum value in each grouping:

import itertools
d = [('A', 'B', 1), ('C', 'D', 1), 
 ('B', 'D', 2), ('A', 'B', 3), 
 ('A', 'D', 3), ('B', 'C', 4), 
 ('A', 'C', 5), ('B', 'C', 8)]
new_d = [min(list(b), key=lambda x:x[-1]) for _, b in itertools.groupby(sorted(d, key=lambda x:x[:-1]), key=lambda x:x[:-1])]

Output:

[('A', 'B', 1), ('A', 'C', 5), ('A', 'D', 3), ('B', 'C', 4), ('B', 'D', 2), ('C', 'D', 1)]

Upvotes: 1

Related Questions