Merging dictionary keys if values the same

Question

So this is a weird problem that I suspect is really simple to solve. I'm building a lyrics webapp for remote players in my house. It currently generates a dictionary of players with the song they're playing. Eg:

{
    'bathroom': <Song: Blur - Song 2>,
    'bedroom1': <Song: Blur - Song 2>,
    'kitchen': <Song: Meat Loaf - I'd Do Anything for Love (But I Won't Do That)>,
}

Occasionally subsets of these players are synced. So —as above— they display the same value. I'd like to group these in the interface. I could be more intelligent when I'm building the dictionary, but assuming I won't do that, is there a good way to merge keys by value?

The desired output from the above would be, something like:

{
    'bathroom,bedroom1': <Song: Blur - Song 2>,
    'kitchen': <Song: Meat Loaf - I'd Do Anything for Love (But I Won't Do That)>,
}

However this does break how I'd like to look things up (I'd like to specify by name, hence this is a dictionary)... Is there a better collection that can have multiple keys per value and indicate when there are merged duplicates (and backwards-refer to all their keys)?

---

There is a good answer which flips this around to a key of songs, and list of players as a value. This is great except that sometimes I want to know which song is playing on a named player. That's why I originally went with a dictionary.

Is there a good way to preserve a lookup in both directions (short of keeping both collections around)?

Answer 1

from itertools import groupby

x = {
    'bathroom': 'a',
    'bedroom1': 'a',
    'kitchen': 'b'
}


{
  ','.join(i[0] for i in v): k
  for k,v in groupby(sorted(x.iteritems(), key=lambda p: p[1]), lambda p: p[1])
}

Answer 2

When the amount of data involved is significant, this is the type of thing where a relational database comes in handy. A database with two columns, key and value, and an index on the key column, acts kind of like a dict. But you can also put an index on the value column to enable efficient reverse lookups.

In your case, though, since the amount of data involved is small, I'd just make a defaultdict, and add the (value, key) pairs.

reverse_lookup = defaultdict(list)
for k, v in now_playing.items():
    reverse_lookup[v].append(k)

And then you can ','.join() the values to produce your composite keys. Since these composite keys are going to be used for display, it seems, not really for lookup, I'd just keep both the original dict and the reverse lookup dict in memory and use whichever one you need when you do need to perform a lookup. The task of finding other players that are playing the same song as a given one (and are presumably synced) then involves two lookups, one forward and one reverse, but they're hashtable lookups so the added cost is minimal.

---

After some thought about other, more "interesting" ways to do this: you might be able to pervert the disjoint set data structure to meet your needs. You'd have a node for each player, and a node for each song currently being played. The nodes are grouped into sets by song, where one set contains both the node for the song, and the nodes for any players currently playing that song. If you put each set's nodes (song plus players) in a cyclic linked list, as long as the overall data structure is properly maintained, you can start from any node and walk the list to iterate over both the song and the list of players that are playing that song.

The trick, of course, is finding an efficient way to maintain that overall data structure, i.e. to update the cyclic lists as the songs change. If the players are truly synced, it's as easy as replacing one song node with another, each time the whole group of players moves to the next track. But I can imagine an app like the one you're building will often have to do other kinds of lookups, for which the disjoint set structure offers you no benefit.