Python: Group List by Set of Keys

Question

I have an input list of tuples whose entries are:

input_1 = [('v1',['f1','f2','f3']),('v2',['f1','f2','f4']),('v3',['f1','f2','f4'])]
                  ^^^^^^^^^               ^^^^^^^^^               ^^^^^^^^^

I want to know if there is a way to get a list of tuples containing "groups" like the following:

output_1 = [(['f1','f2'],['v1','v2','v3']) , (['f3'],['v1']), (['f4'],['v2','v3'])]

In case that's not enough information, other inputs/outputs might be:

input_2 = [('v1',['f1']),('v2',['f2','f3']),('v3',['f4'])]

output_2 = [(['f1'],['v1']) , (['f2','f3'],['v2']), (['f4'],['v3'])]

or

input_3 = [('v1',['f1','f2']),('v2',['f1','f2']),('v3',['f3']),('v4',['f1','f2'])]
                  ^^^^^^^^^          ^^^^^^^^^                        ^^^^^^^^^

output_3 = [(['f1','f2'],['v1','v2','v4']) , (['f3'],['v3'])]

I think there may be a way to achieve this with implementing the dictionary, but I'm new with Python and I can't figure out how to do this from the examples that I've seen:

Grouping integers by set membership in Python

Make sure all dicts in a list have the same keys

I think I could manage to do this, inefficiently, with a bunch of for loops, but is there a pythonic or clean alternative? Sorry if this question was not well posed but thank you for any input.

Answer 1

You could iterate through both levels then rebuild the input flipping the levels around; it gets you most of the way. The major issue is how would you group the v's that share f's...there are different permutations that could give you the same result as Tim suggests.

Anyways: this is a start.

from collections import defaultdict

input_1 = [('v1',['f1','f2','f3']),
           ('v2',['f1','f2','f4']),
           ('v3',['f1','f2','f4'])]
input_2 = [('v1',['f1']),
           ('v2',['f2','f3']),
           ('v3',['f4'])]
input_3 = [('v1',['f1','f2']),
           ('v2',['f1','f2']),
           ('v3',['f3']),
           ('v4',['f1','f2'])]

def group(inp):
    out = defaultdict(list)
    for group in inp:
        key = group[0]
        for entry in group[1]:
            out[entry].append(key)
    return dict(out)

Outputs would look like:

print group(input_1)
# {'f1': ['v1', 'v2', 'v3'], 
#  'f2': ['v1', 'v2', 'v3'], 
#  'f3': ['v1'], 
#  'f4': ['v2', 'v3']}
print group(input_2)
# {'f1': ['v1'], 
#  'f2': ['v2'], 
#  'f3': ['v2'], 
#  'f4': ['v3']}
print group(input_3)
# {'f1': ['v1', 'v2', 'v4'], 
#  'f2': ['v1', 'v2', 'v4'], 
#  'f3': ['v3']}