Flatten A Dictionary Of Dictionaries (2 Levels Deep) Of Lists

I'm trying to wrap my brain around this but it's not flexible enough. In my Python script I have a dictionary of dictionaries of lists. (Actually it gets a little deeper but that l

Solution 1:

I hope you realize that any order you see in a dict is accidental -- it's there only because, when shown on screen, some order has to be picked, but there's absolutely no guarantee.

Net of ordering issues among the various sublists getting catenated,

[x for d in thedict.itervalues()
   for alist in d.itervalues()
   for x in alist]

does what you want without any inefficiency nor intermediate lists.

Solution 2:

edit: re-read the original question and reworked answer to assume that all non-dictionaries are lists to be flattened.

In cases where you're not sure how far down the dictionaries go, you would want to use a recursive function. @Arrieta has already posted a function that recursively builds a list of non-dictionary values.

This one is a generator that yields successive non-dictionary values in the dictionary tree:

def flatten(d):
    """Recursively flatten dictionary values in `d`.

    >>> hat = {'cat': ['images/cat-in-the-hat.png'],
    ...        'fish': {'colours': {'red': [0xFF0000], 'blue': [0x0000FF]},
    ...                 'numbers': {'one': [1], 'two': [2]}},
    ...        'food': {'eggs': {'green': [0x00FF00]},
    ...                 'ham': ['lean', 'medium', 'fat']}}
    >>> set_of_values = set(flatten(hat))
    >>> sorted(set_of_values)
    [1, 2, 255, 65280, 16711680, 'fat', 'images/cat-in-the-hat.png', 'lean', 'medium']
    """
    try:
        for v in d.itervalues():
            for nested_v in flatten(v):
                yield nested_v
    except AttributeError:
        for list_v in d:
            yield list_v

The doctest passes the resulting iterator to the set function. This is likely to be what you want, since, as Mr. Martelli points out, there's no intrinsic order to the values of a dictionary, and therefore no reason to keep track of the order in which they were found.

You may want to keep track of the number of occurrences of each value; this information will be lost if you pass the iterator to set. If you want to track that, just pass the result of flatten(hat) to some other function instead of set. Under Python 2.7, that other function could be collections.Counter. For compatibility with less-evolved pythons, you can write your own function or (with some loss of efficiency) combine sorted with itertools.groupby.

Solution 3:

A recursive function may work:

def flat(d, out=[]):
 for val in d.values():
  if isinstance(val, dict):
    flat(d, out)
  else:
    out+= val

If you try it with :

>>> d = {1: {'a': [1, 2, 3], 'b': [0]}, 2: {'c': [4, 5, 6], 'd': [3, 8]}}
>>> out = []
>>> flat(d, out)
>>> print out
[1, 2, 3, 0, 4, 5, 6, 3, 8]

Notice that dictionaries have no order, so the list is in random order.

You can also return out (at the end of the loop) and don't call the function with a list argument.

def flat(d, out=[]):
 for val in d.values():
  if isinstance(val, dict):
    flat(d, out)
  else:
    out+= val
 return out

call as:

my_list = flat(d)