Iterate over multiple dictionaries with combinations

user_10098481 0
Viewed 159

I have an increasing number of n_term dictionaries, where the values of E need to be combined in a specific way. The dictionaries have the form:

one_terms = {'i': {'E':1},
             'j': {'E':2},
             ...
             'n': {'E':some_int}}
   
two_terms = {'i:j': {'E':12},
             'i:k': {'E':13},
             ...
             'm:n': {'E':some_int}}

three_terms = {'i:j:k': {'E':111},
               'i:j:l': {'E':112},
               ...
               'm:n:o': {'E':some_int}}

The numbers inside are placeholders. In reality these numbers come from computationally expensive calculations. The number of dictionaries holding n-terms (ijkl...n) can also become large. For instance, this can go up to a fifty_term dictionary.

The intention is to combine all the corresponding terms of a n_term dictionary and append that value to the appropriate dictionary. An example explains this better:

the task is relatively simple for a low number of terms (2 or 3), and can be done without an invoking combinations. For example, for the two_term dictionary:

for key, value in two_terms.items():
    i = one_terms[str(key).split(':')[0]]['E']
    j = one_terms[str(key).split(':')[1]]['E']

    ij = 0 -i -j
    two_terms[key]['new_value'] = ij

Gives the solution I desire. And for the three_terms dictionary.

for key, value in three_terms.items():
    i = one_terms[str(key).split(':')[0]]['E']
    j = one_terms[str(key).split(':')[1]]['E']
    k = one_terms[str(key).split(':')[2]]['E']

    ij = two_terms[(str(key).split(':')[0] + ':' + two_terms[(str(key).split(':')[1])]['E']
    ik = two_terms[(str(key).split(':')[0] + ':' + two_terms[(str(key).split(':')[2])]['E']
    jk = two_terms[(str(key).split(':')[1] + ':' + two_terms[(str(key).split(':')[2])]['E']

    ijk = 0 -ij -ik -jk -i -j -k
    three_terms[key]['new_value'] = ijk

Also gives the desired solution. Note that I have used the split() function to go through the different key combinations (ij, ik, etc).

However, for an increasing number of n_terms this method becomes impractical. I need an iterative solution.

My attempt.

I have attempted to use the itertools.combinations library so that I can iteratively go through all combinations.

for C in range(1, len(dictionary):
    for S in itertools.combinations(dictionary, C):

However, this simply provides a tuple which becomes difficult to manipulate into something of the form

n = n_terms[(str(key).split(':')[A] + ':' +\
             str(key).split(':')[B] + ':' +\
             ... 
             str(key).split(':')[Z])]['E']

Where A, B,...Z would be combinations.

In the two_term case, the solution might take the form:

for key, value in two_term.items():
    n_list
    for i in range (0, 2):
        n_list.append(one_terms[str(key).split(':')[i]])

    two_body[key]['E'] = sum(n_list)

Though I am struggling to extend this method.

dictionary python
2 Answers

If you have a large (or even variable) number of these n-term dictionaries, it's a good idea to store them in a separate data structure, e.g. a list where the list index refers to the "n" in n-term:

terms = [
    None,  # zero terms (placeholder to align the n-term index later on)
    {'i': {'E': 1}, 'j': {'E': 2}, 'k': {'E': 3}},  # one terms
    {'i:j': {'E': 12}, 'i:k': {'E': 13}, 'j:k': {'E': 14}},  # two terms
    {'i:j:k': {'E': 111}}  # three terms
    # and so on
]

Then you can loop over these dicts and for each n-terms dictionary you can build combinations of keys for each of the r-terms dicts where r < n:

import itertools as it

for n in range(2, len(terms)):
    for key in terms[n]:
        new_value = 0
        parts = key.split(':')
        for r in range(1, n):
            new_value -= sum(terms[r][':'.join(x)]['E'] for x in it.combinations(parts, r=r))
        terms[n][key]['new_value'] = new_value
user_37672390

For the general case, you would probably want a nested loop, as you already noticed. Do not be afraid of tuples. A data structure with an indeterminate length is exactly what you need to generalize. Instead, be afraid of enumerating all the combinations in your local namespace, as that hinders generalization.

The first problem is that all your dictionaries have a hard-coded human-readable names. That is hard to access in a general purpose loop without using additional data-structures. I would recommend grouping them into a list, such that element N of the list is the dictionary with N + 1 terms:

all_terms = [one_terms, two_terms, three_terms, ..., n_terms]

You call str(key).split(':') for each term, rather than once. Aside from being inefficient, you are not using the result to determine how many elements you actually have. So let's start with that:

z = 2  # 2 chosen arbitrarily. Make it an input
for key, value in all_terms[z].items():
    names = str(key).split(':')

Now len(names) tells you just how deep you need to go, and all_terms lets you actually do it. So let's put that all together, along with some combinations:

    new_value = 0
    for n in range(len(names) - 1):
        for combo in itertools.combinations(names, n + 1):
            new_value -= all_terms[n][':'.join(combo)]['E']
    all_terms[z][key]['new_value'] = new_value

You can put the whole thing into a function that accepts z (the level you want to process) as an input, or just processes the last available element in all_terms, so you can keep expanding it iteratively. Keep in mind that this will become mind-numbingly slow as your list expands and the number of combinations does too:

TL;DR

def expand_terms(terms, level=None):
    if level is None:
        level = len(terms) - 1
    for key, value in terms[level].items():
        names = str(key).split(':')
        new_value = 0
        for n in range(len(names) - 1):
            for combo in itertools.combinations(names, n + 1):
                new_value -= terms[n][':'.join(names)]['E']
        terms[level][key]['new_value'] = new_value
user_29887300
Related