# Find duplicates for mixed type values in dictionaries

Following these two SO questions:

I came to the conclusion that the solution I proposed is mature enough to be reviewed here.

The idea is to find duplicates in a dictionary such as example below, but with extended support for mixed type content (seq/mapping/scalars):

d = collections.defaultdict(set)
[d[k].add(v) for k, v in s]

Here's my solution:

import copy
import collections

def faithfulrepr(ds):
"""Returns a plain-text representation of a mixed seq/mapping/scalar
type data structure.

The datastructure is recursively ordered (ordereddict) then a
dataset representation is returned.

Args:

ds  Dataset (mixed seq/mapping/scalar data structure)

Returns:

Sorted plain-text representation of the input dataset.
"""
ds = copy.deepcopy(ds)
if isinstance(ds, collections.Mapping):
res = collections.OrderedDict()
for k, v in sorted(ds.items()):
res[k] = faithfulrepr(v)
return repr(res)
if isinstance(ds, list):
for i, v in enumerate(ds):
ds[i] = faithfulrepr(v)
return repr(ds)
return repr(ds)

def tupelize_dict(ds):
"""Group identical values of a dictionary under the same key. The keys
become a tuple of all the duplicate keys.

Args:

ds: Input dictionary

Example::

ds = {23: 'foo',
25: 'bar',
28: 'foo',
30: 'bar',
33: 'foo'}

>>>tupelize_dict(ds)
{
(23,28,33): 'foo',
(25,30): 'bar'
}
"""
taxonomy = {}
binder = collections.defaultdict(list)
for key, value in ds.items():
signature = faithfulrepr(value)
taxonomy[signature] = value
binder[signature].append(key)
return {tuple(keys): taxonomy[s] for s, keys in binder.items()}

I am open for any better name for tupelize_dict :)

You could just simplify a bit faithfulrepr by using generator expression and removing the need for the deepcopy:

def faithfulrepr(ds):
if isinstance(ds, collections.Mapping):
res = collections.OrderedDict(
(k, faithfulrepr(v)) for k, v in sorted(ds.items())
)
elif isinstance(ds, list):
res = [faithfulrepr(v) for v in ds]
else:
res = ds
return repr(res)

However this method will fail when fed dictionaries that have variable types as their keys (like {1: 'one', 'two': 2}).

An other take on the problem would involve more computations but can compare elements with the equality operator (which seems to be what you are really interested on). It involves maintaining two lists, one for the list of keys and one for the values, and searching in the list of values if the current one already exist. This is done using index which, unfortunately, is $O(n)$ but compares using __eq__:

def tupelize_dict(ds):
keys, values = [], []
for key, value in ds.items():
try:
index = values.index(value)
except ValueError:
values.append(value)
keys.append([key])
else:
keys[index].append(key)
return dict(zip(map(tuple, keys), values))
# or the more readable return {tuple(k): v for k, v in zip(keys, values)}