Python "triplet" dictionary?

Question

If we have (a1, b1) and (a2, b2) it's easy to use a dictionary to store the correspondences:

dict[a1] = b1
dict[a2] = b2

And we can get (a1, b1) and (a2, b2) back no problem.

But, if we have (a1, b1, c1) and (a2, b2, c2), is it possible to get something like:

dict[a1] = (b1, c1)
dict[b1] = (a1, c1)

Where we can use either a1 or b1 to get the triplet (a1, b1, c2) back? Does that make sense? I'm not quite sure which datatype to use for this problem. The above would work but there would be duplicate data.

Basically, if I have a triplet, which data type could I use such that I can use either the first or second value to get the triplet back?

Answer 1

Solution

You can write your own mapping data-structure which allows to add triples, or groups of any size, and recover the group with __getitem__.

class GroupMap:
    def __init__(self):
        self.data = {}

    def add(self, group):
        for item in group:
            self.data[item] = group

    def __getitem__(self, item):
        return self.data[item]

group = (1, 2, 3)
group_map = GroupMap()

group_map.add(group)

print(group_map[1]) # (1, 2, 3)

Notice that this GroupMap can be used for groups of any size, not only triples.

The next step in the above would be to extend the class to avoid collisions according to the behaviour you want when a collision occurs.

Theory

You might wonder if there is a better way to represent groups of connected objects. The answer is not really.

Suppose you have a graph containing n vertices. Then for the graph to be connected, you must have at least n - 1 edges. In the above data-structure, I used n entry in the dict, meaning the solution is nearly optimal.

Why not use n - 1 entries if it can be done? Because you would then need to traverse all your graph to recover the whole group. Thus using one more edge allows for O(1) lookup, which is a trade-off you probably want to take.

Answer 2

An alternative if you want to subclass dict (to get all other methods associated with dict like .get and whatnot) and only get the other elements when asked (for some reason). You can make a new dictionary that is all your own

class TupleDict(dict):

    def __setitem__(self, key, value):
        assert isinstance(key, tuple)
        for i, e in enumerate(key):
            dict.__setitem__(self, e, key[:i] + key[i+1:] + (value,))
        dict.__setitem__(self, value, key)

and then assign any key that is a tuple to a single value (not sure I like this syntax, but we can make it different or use a stand-alone method)

d = TriDict()
d[(1,2)] = 4

and you will have the result of __getitem__ return the rest of the tuple not present.

>>> print(d[1])
(2, 4)
>>> print(d[2])
(1, 4)
print(d[4])
>>> (1, 2)